07_divide_conquer.c

Download
c 383 lines 10.5 KB 
  1/*
  2 * ๋ถ„ํ•  ์ •๋ณต (Divide and Conquer)
  3 * Merge Sort, Quick Sort, Fast Exponentiation, Closest Pair
  4 *
  5 * ๋ฌธ์ œ๋ฅผ ์ž‘์€ ๋ถ€๋ถ„์œผ๋กœ ๋‚˜๋ˆ„์–ด ํ•ด๊ฒฐํ•˜๋Š” ๊ธฐ๋ฒ•์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <math.h>
 11#include <float.h>
 12
 13/* =============================================================================
 14 * 1. ๋ณ‘ํ•ฉ ์ •๋ ฌ
 15 * ============================================================================= */
 16
 17void merge(int arr[], int left, int mid, int right) {
 18    int n1 = mid - left + 1;
 19    int n2 = right - mid;
 20
 21    int* L = malloc(n1 * sizeof(int));
 22    int* R = malloc(n2 * sizeof(int));
 23
 24    for (int i = 0; i < n1; i++)
 25        L[i] = arr[left + i];
 26    for (int j = 0; j < n2; j++)
 27        R[j] = arr[mid + 1 + j];
 28
 29    int i = 0, j = 0, k = left;
 30    while (i < n1 && j < n2) {
 31        if (L[i] <= R[j])
 32            arr[k++] = L[i++];
 33        else
 34            arr[k++] = R[j++];
 35    }
 36
 37    while (i < n1) arr[k++] = L[i++];
 38    while (j < n2) arr[k++] = R[j++];
 39
 40    free(L);
 41    free(R);
 42}
 43
 44void merge_sort(int arr[], int left, int right) {
 45    if (left < right) {
 46        int mid = left + (right - left) / 2;
 47        merge_sort(arr, left, mid);
 48        merge_sort(arr, mid + 1, right);
 49        merge(arr, left, mid, right);
 50    }
 51}
 52
 53/* =============================================================================
 54 * 2. ํ€ต ์ •๋ ฌ
 55 * ============================================================================= */
 56
 57void swap(int* a, int* b) {
 58    int temp = *a;
 59    *a = *b;
 60    *b = temp;
 61}
 62
 63int partition(int arr[], int low, int high) {
 64    int pivot = arr[high];
 65    int i = low - 1;
 66
 67    for (int j = low; j < high; j++) {
 68        if (arr[j] < pivot) {
 69            i++;
 70            swap(&arr[i], &arr[j]);
 71        }
 72    }
 73    swap(&arr[i + 1], &arr[high]);
 74    return i + 1;
 75}
 76
 77void quick_sort(int arr[], int low, int high) {
 78    if (low < high) {
 79        int pi = partition(arr, low, high);
 80        quick_sort(arr, low, pi - 1);
 81        quick_sort(arr, pi + 1, high);
 82    }
 83}
 84
 85/* =============================================================================
 86 * 3. ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ
 87 * ============================================================================= */
 88
 89long long power(long long base, long long exp, long long mod) {
 90    long long result = 1;
 91    base %= mod;
 92
 93    while (exp > 0) {
 94        if (exp & 1)
 95            result = (result * base) % mod;
 96        base = (base * base) % mod;
 97        exp >>= 1;
 98    }
 99
100    return result;
101}
102
103/* ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ */
104typedef struct {
105    long long a[2][2];
106} Matrix;
107
108Matrix matrix_multiply(Matrix A, Matrix B, long long mod) {
109    Matrix C = {{{0}}};
110
111    for (int i = 0; i < 2; i++) {
112        for (int j = 0; j < 2; j++) {
113            for (int k = 0; k < 2; k++) {
114                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j]) % mod;
115            }
116        }
117    }
118
119    return C;
120}
121
122Matrix matrix_power(Matrix M, long long n, long long mod) {
123    Matrix result = {{{1, 0}, {0, 1}}};  /* ๋‹จ์œ„ ํ–‰๋ ฌ */
124
125    while (n > 0) {
126        if (n & 1)
127            result = matrix_multiply(result, M, mod);
128        M = matrix_multiply(M, M, mod);
129        n >>= 1;
130    }
131
132    return result;
133}
134
135/* ํ”ผ๋ณด๋‚˜์น˜ O(log n) */
136long long fibonacci_matrix(long long n, long long mod) {
137    if (n <= 1) return n;
138
139    Matrix M = {{{1, 1}, {1, 0}}};
140    Matrix result = matrix_power(M, n - 1, mod);
141
142    return result.a[0][0];
143}
144
145/* =============================================================================
146 * 4. ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ
147 * ============================================================================= */
148
149typedef struct {
150    double x, y;
151} Point;
152
153int compare_x(const void* a, const void* b) {
154    Point* p1 = (Point*)a;
155    Point* p2 = (Point*)b;
156    return (p1->x > p2->x) - (p1->x < p2->x);
157}
158
159int compare_y(const void* a, const void* b) {
160    Point* p1 = (Point*)a;
161    Point* p2 = (Point*)b;
162    return (p1->y > p2->y) - (p1->y < p2->y);
163}
164
165double dist(Point p1, Point p2) {
166    return sqrt((p1.x - p2.x) * (p1.x - p2.x) +
167                (p1.y - p2.y) * (p1.y - p2.y));
168}
169
170double min_double(double a, double b) {
171    return (a < b) ? a : b;
172}
173
174double brute_force(Point points[], int n) {
175    double min_dist = DBL_MAX;
176    for (int i = 0; i < n; i++) {
177        for (int j = i + 1; j < n; j++) {
178            double d = dist(points[i], points[j]);
179            if (d < min_dist) min_dist = d;
180        }
181    }
182    return min_dist;
183}
184
185double strip_closest(Point strip[], int size, double d) {
186    double min_dist = d;
187    qsort(strip, size, sizeof(Point), compare_y);
188
189    for (int i = 0; i < size; i++) {
190        for (int j = i + 1; j < size && (strip[j].y - strip[i].y) < min_dist; j++) {
191            double dist_ij = dist(strip[i], strip[j]);
192            if (dist_ij < min_dist)
193                min_dist = dist_ij;
194        }
195    }
196
197    return min_dist;
198}
199
200double closest_pair_impl(Point points[], int n) {
201    if (n <= 3)
202        return brute_force(points, n);
203
204    int mid = n / 2;
205    Point mid_point = points[mid];
206
207    double dl = closest_pair_impl(points, mid);
208    double dr = closest_pair_impl(points + mid, n - mid);
209    double d = min_double(dl, dr);
210
211    Point* strip = malloc(n * sizeof(Point));
212    int j = 0;
213    for (int i = 0; i < n; i++) {
214        if (fabs(points[i].x - mid_point.x) < d)
215            strip[j++] = points[i];
216    }
217
218    double strip_d = strip_closest(strip, j, d);
219    free(strip);
220
221    return min_double(d, strip_d);
222}
223
224double closest_pair(Point points[], int n) {
225    qsort(points, n, sizeof(Point), compare_x);
226    return closest_pair_impl(points, n);
227}
228
229/* =============================================================================
230 * 5. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ (Inversion Count)
231 * ============================================================================= */
232
233long long merge_count(int arr[], int temp[], int left, int mid, int right) {
234    int i = left, j = mid + 1, k = left;
235    long long inv_count = 0;
236
237    while (i <= mid && j <= right) {
238        if (arr[i] <= arr[j]) {
239            temp[k++] = arr[i++];
240        } else {
241            temp[k++] = arr[j++];
242            inv_count += (mid - i + 1);
243        }
244    }
245
246    while (i <= mid) temp[k++] = arr[i++];
247    while (j <= right) temp[k++] = arr[j++];
248
249    for (i = left; i <= right; i++)
250        arr[i] = temp[i];
251
252    return inv_count;
253}
254
255long long merge_sort_count(int arr[], int temp[], int left, int right) {
256    long long inv_count = 0;
257
258    if (left < right) {
259        int mid = left + (right - left) / 2;
260        inv_count += merge_sort_count(arr, temp, left, mid);
261        inv_count += merge_sort_count(arr, temp, mid + 1, right);
262        inv_count += merge_count(arr, temp, left, mid, right);
263    }
264
265    return inv_count;
266}
267
268long long count_inversions(int arr[], int n) {
269    int* temp = malloc(n * sizeof(int));
270    long long count = merge_sort_count(arr, temp, 0, n - 1);
271    free(temp);
272    return count;
273}
274
275/* =============================================================================
276 * 6. ์นด๋ผ์ธ ๋ฐ” ๊ณฑ์…ˆ
277 * ============================================================================= */
278
279long long karatsuba(long long x, long long y) {
280    if (x < 10 || y < 10)
281        return x * y;
282
283    int n = 0;
284    long long temp = (x > y) ? x : y;
285    while (temp > 0) {
286        n++;
287        temp /= 10;
288    }
289
290    long long half = 1;
291    for (int i = 0; i < n / 2; i++)
292        half *= 10;
293
294    long long a = x / half;
295    long long b = x % half;
296    long long c = y / half;
297    long long d = y % half;
298
299    long long ac = karatsuba(a, c);
300    long long bd = karatsuba(b, d);
301    long long ad_bc = karatsuba(a + b, c + d) - ac - bd;
302
303    return ac * half * half + ad_bc * half + bd;
304}
305
306/* =============================================================================
307 * ํ…Œ์ŠคํŠธ
308 * ============================================================================= */
309
310void print_array(int arr[], int n) {
311    printf("[");
312    for (int i = 0; i < n; i++) {
313        printf("%d", arr[i]);
314        if (i < n - 1) printf(", ");
315    }
316    printf("]\n");
317}
318
319int main(void) {
320    printf("============================================================\n");
321    printf("๋ถ„ํ•  ์ •๋ณต (Divide and Conquer) ์˜ˆ์ œ\n");
322    printf("============================================================\n");
323
324    /* 1. ๋ณ‘ํ•ฉ ์ •๋ ฌ */
325    printf("\n[1] ๋ณ‘ํ•ฉ ์ •๋ ฌ\n");
326    int arr1[] = {38, 27, 43, 3, 9, 82, 10};
327    printf("    ์ •๋ ฌ ์ „: ");
328    print_array(arr1, 7);
329    merge_sort(arr1, 0, 6);
330    printf("    ์ •๋ ฌ ํ›„: ");
331    print_array(arr1, 7);
332
333    /* 2. ํ€ต ์ •๋ ฌ */
334    printf("\n[2] ํ€ต ์ •๋ ฌ\n");
335    int arr2[] = {10, 7, 8, 9, 1, 5};
336    printf("    ์ •๋ ฌ ์ „: ");
337    print_array(arr2, 6);
338    quick_sort(arr2, 0, 5);
339    printf("    ์ •๋ ฌ ํ›„: ");
340    print_array(arr2, 6);
341
342    /* 3. ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ */
343    printf("\n[3] ๋น ๋ฅธ ๊ฑฐ๋“ญ์ œ๊ณฑ\n");
344    printf("    2^10 mod 1000 = %lld\n", power(2, 10, 1000));
345    printf("    3^20 mod 1000000007 = %lld\n", power(3, 20, 1000000007));
346
347    /* 4. ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ - ํ”ผ๋ณด๋‚˜์น˜ */
348    printf("\n[4] ํ–‰๋ ฌ ๊ฑฐ๋“ญ์ œ๊ณฑ - ํ”ผ๋ณด๋‚˜์น˜\n");
349    printf("    fib(10) = %lld\n", fibonacci_matrix(10, 1000000007));
350    printf("    fib(50) = %lld\n", fibonacci_matrix(50, 1000000007));
351
352    /* 5. ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ */
353    printf("\n[5] ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์  ์Œ\n");
354    Point points[] = {{2, 3}, {12, 30}, {40, 50}, {5, 1}, {12, 10}, {3, 4}};
355    printf("    ์ ๋“ค: (2,3), (12,30), (40,50), (5,1), (12,10), (3,4)\n");
356    printf("    ์ตœ์†Œ ๊ฑฐ๋ฆฌ: %.4f\n", closest_pair(points, 6));
357
358    /* 6. ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜ */
359    printf("\n[6] ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜\n");
360    int arr6[] = {8, 4, 2, 1};
361    printf("    ๋ฐฐ์—ด: [8, 4, 2, 1]\n");
362    printf("    ์—ญ์ˆœ ์Œ: %lld\n", count_inversions(arr6, 4));
363
364    /* 7. ์นด๋ผ์ธ ๋ฐ” ๊ณฑ์…ˆ */
365    printf("\n[7] ์นด๋ผ์ธ ๋ฐ” ๊ณฑ์…ˆ\n");
366    printf("    1234 ร— 5678 = %lld\n", karatsuba(1234, 5678));
367    printf("    ๊ฒ€์ฆ: %lld\n", (long long)1234 * 5678);
368
369    /* 8. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์š”์•ฝ */
370    printf("\n[8] ๋ถ„ํ•  ์ •๋ณต ์š”์•ฝ\n");
371    printf("    | ์•Œ๊ณ ๋ฆฌ์ฆ˜      | ์‹œ๊ฐ„ ๋ณต์žก๋„   | ๋ถ„ํ•  ๋ฐฉ์‹        |\n");
372    printf("    |---------------|---------------|------------------|\n");
373    printf("    | ๋ณ‘ํ•ฉ ์ •๋ ฌ     | O(n log n)    | ๋ฐ˜์”ฉ ๋ถ„ํ•         |\n");
374    printf("    | ํ€ต ์ •๋ ฌ       | O(n log n)    | ํ”ผ๋ฒ— ๊ธฐ์ค€ ๋ถ„ํ•    |\n");
375    printf("    | ๊ฑฐ๋“ญ์ œ๊ณฑ      | O(log n)      | ์ง€์ˆ˜ ๋ฐ˜๊ฐ        |\n");
376    printf("    | ๊ฐ€์žฅ ๊ฐ€๊นŒ์šด ์Œ| O(n log n)    | ์ขŒํ‘œ ๊ธฐ์ค€ ๋ถ„ํ•    |\n");
377    printf("    | ์—ญ์ˆœ ์Œ ๊ฐœ์ˆ˜  | O(n log n)    | ๋ณ‘ํ•ฉ ์‹œ ๊ณ„์‚ฐ     |\n");
378
379    printf("\n============================================================\n");
380
381    return 0;
382}