원리 1. 집합의 최댓값을 구해서 최대값만큼의 메모리를 차지하는 카운팅 배열을 만든다. 2. 각원소의 개수를 카운팅시킨다 3. 카운팅 배열의 누적합을 구한다. 4. 카운팅 배열을 통해 순서대로 수를 나열한다. [ 15, 13, 10, 7, 5, 5, 1, 0, 7 ] 카운팅 배열에는 다음과 같이 구성될 수 있습니다. Index 0 1 5 7 10 13 15 count 1 1 2 2 1 1 1 다음을 누적합의 표입니다. Index 0 1 5 7 10 13 15 count 1 2 4 6 7 8 9 이때, 누적합을 구하는 이유는 어느 인덱스에 원본 원소가 들어갈지 순서를 강제하기 위해서 입니다. 정렬된 원소들이 들어갈 배열의 인덱스를 카운팅배열의 데이터 - 1로 설정 해줌으로서 정렬 해줄 수 있습니다. 예를들..

원리 1. 0번부터 n번 인덱스의 데이터를 차례대로 선택하자 2. 선택한 인덱스부터 0까지 인접한 인덱스를 비교하자 3. 만약 인덱스가 낮은 원소가 더 크다면 교환하고 아니라면 탈출한다. (오름차순기준) [ 70, 55, 30, 47, 66 ] (70) 55 30 47 66 --> "70" 55 30 47 66 70 (55) 30 47 66 --> "55" 70 30 47 66 55 70 (30) 47 66 --> "30" 55 70 47 66 30 55 70 (47) 66 --> 30 "47" 55 70 66 30 47 55 70 (66) --> 30 47 55 "66" 70 정렬 후 : [ 30 47 55 66 70 ] 구현 for (int i = 0; i < n - 1; ++i) { int fix ..

원리 1. 정렬되지 않은 중 원소를 가장 작은 원소를 탐색하자 2. 가장 작은 원소를 정렬 되지 않은 원소 맨앞으로 보내자 [ 70, 55, 30, 20, 47 ] | 70, 55, 30, 20, 47 --> 70, 55, 30, (20), 47 (선택) 20, | 70, 55, 30, 47 --> 20, 70, 55, (30), 47 (선택) 20, 30, | 70, 55, 47 --> 20, 30, 70, 55, (47) (선택) 20, 30, 47, | 70, 55 --> 20, 30, 47, 70, (55) (선택) 정렬 후 : [ 20, 30, 47, 55, 70 ] 구현 for (int i = 0; i < n - 1; ++i) { int min_idx = i; for (int j = i + 1..

알고리즘 문제를 풀다보면 흔히 제한 시간 초과 (Time Out)을 경험할 수 있습니다. 이번 포스팅에서는 어떻게 하면 제한 시간 초과를 피할 수 있는지 그 방법에 대해서 다루어보고자 합니다. 보통 시간복잡도를 표기할 때 빅오 표기법 (Big-O Notation)으로 표기하는 것이 일반적입니다. 대표적인 시간복잡도들을 대소 관계로 나타낸 그래프는 아래의 그림과 같습니다. 그래프를 보면 주어진 입력의 크기인 N이 점점 커짐에 따라 시간복잡도의 차이가 수행시간에 큰 영향을 준다는 것을 알 수 있습니다. 상수 시간인 O(1) 이 가장 좋고, 그 다음으로는 O(logN) 이후로 O(N) 순서이며, O(2N) 과 O(N!) 과 같은 지수시간 이상의 알고리즘 들은 N이 굉장히 작은게 아니라면 제한시간 내에 문제를 ..

원리 1. 첫 인덱스부터 인접한 두 원소를 "비교"하자 2. 가장 큰 원소를 "맨뒤"로 보내자 [ 1, 55, 30, 20, 47 ] (1, 55), 30, 20, 47 --> (1, 55), 30, 20, 47 1, (55, 30), 20, 47 --> 1, (30, 55), 20, 47 1, 30, (55, 20), 47 --> 1, 30, (20, 55), 47 1, 30, 20, (55, 47) --> 1, 30, 20, (47, 55) 이 과정을 거쳐서 55이라는 숫자가 맨뒤로 정렬 된 것을 확인할 수 있습니다. 이 과정을 총 n번 반복하면 됩니다. 구현 vector vec = { 55, 7, 78, 12, 42, 3, 2 }; for(int i = 0; i < vec.size(); ++i) f..