06_searching.c

Download
c 376 lines 10.4 KB 
  1/*
  2 * ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Searching Algorithms)
  3 * Linear Search, Binary Search, Parametric Search
  4 *
  5 * ๋‹ค์–‘ํ•œ ํƒ์ƒ‰ ๊ธฐ๋ฒ•๊ณผ ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <stdbool.h>
 11
 12/* =============================================================================
 13 * 1. ์„ ํ˜• ํƒ์ƒ‰ - O(n)
 14 * ============================================================================= */
 15
 16int linear_search(int arr[], int n, int target) {
 17    for (int i = 0; i < n; i++) {
 18        if (arr[i] == target)
 19            return i;
 20    }
 21    return -1;
 22}
 23
 24/* =============================================================================
 25 * 2. ์ด๋ถ„ ํƒ์ƒ‰ - O(log n)
 26 * ============================================================================= */
 27
 28int binary_search(int arr[], int n, int target) {
 29    int left = 0, right = n - 1;
 30
 31    while (left <= right) {
 32        int mid = left + (right - left) / 2;
 33
 34        if (arr[mid] == target)
 35            return mid;
 36        else if (arr[mid] < target)
 37            left = mid + 1;
 38        else
 39            right = mid - 1;
 40    }
 41
 42    return -1;
 43}
 44
 45/* ์žฌ๊ท€ ๋ฒ„์ „ */
 46int binary_search_recursive(int arr[], int left, int right, int target) {
 47    if (left > right)
 48        return -1;
 49
 50    int mid = left + (right - left) / 2;
 51
 52    if (arr[mid] == target)
 53        return mid;
 54    else if (arr[mid] < target)
 55        return binary_search_recursive(arr, mid + 1, right, target);
 56    else
 57        return binary_search_recursive(arr, left, mid - 1, target);
 58}
 59
 60/* =============================================================================
 61 * 3. Lower Bound / Upper Bound
 62 * ============================================================================= */
 63
 64/* target ์ด์ƒ์ธ ์ฒซ ๋ฒˆ์งธ ์œ„์น˜ */
 65int lower_bound(int arr[], int n, int target) {
 66    int left = 0, right = n;
 67
 68    while (left < right) {
 69        int mid = left + (right - left) / 2;
 70        if (arr[mid] < target)
 71            left = mid + 1;
 72        else
 73            right = mid;
 74    }
 75
 76    return left;
 77}
 78
 79/* target ์ดˆ๊ณผ์ธ ์ฒซ ๋ฒˆ์งธ ์œ„์น˜ */
 80int upper_bound(int arr[], int n, int target) {
 81    int left = 0, right = n;
 82
 83    while (left < right) {
 84        int mid = left + (right - left) / 2;
 85        if (arr[mid] <= target)
 86            left = mid + 1;
 87        else
 88            right = mid;
 89    }
 90
 91    return left;
 92}
 93
 94/* target์˜ ๊ฐœ์ˆ˜ */
 95int count_occurrences(int arr[], int n, int target) {
 96    return upper_bound(arr, n, target) - lower_bound(arr, n, target);
 97}
 98
 99/* =============================================================================
100 * 4. ์‚ฝ์ž… ์œ„์น˜ ์ฐพ๊ธฐ
101 * ============================================================================= */
102
103int search_insert(int arr[], int n, int target) {
104    int left = 0, right = n;
105
106    while (left < right) {
107        int mid = left + (right - left) / 2;
108        if (arr[mid] < target)
109            left = mid + 1;
110        else
111            right = mid;
112    }
113
114    return left;
115}
116
117/* =============================================================================
118 * 5. ํšŒ์ „ ์ •๋ ฌ ๋ฐฐ์—ด ํƒ์ƒ‰
119 * ============================================================================= */
120
121int search_rotated(int arr[], int n, int target) {
122    int left = 0, right = n - 1;
123
124    while (left <= right) {
125        int mid = left + (right - left) / 2;
126
127        if (arr[mid] == target)
128            return mid;
129
130        /* ์™ผ์ชฝ์ด ์ •๋ ฌ๋จ */
131        if (arr[left] <= arr[mid]) {
132            if (arr[left] <= target && target < arr[mid])
133                right = mid - 1;
134            else
135                left = mid + 1;
136        }
137        /* ์˜ค๋ฅธ์ชฝ์ด ์ •๋ ฌ๋จ */
138        else {
139            if (arr[mid] < target && target <= arr[right])
140                left = mid + 1;
141            else
142                right = mid - 1;
143        }
144    }
145
146    return -1;
147}
148
149/* ํšŒ์ „ ๋ฐฐ์—ด์—์„œ ์ตœ์†Ÿ๊ฐ’ */
150int find_min_rotated(int arr[], int n) {
151    int left = 0, right = n - 1;
152
153    while (left < right) {
154        int mid = left + (right - left) / 2;
155
156        if (arr[mid] > arr[right])
157            left = mid + 1;
158        else
159            right = mid;
160    }
161
162    return arr[left];
163}
164
165/* =============================================================================
166 * 6. ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜
167 * ============================================================================= */
168
169/* ๋ฐฐ์—ด์„ k๊ฐœ๋กœ ๋‚˜๋ˆŒ ๋•Œ ์ตœ๋Œ€ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’ */
170bool can_split(int arr[], int n, int max_sum, int k) {
171    int count = 1;
172    int current_sum = 0;
173
174    for (int i = 0; i < n; i++) {
175        if (arr[i] > max_sum)
176            return false;
177
178        if (current_sum + arr[i] > max_sum) {
179            count++;
180            current_sum = arr[i];
181        } else {
182            current_sum += arr[i];
183        }
184    }
185
186    return count <= k;
187}
188
189int split_array_min_max(int arr[], int n, int k) {
190    int left = 0, right = 0;
191
192    for (int i = 0; i < n; i++) {
193        if (arr[i] > left) left = arr[i];
194        right += arr[i];
195    }
196
197    while (left < right) {
198        int mid = left + (right - left) / 2;
199
200        if (can_split(arr, n, mid, k))
201            right = mid;
202        else
203            left = mid + 1;
204    }
205
206    return left;
207}
208
209/* ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ: ๋†’์ด H๋กœ ์ž˜๋ž์„ ๋•Œ M ์ด์ƒ์˜ ๋‚˜๋ฌด๋ฅผ ์–ป์„ ์ˆ˜ ์žˆ๋Š” ์ตœ๋Œ€ H */
210long long cut_trees(int trees[], int n, long long target) {
211    long long left = 0, right = 0;
212
213    for (int i = 0; i < n; i++) {
214        if (trees[i] > right)
215            right = trees[i];
216    }
217
218    while (left < right) {
219        long long mid = left + (right - left + 1) / 2;
220        long long total = 0;
221
222        for (int i = 0; i < n; i++) {
223            if (trees[i] > mid)
224                total += trees[i] - mid;
225        }
226
227        if (total >= target)
228            left = mid;
229        else
230            right = mid - 1;
231    }
232
233    return left;
234}
235
236/* =============================================================================
237 * 7. ์‹ค์ˆ˜ ์ด๋ถ„ ํƒ์ƒ‰
238 * ============================================================================= */
239
240double sqrt_binary_search(double x) {
241    if (x < 0) return -1;
242    if (x < 1) {
243        double lo = x, hi = 1.0;
244        while (hi - lo > 1e-9) {
245            double mid = (lo + hi) / 2;
246            if (mid * mid < x)
247                lo = mid;
248            else
249                hi = mid;
250        }
251        return lo;
252    }
253
254    double lo = 1.0, hi = x;
255    while (hi - lo > 1e-9) {
256        double mid = (lo + hi) / 2;
257        if (mid * mid < x)
258            lo = mid;
259        else
260            hi = mid;
261    }
262    return lo;
263}
264
265/* =============================================================================
266 * 8. ํ”ผํฌ ์ฐพ๊ธฐ
267 * ============================================================================= */
268
269int find_peak(int arr[], int n) {
270    int left = 0, right = n - 1;
271
272    while (left < right) {
273        int mid = left + (right - left) / 2;
274
275        if (arr[mid] < arr[mid + 1])
276            left = mid + 1;
277        else
278            right = mid;
279    }
280
281    return left;
282}
283
284/* =============================================================================
285 * ํ…Œ์ŠคํŠธ
286 * ============================================================================= */
287
288void print_array(int arr[], int n) {
289    printf("[");
290    for (int i = 0; i < n; i++) {
291        printf("%d", arr[i]);
292        if (i < n - 1) printf(", ");
293    }
294    printf("]");
295}
296
297int main(void) {
298    printf("============================================================\n");
299    printf("ํƒ์ƒ‰ ์•Œ๊ณ ๋ฆฌ์ฆ˜ (Searching Algorithms) ์˜ˆ์ œ\n");
300    printf("============================================================\n");
301
302    /* 1. ์ด๋ถ„ ํƒ์ƒ‰ */
303    printf("\n[1] ์ด๋ถ„ ํƒ์ƒ‰\n");
304    int arr1[] = {1, 3, 5, 7, 9, 11, 13, 15};
305    printf("    ๋ฐฐ์—ด: ");
306    print_array(arr1, 8);
307    printf("\n");
308    printf("    7์˜ ์œ„์น˜: %d\n", binary_search(arr1, 8, 7));
309    printf("    6์˜ ์œ„์น˜: %d\n", binary_search(arr1, 8, 6));
310
311    /* 2. Lower/Upper Bound */
312    printf("\n[2] Lower/Upper Bound\n");
313    int arr2[] = {1, 2, 2, 2, 3, 4, 4, 5};
314    printf("    ๋ฐฐ์—ด: ");
315    print_array(arr2, 8);
316    printf("\n");
317    printf("    lower_bound(2): %d\n", lower_bound(arr2, 8, 2));
318    printf("    upper_bound(2): %d\n", upper_bound(arr2, 8, 2));
319    printf("    2์˜ ๊ฐœ์ˆ˜: %d\n", count_occurrences(arr2, 8, 2));
320
321    /* 3. ์‚ฝ์ž… ์œ„์น˜ */
322    printf("\n[3] ์‚ฝ์ž… ์œ„์น˜\n");
323    int arr3[] = {1, 3, 5, 7};
324    printf("    ๋ฐฐ์—ด: [1,3,5,7]\n");
325    printf("    4์˜ ์‚ฝ์ž… ์œ„์น˜: %d\n", search_insert(arr3, 4, 4));
326    printf("    6์˜ ์‚ฝ์ž… ์œ„์น˜: %d\n", search_insert(arr3, 4, 6));
327
328    /* 4. ํšŒ์ „ ๋ฐฐ์—ด */
329    printf("\n[4] ํšŒ์ „ ๋ฐฐ์—ด ํƒ์ƒ‰\n");
330    int arr4[] = {4, 5, 6, 7, 0, 1, 2};
331    printf("    ๋ฐฐ์—ด: ");
332    print_array(arr4, 7);
333    printf("\n");
334    printf("    0์˜ ์œ„์น˜: %d\n", search_rotated(arr4, 7, 0));
335    printf("    ์ตœ์†Ÿ๊ฐ’: %d\n", find_min_rotated(arr4, 7));
336
337    /* 5. ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜ - ๋ฐฐ์—ด ๋ถ„ํ•  */
338    printf("\n[5] ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜ - ๋ฐฐ์—ด ๋ถ„ํ• \n");
339    int arr5[] = {7, 2, 5, 10, 8};
340    printf("    ๋ฐฐ์—ด: [7,2,5,10,8], k=2\n");
341    printf("    ์ตœ๋Œ€ ํ•ฉ์˜ ์ตœ์†Ÿ๊ฐ’: %d\n", split_array_min_max(arr5, 5, 2));
342
343    /* 6. ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ */
344    printf("\n[6] ๋‚˜๋ฌด ์ž๋ฅด๊ธฐ\n");
345    int trees[] = {20, 15, 10, 17};
346    long long target = 7;
347    printf("    ๋‚˜๋ฌด ๋†’์ด: [20,15,10,17], ํ•„์š”๋Ÿ‰: %lld\n", target);
348    printf("    ์ตœ๋Œ€ ์ ˆ๋‹จ ๋†’์ด: %lld\n", cut_trees(trees, 4, target));
349
350    /* 7. ์‹ค์ˆ˜ ์ด๋ถ„ ํƒ์ƒ‰ */
351    printf("\n[7] ์ œ๊ณฑ๊ทผ ์ด๋ถ„ ํƒ์ƒ‰\n");
352    printf("    sqrt(2): %.6f\n", sqrt_binary_search(2));
353    printf("    sqrt(10): %.6f\n", sqrt_binary_search(10));
354
355    /* 8. ํ”ผํฌ ์ฐพ๊ธฐ */
356    printf("\n[8] ํ”ผํฌ ์ฐพ๊ธฐ\n");
357    int arr8[] = {1, 2, 1, 3, 5, 6, 4};
358    printf("    ๋ฐฐ์—ด: [1,2,1,3,5,6,4]\n");
359    int peak_idx = find_peak(arr8, 7);
360    printf("    ํ”ผํฌ ์ธ๋ฑ์Šค: %d (๊ฐ’: %d)\n", peak_idx, arr8[peak_idx]);
361
362    /* 9. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์š”์•ฝ */
363    printf("\n[9] ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ ์ •๋ฆฌ\n");
364    printf("    | ๋ฌธ์ œ ์œ ํ˜•        | ํ•ต์‹ฌ ์•„์ด๋””์–ด             |\n");
365    printf("    |------------------|---------------------------|\n");
366    printf("    | lower_bound      | arr[mid] < target         |\n");
367    printf("    | upper_bound      | arr[mid] <= target        |\n");
368    printf("    | ํšŒ์ „ ๋ฐฐ์—ด        | ์ •๋ ฌ๋œ ์ ˆ๋ฐ˜ ์ฐพ๊ธฐ          |\n");
369    printf("    | ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ       | ๊ฒฐ์ • ๋ฌธ์ œ๋กœ ๋ณ€ํ™˜          |\n");
370    printf("    | ์ตœ๋Œ€์˜ ์ตœ์†Œ      | ๊ฐ€๋Šฅํ•œ ์ตœ์†Œ๊ฐ’ ์ด๋ถ„ํƒ์ƒ‰    |\n");
371
372    printf("\n============================================================\n");
373
374    return 0;
375}