29_practice.c

Download
c 450 lines 12.9 KB 
  1/*
  2 * ์‹ค์ „ ๋ฌธ์ œ ํ’€์ด (Practice Problems)
  3 * ์ข…ํ•ฉ ๋ฌธ์ œ (๋‹ค์–‘ํ•œ ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์กฐํ•ฉ)
  4 *
  5 * ์ฝ”๋”ฉ ํ…Œ์ŠคํŠธ์—์„œ ์ž์ฃผ ๋‚˜์˜ค๋Š” ์œ ํ˜•๋“ค์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11#include <stdbool.h>
 12#include <limits.h>
 13
 14#define MAX_N 100001
 15#define INF INT_MAX
 16
 17typedef long long ll;
 18
 19/* =============================================================================
 20 * 1. ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (ํˆฌ ํฌ์ธํ„ฐ)
 21 * ============================================================================= */
 22
 23/* ํ•ฉ์ด target ์ด์ƒ์ธ ์ตœ์†Œ ๊ธธ์ด ๋ถ€๋ถ„ ๋ฐฐ์—ด */
 24int min_subarray_sum(int arr[], int n, int target) {
 25    int left = 0;
 26    int sum = 0;
 27    int min_len = n + 1;
 28
 29    for (int right = 0; right < n; right++) {
 30        sum += arr[right];
 31
 32        while (sum >= target) {
 33            int len = right - left + 1;
 34            if (len < min_len) min_len = len;
 35            sum -= arr[left++];
 36        }
 37    }
 38
 39    return (min_len == n + 1) ? 0 : min_len;
 40}
 41
 42/* =============================================================================
 43 * 2. ์ž‘์—… ์Šค์ผ€์ค„๋ง (Greedy + Heap)
 44 * ============================================================================= */
 45
 46typedef struct {
 47    int deadline;
 48    int profit;
 49} Job;
 50
 51int compare_jobs(const void* a, const void* b) {
 52    return ((Job*)b)->profit - ((Job*)a)->profit;
 53}
 54
 55int job_scheduling(Job jobs[], int n) {
 56    qsort(jobs, n, sizeof(Job), compare_jobs);
 57
 58    int max_deadline = 0;
 59    for (int i = 0; i < n; i++) {
 60        if (jobs[i].deadline > max_deadline)
 61            max_deadline = jobs[i].deadline;
 62    }
 63
 64    int* slot = malloc((max_deadline + 1) * sizeof(int));
 65    memset(slot, -1, (max_deadline + 1) * sizeof(int));
 66
 67    int total_profit = 0;
 68    int job_count = 0;
 69
 70    for (int i = 0; i < n; i++) {
 71        for (int j = jobs[i].deadline; j >= 1; j--) {
 72            if (slot[j] == -1) {
 73                slot[j] = i;
 74                total_profit += jobs[i].profit;
 75                job_count++;
 76                break;
 77            }
 78        }
 79    }
 80
 81    free(slot);
 82    return total_profit;
 83}
 84
 85/* =============================================================================
 86 * 3. ์ตœ์†Œ ํšŒ์˜์‹ค ์ˆ˜ (์ด๋ฒคํŠธ ์ •๋ ฌ)
 87 * ============================================================================= */
 88
 89typedef struct {
 90    int time;
 91    int type;  /* 1: ์‹œ์ž‘, -1: ์ข…๋ฃŒ */
 92} Event;
 93
 94int compare_events(const void* a, const void* b) {
 95    Event* e1 = (Event*)a;
 96    Event* e2 = (Event*)b;
 97    if (e1->time != e2->time)
 98        return e1->time - e2->time;
 99    return e1->type - e2->type;  /* ์ข…๋ฃŒ๊ฐ€ ๋จผ์ € */
100}
101
102int min_meeting_rooms(int start[], int end[], int n) {
103    Event* events = malloc(2 * n * sizeof(Event));
104
105    for (int i = 0; i < n; i++) {
106        events[2 * i] = (Event){start[i], 1};
107        events[2 * i + 1] = (Event){end[i], -1};
108    }
109
110    qsort(events, 2 * n, sizeof(Event), compare_events);
111
112    int rooms = 0, max_rooms = 0;
113    for (int i = 0; i < 2 * n; i++) {
114        rooms += events[i].type;
115        if (rooms > max_rooms) max_rooms = rooms;
116    }
117
118    free(events);
119    return max_rooms;
120}
121
122/* =============================================================================
123 * 4. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜ (DP)
124 * ============================================================================= */
125
126int min_palindrome_insertions(char* s) {
127    int n = strlen(s);
128    int** dp = malloc(n * sizeof(int*));
129    for (int i = 0; i < n; i++) {
130        dp[i] = calloc(n, sizeof(int));
131    }
132
133    for (int len = 2; len <= n; len++) {
134        for (int i = 0; i + len - 1 < n; i++) {
135            int j = i + len - 1;
136            if (s[i] == s[j]) {
137                dp[i][j] = dp[i + 1][j - 1];
138            } else {
139                int v1 = dp[i + 1][j];
140                int v2 = dp[i][j - 1];
141                dp[i][j] = 1 + (v1 < v2 ? v1 : v2);
142            }
143        }
144    }
145
146    int result = dp[0][n - 1];
147    for (int i = 0; i < n; i++) free(dp[i]);
148    free(dp);
149    return result;
150}
151
152/* =============================================================================
153 * 5. ์„ฌ์˜ ๊ฐœ์ˆ˜ (DFS/BFS)
154 * ============================================================================= */
155
156int dx[] = {-1, 1, 0, 0};
157int dy[] = {0, 0, -1, 1};
158
159void dfs_island(int** grid, int rows, int cols, int i, int j, bool** visited) {
160    if (i < 0 || i >= rows || j < 0 || j >= cols) return;
161    if (visited[i][j] || grid[i][j] == 0) return;
162
163    visited[i][j] = true;
164    for (int d = 0; d < 4; d++) {
165        dfs_island(grid, rows, cols, i + dx[d], j + dy[d], visited);
166    }
167}
168
169int count_islands(int** grid, int rows, int cols) {
170    bool** visited = malloc(rows * sizeof(bool*));
171    for (int i = 0; i < rows; i++) {
172        visited[i] = calloc(cols, sizeof(bool));
173    }
174
175    int count = 0;
176    for (int i = 0; i < rows; i++) {
177        for (int j = 0; j < cols; j++) {
178            if (grid[i][j] == 1 && !visited[i][j]) {
179                dfs_island(grid, rows, cols, i, j, visited);
180                count++;
181            }
182        }
183    }
184
185    for (int i = 0; i < rows; i++) free(visited[i]);
186    free(visited);
187    return count;
188}
189
190/* =============================================================================
191 * 6. Union-Find ์‘์šฉ (์ค‘๋ณต ์—ฐ๊ฒฐ)
192 * ============================================================================= */
193
194int uf_parent[MAX_N];
195int uf_rank_arr[MAX_N];
196
197void uf_init(int n) {
198    for (int i = 0; i < n; i++) {
199        uf_parent[i] = i;
200        uf_rank_arr[i] = 0;
201    }
202}
203
204int uf_find(int x) {
205    if (uf_parent[x] != x)
206        uf_parent[x] = uf_find(uf_parent[x]);
207    return uf_parent[x];
208}
209
210bool uf_union(int x, int y) {
211    int px = uf_find(x);
212    int py = uf_find(y);
213    if (px == py) return false;
214
215    if (uf_rank_arr[px] < uf_rank_arr[py]) {
216        uf_parent[px] = py;
217    } else if (uf_rank_arr[px] > uf_rank_arr[py]) {
218        uf_parent[py] = px;
219    } else {
220        uf_parent[py] = px;
221        uf_rank_arr[px]++;
222    }
223    return true;
224}
225
226/* ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ */
227int* find_redundant_connection(int edges[][2], int n) {
228    uf_init(n + 1);
229    static int result[2];
230
231    for (int i = 0; i < n; i++) {
232        if (!uf_union(edges[i][0], edges[i][1])) {
233            result[0] = edges[i][0];
234            result[1] = edges[i][1];
235            return result;
236        }
237    }
238
239    result[0] = -1;
240    result[1] = -1;
241    return result;
242}
243
244/* =============================================================================
245 * 7. LIS (Longest Increasing Subsequence)
246 * ============================================================================= */
247
248int lower_bound(int arr[], int n, int target) {
249    int lo = 0, hi = n;
250    while (lo < hi) {
251        int mid = (lo + hi) / 2;
252        if (arr[mid] < target) lo = mid + 1;
253        else hi = mid;
254    }
255    return lo;
256}
257
258int lis_length(int arr[], int n) {
259    int* tails = malloc(n * sizeof(int));
260    int len = 0;
261
262    for (int i = 0; i < n; i++) {
263        int pos = lower_bound(tails, len, arr[i]);
264        tails[pos] = arr[i];
265        if (pos == len) len++;
266    }
267
268    free(tails);
269    return len;
270}
271
272/* =============================================================================
273 * 8. ์Šค๋„์ฟ  (๋ฐฑํŠธ๋ž˜ํ‚น)
274 * ============================================================================= */
275
276bool is_valid_sudoku(int board[9][9], int row, int col, int num) {
277    /* ํ–‰ ๊ฒ€์‚ฌ */
278    for (int j = 0; j < 9; j++) {
279        if (board[row][j] == num) return false;
280    }
281
282    /* ์—ด ๊ฒ€์‚ฌ */
283    for (int i = 0; i < 9; i++) {
284        if (board[i][col] == num) return false;
285    }
286
287    /* 3x3 ๋ฐ•์Šค ๊ฒ€์‚ฌ */
288    int box_row = (row / 3) * 3;
289    int box_col = (col / 3) * 3;
290    for (int i = 0; i < 3; i++) {
291        for (int j = 0; j < 3; j++) {
292            if (board[box_row + i][box_col + j] == num) return false;
293        }
294    }
295
296    return true;
297}
298
299bool solve_sudoku(int board[9][9]) {
300    for (int i = 0; i < 9; i++) {
301        for (int j = 0; j < 9; j++) {
302            if (board[i][j] == 0) {
303                for (int num = 1; num <= 9; num++) {
304                    if (is_valid_sudoku(board, i, j, num)) {
305                        board[i][j] = num;
306                        if (solve_sudoku(board)) return true;
307                        board[i][j] = 0;
308                    }
309                }
310                return false;
311            }
312        }
313    }
314    return true;
315}
316
317/* =============================================================================
318 * 9. ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ (ํŒŒ๋ผ๋ฉ”ํŠธ๋ฆญ ์„œ์น˜)
319 * ============================================================================= */
320
321/* ์ตœ๋Œ€ ์šด๋ฐ˜ ํšŸ์ˆ˜๊ฐ€ days ์ดํ•˜๊ฐ€ ๋˜๋„๋ก ํ•˜๋Š” ์ตœ์†Œ ์šฉ๋Ÿ‰ */
322bool can_ship(int weights[], int n, int capacity, int days) {
323    int current = 0;
324    int day_count = 1;
325
326    for (int i = 0; i < n; i++) {
327        if (weights[i] > capacity) return false;
328        if (current + weights[i] > capacity) {
329            day_count++;
330            current = weights[i];
331        } else {
332            current += weights[i];
333        }
334    }
335
336    return day_count <= days;
337}
338
339int ship_within_days(int weights[], int n, int days) {
340    int max_weight = 0, total = 0;
341    for (int i = 0; i < n; i++) {
342        if (weights[i] > max_weight) max_weight = weights[i];
343        total += weights[i];
344    }
345
346    int lo = max_weight, hi = total;
347    while (lo < hi) {
348        int mid = (lo + hi) / 2;
349        if (can_ship(weights, n, mid, days)) {
350            hi = mid;
351        } else {
352            lo = mid + 1;
353        }
354    }
355
356    return lo;
357}
358
359/* =============================================================================
360 * ํ…Œ์ŠคํŠธ
361 * ============================================================================= */
362
363int main(void) {
364    printf("============================================================\n");
365    printf("์‹ค์ „ ๋ฌธ์ œ ํ’€์ด ์˜ˆ์ œ\n");
366    printf("============================================================\n");
367
368    /* 1. ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ */
369    printf("\n[1] ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (ํˆฌ ํฌ์ธํ„ฐ)\n");
370    int arr1[] = {2, 3, 1, 2, 4, 3};
371    printf("    ๋ฐฐ์—ด: [2, 3, 1, 2, 4, 3], target = 7\n");
372    printf("    ์ตœ์†Œ ๊ธธ์ด: %d\n", min_subarray_sum(arr1, 6, 7));
373
374    /* 2. ์ž‘์—… ์Šค์ผ€์ค„๋ง */
375    printf("\n[2] ์ž‘์—… ์Šค์ผ€์ค„๋ง (Greedy)\n");
376    Job jobs[] = {{4, 20}, {1, 10}, {1, 40}, {1, 30}};
377    printf("    ์ž‘์—…: {๋งˆ๊ฐ:4,์ด์ต:20}, {1,10}, {1,40}, {1,30}\n");
378    printf("    ์ตœ๋Œ€ ์ด์ต: %d\n", job_scheduling(jobs, 4));
379
380    /* 3. ์ตœ์†Œ ํšŒ์˜์‹ค */
381    printf("\n[3] ์ตœ์†Œ ํšŒ์˜์‹ค ์ˆ˜\n");
382    int start[] = {0, 5, 15};
383    int end[] = {30, 10, 20};
384    printf("    ํšŒ์˜: [0-30], [5-10], [15-20]\n");
385    printf("    ์ตœ์†Œ ํšŒ์˜์‹ค: %d\n", min_meeting_rooms(start, end, 3));
386
387    /* 4. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜ */
388    printf("\n[4] ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ณ€ํ™˜\n");
389    printf("    ๋ฌธ์ž์—ด: \"abcde\"\n");
390    printf("    ์ตœ์†Œ ์‚ฝ์ž…: %d\n", min_palindrome_insertions("abcde"));
391
392    /* 5. ์„ฌ์˜ ๊ฐœ์ˆ˜ */
393    printf("\n[5] ์„ฌ์˜ ๊ฐœ์ˆ˜\n");
394    int grid_data[4][4] = {
395        {1, 1, 0, 0},
396        {1, 0, 0, 0},
397        {0, 0, 1, 0},
398        {0, 0, 0, 1}
399    };
400    int** grid = malloc(4 * sizeof(int*));
401    for (int i = 0; i < 4; i++) {
402        grid[i] = malloc(4 * sizeof(int));
403        for (int j = 0; j < 4; j++) grid[i][j] = grid_data[i][j];
404    }
405    printf("    ๊ทธ๋ฆฌ๋“œ:\n");
406    for (int i = 0; i < 4; i++) {
407        printf("      ");
408        for (int j = 0; j < 4; j++) printf("%d ", grid[i][j]);
409        printf("\n");
410    }
411    printf("    ์„ฌ์˜ ๊ฐœ์ˆ˜: %d\n", count_islands(grid, 4, 4));
412    for (int i = 0; i < 4; i++) free(grid[i]);
413    free(grid);
414
415    /* 6. ์ค‘๋ณต ์—ฐ๊ฒฐ */
416    printf("\n[6] ์ค‘๋ณต ์—ฐ๊ฒฐ ์ฐพ๊ธฐ (Union-Find)\n");
417    int edges[][2] = {{1, 2}, {1, 3}, {2, 3}};
418    int* redundant = find_redundant_connection(edges, 3);
419    printf("    ๊ฐ„์„ : (1,2), (1,3), (2,3)\n");
420    printf("    ์ค‘๋ณต ์—ฐ๊ฒฐ: (%d, %d)\n", redundant[0], redundant[1]);
421
422    /* 7. LIS */
423    printf("\n[7] ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„์ˆ˜์—ด (LIS)\n");
424    int arr2[] = {10, 9, 2, 5, 3, 7, 101, 18};
425    printf("    ๋ฐฐ์—ด: [10, 9, 2, 5, 3, 7, 101, 18]\n");
426    printf("    LIS ๊ธธ์ด: %d\n", lis_length(arr2, 8));
427
428    /* 8. ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ */
429    printf("\n[8] ์ด๋ถ„ ํƒ์ƒ‰ ์‘์šฉ (๋ฐฐ์†ก)\n");
430    int weights[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
431    printf("    ๋ฌผ๊ฑด ๋ฌด๊ฒŒ: [1-10]\n");
432    printf("    5์ผ ๋‚ด ๋ฐฐ์†ก ์ตœ์†Œ ์šฉ๋Ÿ‰: %d\n", ship_within_days(weights, 10, 5));
433
434    /* 9. ๋ฌธ์ œ ํ’€์ด ์ „๋žต */
435    printf("\n[9] ๋ฌธ์ œ ํ’€์ด ์ „๋žต\n");
436    printf("    1. ๋ฌธ์ œ ์ดํ•ด: ์ž…๋ ฅ/์ถœ๋ ฅ, ์ œ์•ฝ ์กฐ๊ฑด ํ™•์ธ\n");
437    printf("    2. ์˜ˆ์ œ ๋ถ„์„: ์†์œผ๋กœ ํ’€์–ด๋ณด๊ธฐ\n");
438    printf("    3. ์•Œ๊ณ ๋ฆฌ์ฆ˜ ์„ ํƒ:\n");
439    printf("       - N โ‰ค 20: ์™„์ „ ํƒ์ƒ‰, ๋น„ํŠธ๋งˆ์Šคํฌ\n");
440    printf("       - N โ‰ค 10^3: O(Nยฒ) DP, ๋ธŒ๋ฃจํŠธํฌ์Šค\n");
441    printf("       - N โ‰ค 10^5: O(N log N) ์ •๋ ฌ, ์ด๋ถ„ํƒ์ƒ‰\n");
442    printf("       - N โ‰ค 10^7: O(N) ํˆฌ ํฌ์ธํ„ฐ, ํ•ด์‹œ\n");
443    printf("    4. ๊ตฌํ˜„ ๋ฐ ํ…Œ์ŠคํŠธ\n");
444    printf("    5. ์—ฃ์ง€ ์ผ€์ด์Šค ํ™•์ธ\n");
445
446    printf("\n============================================================\n");
447
448    return 0;
449}