정렬

[BOJ] 1822 - 차집합 (C++)

1. 문제 https://www.acmicpc.net/problem/1822 1822번: 차집합 첫째 줄에는 집합 A의 원소의 개수 n(A)와 집합 B의 원소의 개수 n(B)가 빈 칸을 사이에 두고 주어진다. (1 ≤ n(A), n(B) ≤ 500,000)이 주어진다. 둘째 줄에는 집합 A의 원소가, 셋째 줄에는 집합 B의 원소 www.acmicpc.net 집합 A에는 속하지만, B에는 속하지 않는 원소들의 개수와 원소들을 모두 출력하는 문제이다. 집합에서 A - B (차집합)의 개념이 등장한다. 2. 풀이 방법 배열이나 리스트 등을 사용하면 해당 자료형 안에 특정 원소가 있는지 확인하려면 O(1)의 시간이 걸리기에, 접근하는데 시간이 O(1)이 걸리는 맵 자료형을 이용하여 문제를 해결했다. 먼저 A와 ..

[Algo] Insertion Sort - 삽입 정렬

참고한 블로그 : https://gmlwjd9405.github.io/2018/05/06/algorithm-insertion-sort.html [알고리즘] 삽입 정렬(insertion sort)이란 - Heee's Development Blog Step by step goes a long way. gmlwjd9405.github.io 알고리즘을 풀다 내가 삽입 정렬도 구현하지 못하는 것을 발견했고, 잊지 않고자 기록한다... 먼저 삽입 정렬이란 다음과 같다. (오름차순 정렬이라고 가정) https://ko.wikipedia.org/wiki/%EC%82%BD%EC%9E%85_%EC%A0%95%EB%A0%AC 삽입 정렬 - 위키백과, 우리 모두의 백과사전 위키백과, 우리 모두의 백과사전. 삽입 정렬(揷入整列..