18_dp.c

Download
c 298 lines 9.0 KB 
  1/*
  2 * ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ (Dynamic Programming)
  3 * Fibonacci, Knapsack, LCS, LIS, Edit Distance
  4 *
  5 * ๋ถ€๋ถ„ ๋ฌธ์ œ์˜ ์ตœ์  ํ•ด๋ฅผ ์ด์šฉํ•œ ๋ฌธ์ œ ํ•ด๊ฒฐ ๊ธฐ๋ฒ•์ž…๋‹ˆ๋‹ค.
  6 */
  7
  8#include <stdio.h>
  9#include <stdlib.h>
 10#include <string.h>
 11
 12#define MAX(a, b) ((a) > (b) ? (a) : (b))
 13#define MIN(a, b) ((a) < (b) ? (a) : (b))
 14
 15/* =============================================================================
 16 * 1. ํ”ผ๋ณด๋‚˜์น˜ (Memoization & Tabulation)
 17 * ============================================================================= */
 18
 19long long fib_memo[100];
 20int fib_computed[100];
 21
 22long long fibonacci_memo(int n) {
 23    if (n <= 1) return n;
 24    if (fib_computed[n]) return fib_memo[n];
 25    fib_computed[n] = 1;
 26    fib_memo[n] = fibonacci_memo(n - 1) + fibonacci_memo(n - 2);
 27    return fib_memo[n];
 28}
 29
 30long long fibonacci_tab(int n) {
 31    if (n <= 1) return n;
 32    long long* dp = malloc((n + 1) * sizeof(long long));
 33    dp[0] = 0; dp[1] = 1;
 34    for (int i = 2; i <= n; i++)
 35        dp[i] = dp[i - 1] + dp[i - 2];
 36    long long result = dp[n];
 37    free(dp);
 38    return result;
 39}
 40
 41/* =============================================================================
 42 * 2. 0/1 ๋ฐฐ๋‚ญ ๋ฌธ์ œ
 43 * ============================================================================= */
 44
 45int knapsack_01(int W, int weights[], int values[], int n) {
 46    int** dp = malloc((n + 1) * sizeof(int*));
 47    for (int i = 0; i <= n; i++)
 48        dp[i] = calloc(W + 1, sizeof(int));
 49
 50    for (int i = 1; i <= n; i++) {
 51        for (int w = 0; w <= W; w++) {
 52            dp[i][w] = dp[i - 1][w];
 53            if (weights[i - 1] <= w) {
 54                int take = dp[i - 1][w - weights[i - 1]] + values[i - 1];
 55                dp[i][w] = MAX(dp[i][w], take);
 56            }
 57        }
 58    }
 59
 60    int result = dp[n][W];
 61    for (int i = 0; i <= n; i++) free(dp[i]);
 62    free(dp);
 63    return result;
 64}
 65
 66/* ๊ณต๊ฐ„ ์ตœ์ ํ™” */
 67int knapsack_01_optimized(int W, int weights[], int values[], int n) {
 68    int* dp = calloc(W + 1, sizeof(int));
 69
 70    for (int i = 0; i < n; i++) {
 71        for (int w = W; w >= weights[i]; w--) {
 72            dp[w] = MAX(dp[w], dp[w - weights[i]] + values[i]);
 73        }
 74    }
 75
 76    int result = dp[W];
 77    free(dp);
 78    return result;
 79}
 80
 81/* =============================================================================
 82 * 3. ์ตœ์žฅ ๊ณตํ†ต ๋ถ€๋ถ„ ์ˆ˜์—ด (LCS)
 83 * ============================================================================= */
 84
 85int lcs(const char* s1, const char* s2) {
 86    int m = strlen(s1);
 87    int n = strlen(s2);
 88
 89    int** dp = malloc((m + 1) * sizeof(int*));
 90    for (int i = 0; i <= m; i++)
 91        dp[i] = calloc(n + 1, sizeof(int));
 92
 93    for (int i = 1; i <= m; i++) {
 94        for (int j = 1; j <= n; j++) {
 95            if (s1[i - 1] == s2[j - 1])
 96                dp[i][j] = dp[i - 1][j - 1] + 1;
 97            else
 98                dp[i][j] = MAX(dp[i - 1][j], dp[i][j - 1]);
 99        }
100    }
101
102    int result = dp[m][n];
103    for (int i = 0; i <= m; i++) free(dp[i]);
104    free(dp);
105    return result;
106}
107
108/* =============================================================================
109 * 4. ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด (LIS)
110 * ============================================================================= */
111
112/* O(nยฒ) */
113int lis_n2(int arr[], int n) {
114    int* dp = malloc(n * sizeof(int));
115    for (int i = 0; i < n; i++) dp[i] = 1;
116
117    int max_len = 1;
118    for (int i = 1; i < n; i++) {
119        for (int j = 0; j < i; j++) {
120            if (arr[j] < arr[i] && dp[j] + 1 > dp[i])
121                dp[i] = dp[j] + 1;
122        }
123        if (dp[i] > max_len) max_len = dp[i];
124    }
125
126    free(dp);
127    return max_len;
128}
129
130/* O(n log n) */
131int lower_bound(int arr[], int n, int val) {
132    int lo = 0, hi = n;
133    while (lo < hi) {
134        int mid = (lo + hi) / 2;
135        if (arr[mid] < val) lo = mid + 1;
136        else hi = mid;
137    }
138    return lo;
139}
140
141int lis_nlogn(int arr[], int n) {
142    int* tails = malloc(n * sizeof(int));
143    int len = 0;
144
145    for (int i = 0; i < n; i++) {
146        int pos = lower_bound(tails, len, arr[i]);
147        tails[pos] = arr[i];
148        if (pos == len) len++;
149    }
150
151    free(tails);
152    return len;
153}
154
155/* =============================================================================
156 * 5. ํŽธ์ง‘ ๊ฑฐ๋ฆฌ
157 * ============================================================================= */
158
159int edit_distance(const char* s1, const char* s2) {
160    int m = strlen(s1);
161    int n = strlen(s2);
162
163    int** dp = malloc((m + 1) * sizeof(int*));
164    for (int i = 0; i <= m; i++)
165        dp[i] = malloc((n + 1) * sizeof(int));
166
167    for (int i = 0; i <= m; i++) dp[i][0] = i;
168    for (int j = 0; j <= n; j++) dp[0][j] = j;
169
170    for (int i = 1; i <= m; i++) {
171        for (int j = 1; j <= n; j++) {
172            if (s1[i - 1] == s2[j - 1]) {
173                dp[i][j] = dp[i - 1][j - 1];
174            } else {
175                dp[i][j] = 1 + MIN(dp[i - 1][j - 1],
176                                   MIN(dp[i - 1][j], dp[i][j - 1]));
177            }
178        }
179    }
180
181    int result = dp[m][n];
182    for (int i = 0; i <= m; i++) free(dp[i]);
183    free(dp);
184    return result;
185}
186
187/* =============================================================================
188 * 6. ๋™์ „ ๊ตํ™˜
189 * ============================================================================= */
190
191int coin_change(int coins[], int n, int amount) {
192    int* dp = malloc((amount + 1) * sizeof(int));
193    for (int i = 0; i <= amount; i++) dp[i] = amount + 1;
194    dp[0] = 0;
195
196    for (int i = 1; i <= amount; i++) {
197        for (int j = 0; j < n; j++) {
198            if (coins[j] <= i && dp[i - coins[j]] + 1 < dp[i]) {
199                dp[i] = dp[i - coins[j]] + 1;
200            }
201        }
202    }
203
204    int result = (dp[amount] > amount) ? -1 : dp[amount];
205    free(dp);
206    return result;
207}
208
209/* =============================================================================
210 * 7. ํ–‰๋ ฌ ์ฒด์ธ ๊ณฑ์…ˆ
211 * ============================================================================= */
212
213int matrix_chain(int dims[], int n) {
214    int** dp = malloc(n * sizeof(int*));
215    for (int i = 0; i < n; i++) {
216        dp[i] = calloc(n, sizeof(int));
217    }
218
219    for (int len = 2; len < n; len++) {
220        for (int i = 1; i < n - len + 1; i++) {
221            int j = i + len - 1;
222            dp[i][j] = 2147483647;
223            for (int k = i; k < j; k++) {
224                int cost = dp[i][k] + dp[k + 1][j] + dims[i - 1] * dims[k] * dims[j];
225                if (cost < dp[i][j]) dp[i][j] = cost;
226            }
227        }
228    }
229
230    int result = dp[1][n - 1];
231    for (int i = 0; i < n; i++) free(dp[i]);
232    free(dp);
233    return result;
234}
235
236/* =============================================================================
237 * ํ…Œ์ŠคํŠธ
238 * ============================================================================= */
239
240int main(void) {
241    printf("============================================================\n");
242    printf("๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ (DP) ์˜ˆ์ œ\n");
243    printf("============================================================\n");
244
245    /* 1. ํ”ผ๋ณด๋‚˜์น˜ */
246    printf("\n[1] ํ”ผ๋ณด๋‚˜์น˜\n");
247    printf("    fib(10) = %lld\n", fibonacci_tab(10));
248    printf("    fib(45) = %lld\n", fibonacci_tab(45));
249
250    /* 2. 0/1 ๋ฐฐ๋‚ญ */
251    printf("\n[2] 0/1 ๋ฐฐ๋‚ญ ๋ฌธ์ œ\n");
252    int weights[] = {1, 2, 3, 4, 5};
253    int values[] = {1, 6, 10, 16, 20};
254    printf("    ๋ฌด๊ฒŒ: [1,2,3,4,5], ๊ฐ€์น˜: [1,6,10,16,20]\n");
255    printf("    ์šฉ๋Ÿ‰ 8์˜ ์ตœ๋Œ€ ๊ฐ€์น˜: %d\n", knapsack_01(8, weights, values, 5));
256
257    /* 3. LCS */
258    printf("\n[3] ์ตœ์žฅ ๊ณตํ†ต ๋ถ€๋ถ„ ์ˆ˜์—ด (LCS)\n");
259    printf("    'ABCDGH' vs 'AEDFHR': %d\n", lcs("ABCDGH", "AEDFHR"));
260    printf("    'AGGTAB' vs 'GXTXAYB': %d\n", lcs("AGGTAB", "GXTXAYB"));
261
262    /* 4. LIS */
263    printf("\n[4] ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„ ์ˆ˜์—ด (LIS)\n");
264    int arr[] = {10, 22, 9, 33, 21, 50, 41, 60, 80};
265    printf("    [10,22,9,33,21,50,41,60,80]\n");
266    printf("    O(nยฒ): %d\n", lis_n2(arr, 9));
267    printf("    O(n log n): %d\n", lis_nlogn(arr, 9));
268
269    /* 5. ํŽธ์ง‘ ๊ฑฐ๋ฆฌ */
270    printf("\n[5] ํŽธ์ง‘ ๊ฑฐ๋ฆฌ\n");
271    printf("    'kitten' โ†’ 'sitting': %d\n", edit_distance("kitten", "sitting"));
272    printf("    'sunday' โ†’ 'saturday': %d\n", edit_distance("sunday", "saturday"));
273
274    /* 6. ๋™์ „ ๊ตํ™˜ */
275    printf("\n[6] ๋™์ „ ๊ตํ™˜\n");
276    int coins[] = {1, 5, 10, 25};
277    printf("    ๋™์ „: [1,5,10,25], ๊ธˆ์•ก 30\n");
278    printf("    ์ตœ์†Œ ๋™์ „ ์ˆ˜: %d\n", coin_change(coins, 4, 30));
279
280    /* 7. ํ–‰๋ ฌ ์ฒด์ธ */
281    printf("\n[7] ํ–‰๋ ฌ ์ฒด์ธ ๊ณฑ์…ˆ\n");
282    int dims[] = {10, 30, 5, 60};
283    printf("    ์ฐจ์›: 10x30, 30x5, 5x60\n");
284    printf("    ์ตœ์†Œ ๊ณฑ์…ˆ ํšŸ์ˆ˜: %d\n", matrix_chain(dims, 4));
285
286    /* 8. DP ๋ฌธ์ œ ๋ถ„๋ฅ˜ */
287    printf("\n[8] DP ๋ฌธ์ œ ์œ ํ˜•\n");
288    printf("    | ์œ ํ˜•          | ์˜ˆ์‹œ                    | ๋ณต์žก๋„      |\n");
289    printf("    |---------------|-------------------------|-------------|\n");
290    printf("    | 1์ฐจ์› DP      | ํ”ผ๋ณด๋‚˜์น˜, ๊ณ„๋‹จ ์˜ค๋ฅด๊ธฐ   | O(n)        |\n");
291    printf("    | 2์ฐจ์› DP      | ๋ฐฐ๋‚ญ, LCS, ํŽธ์ง‘๊ฑฐ๋ฆฌ     | O(nยฒ) or O(nm)|\n");
292    printf("    | ๊ตฌ๊ฐ„ DP       | ํ–‰๋ ฌ ์ฒด์ธ, ํŒฐ๋ฆฐ๋“œ๋กฌ     | O(nยณ)       |\n");
293
294    printf("\n============================================================\n");
295
296    return 0;
297}