WHAT SPARKS A LIGHT IN YOU

각각의 자릿수 별로 정렬하여 완벽히 정렬된 배열을 만들어내는 알고리즘 #define N 10 #define K 40 #define D 2 int data[N] = {40, 6, 1, 9, 3, 5, 5, 3, 6, 6}; int cnt[K + 2]; int ans[N]; int main(void) { radixSort(); } void radixSort(void) { int i, j; for (i = 0; i < D; i++) // 작은 자리수부터 계산하는 이뉴는 stable sort를 위해 { countingSort(i); for (j = 0; j < N; j++) data[j] = ans[j]; } } void countingSort(int digit) { int i; int t1 = (int)pow..

각각의 원소가 몇 개 존재하는지 counting 한 후 개수를 센 배열을 통해서 정렬된 배열을 뽑아내는 방법 제한사항 데이터는 양의 정수여야 함 데이터 범위(0 ~ K)의 제한이 있음 #define N 10 #define K 40 int data[N] = {40, 6, 1, 9, 3, 5, 5, 3, 6, 6}; int cnt[K + 2]; int ans[N]; int main(void) { int i; for (i = 0; i < N; i++) { cnt[data[i]]++; } for (i = 1; i = 0; i--) { ans[--cnt[data[i]]] = data[i]; // 뒤에서부터 계산하는 이유는 stable sort를 위해 } for (i = 0; i < N; i++) { printf(..

자료구조인 힙(heap)을 이용한 정렬 알고리즘 Heap을 구성한 후 원소들을 다 삽입하고 하나씩 빼면서 배열의 앞에서부터 채워넣는다. #define N 6 int data[N] = {40, 6, 1, 9, 3, 5}; int h[N + 5]; int cnt; heapSort(0, N - 1); void swap(int i, int j) { int t = h[i]; h[i] = h[j]; h[j] = t; } void upHeapify(int index) { if (index == 1) return; if (h[index] < h[index / 2]) { swap(index, index / 2); upHeapify(index / 2); } } void insert(int data) { h[++cnt] =..

합병 정렬과 비슷하게 분할 정복을 이용한 방법 (단, 합병 정렬과 달리 공간복잡도를 N만 사용) Pivot을 설정한다. 0 ~ N-1까지 원소들을 pivot을 기준으로 좌, 우로 나뉘게 한다. (partition) Pivot을 기준으로 나뉜 왼쪽, 오른쪽 부분배열을 각각 정렬한다. (재귀) #define N 6 quickSort(0, N - 1); void quickSort(int left, int right) { if (left

분할 정복을 이용한 정렬 알고리즘 분할 : 배열을 2등분하여 2개의 부분배열로 만든다. 정복 : 각각의 부분배열을 정렬한다. (재귀) 통합 : 정렬된 부분배열을 정렬된 하나의 배열로 합친다. #define N 6 int data[N] = {40, 6, 1, 9, 3, 5}; int temp[N]; int cnt; mergeSort(0, N - 1); void mergeSort(int left, int right) { int mid = (left + right) / 2; if (right == left) return; mergeSort(left, mid); mergeSort(mid + 1, right); merge(left, right); } void merge(int left, int right) { c..

한 번 loop가 돌 때마다 최솟값을 찾아 가장 앞에 넣어주는 방법을 N번 반복하는 방법 시간복잡도 : O(n^2) 공간복잡도 : O(n^2) #define N 6 int data[N] = {40, 6, 1, 9, 3, 5}; int v; for (i = 0; i data[j]) v = j; } swap(i, v); }

비교되는 인접한 두 쌍이 거품처럼 발생한다고 붙여진 이름 시간복잡도 : O(N^2) 공간복잡도 : O(N) #define N 6 int data[N] = {40, 6, 1, 9, 3, 5}; for (i = 1; i data[j]) swap(j - 1, j); } }

재귀는 직관대로 따라 들어가며 읽는 것이 아니라, 수학적 귀납법을 통해 증명해야 한다. 수학적 귀납법 : 𝑃(1)이 참이고 , 𝑃(𝑛)→𝑃(𝑛+1)이 참이면 𝑃(𝑛)은 모든 자연수 𝑛에 대해서 참이다. 수학적 귀납법에서 필요한 것은 𝑃(𝑛)→𝑃(𝑛+1)이 참임을 보이는 것 뿐이므로 𝑃(𝑛)이 정말로 참일 필요는 없음. 즉, 𝑃(𝑛)은 참이라고 가정하고 𝑃(𝑛+1)를 증명하기만 하면 된다. int sum(int x) { if (x