18_dp.cpp

Download
cpp 497 lines 14.2 KB 
  1/*
  2 * ๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ (Dynamic Programming)
  3 * Fibonacci, Knapsack, LCS, LIS, Edit Distance, Matrix Chain
  4 *
  5 * ๋ณต์žกํ•œ ๋ฌธ์ œ๋ฅผ ๋ถ€๋ถ„ ๋ฌธ์ œ๋กœ ๋‚˜๋ˆ„์–ด ํ•ด๊ฒฐํ•ฉ๋‹ˆ๋‹ค.
  6 */
  7
  8#include <iostream>
  9#include <vector>
 10#include <string>
 11#include <algorithm>
 12#include <climits>
 13
 14using namespace std;
 15
 16// =============================================================================
 17// 1. ํ”ผ๋ณด๋‚˜์น˜ (Top-down, Bottom-up)
 18// =============================================================================
 19
 20// Top-down (Memoization)
 21vector<long long> memo;
 22
 23long long fibTopDown(int n) {
 24    if (n <= 1) return n;
 25    if (memo[n] != -1) return memo[n];
 26    return memo[n] = fibTopDown(n - 1) + fibTopDown(n - 2);
 27}
 28
 29// Bottom-up (Tabulation)
 30long long fibBottomUp(int n) {
 31    if (n <= 1) return n;
 32
 33    vector<long long> dp(n + 1);
 34    dp[0] = 0;
 35    dp[1] = 1;
 36
 37    for (int i = 2; i <= n; i++) {
 38        dp[i] = dp[i - 1] + dp[i - 2];
 39    }
 40
 41    return dp[n];
 42}
 43
 44// ๊ณต๊ฐ„ ์ตœ์ ํ™”
 45long long fibOptimized(int n) {
 46    if (n <= 1) return n;
 47
 48    long long prev2 = 0, prev1 = 1;
 49    for (int i = 2; i <= n; i++) {
 50        long long curr = prev1 + prev2;
 51        prev2 = prev1;
 52        prev1 = curr;
 53    }
 54
 55    return prev1;
 56}
 57
 58// =============================================================================
 59// 2. 0/1 ๋ฐฐ๋‚ญ ๋ฌธ์ œ
 60// =============================================================================
 61
 62int knapsack01(int W, const vector<int>& weights, const vector<int>& values) {
 63    int n = weights.size();
 64    vector<vector<int>> dp(n + 1, vector<int>(W + 1, 0));
 65
 66    for (int i = 1; i <= n; i++) {
 67        for (int w = 0; w <= W; w++) {
 68            dp[i][w] = dp[i-1][w];  // ์•ˆ ๋‹ด์Œ
 69            if (weights[i-1] <= w) {
 70                dp[i][w] = max(dp[i][w], dp[i-1][w - weights[i-1]] + values[i-1]);
 71            }
 72        }
 73    }
 74
 75    return dp[n][W];
 76}
 77
 78// ๊ณต๊ฐ„ ์ตœ์ ํ™”
 79int knapsack01Optimized(int W, const vector<int>& weights, const vector<int>& values) {
 80    int n = weights.size();
 81    vector<int> dp(W + 1, 0);
 82
 83    for (int i = 0; i < n; i++) {
 84        for (int w = W; w >= weights[i]; w--) {
 85            dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
 86        }
 87    }
 88
 89    return dp[W];
 90}
 91
 92// ๋ฌดํ•œ ๋ฐฐ๋‚ญ (Unbounded)
 93int unboundedKnapsack(int W, const vector<int>& weights, const vector<int>& values) {
 94    int n = weights.size();
 95    vector<int> dp(W + 1, 0);
 96
 97    for (int w = 1; w <= W; w++) {
 98        for (int i = 0; i < n; i++) {
 99            if (weights[i] <= w) {
100                dp[w] = max(dp[w], dp[w - weights[i]] + values[i]);
101            }
102        }
103    }
104
105    return dp[W];
106}
107
108// =============================================================================
109// 3. ์ตœ์žฅ ๊ณตํ†ต ๋ถ€๋ถ„์ˆ˜์—ด (LCS)
110// =============================================================================
111
112int lcs(const string& s1, const string& s2) {
113    int m = s1.length(), n = s2.length();
114    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
115
116    for (int i = 1; i <= m; i++) {
117        for (int j = 1; j <= n; j++) {
118            if (s1[i-1] == s2[j-1]) {
119                dp[i][j] = dp[i-1][j-1] + 1;
120            } else {
121                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
122            }
123        }
124    }
125
126    return dp[m][n];
127}
128
129// LCS ๋ฌธ์ž์—ด ๋ณต์›
130string lcsString(const string& s1, const string& s2) {
131    int m = s1.length(), n = s2.length();
132    vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));
133
134    for (int i = 1; i <= m; i++) {
135        for (int j = 1; j <= n; j++) {
136            if (s1[i-1] == s2[j-1]) {
137                dp[i][j] = dp[i-1][j-1] + 1;
138            } else {
139                dp[i][j] = max(dp[i-1][j], dp[i][j-1]);
140            }
141        }
142    }
143
144    // ์—ญ์ถ”์ 
145    string result;
146    int i = m, j = n;
147    while (i > 0 && j > 0) {
148        if (s1[i-1] == s2[j-1]) {
149            result = s1[i-1] + result;
150            i--; j--;
151        } else if (dp[i-1][j] > dp[i][j-1]) {
152            i--;
153        } else {
154            j--;
155        }
156    }
157
158    return result;
159}
160
161// =============================================================================
162// 4. ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„์ˆ˜์—ด (LIS)
163// =============================================================================
164
165// O(nยฒ)
166int lisQuadratic(const vector<int>& arr) {
167    int n = arr.size();
168    vector<int> dp(n, 1);
169
170    for (int i = 1; i < n; i++) {
171        for (int j = 0; j < i; j++) {
172            if (arr[j] < arr[i]) {
173                dp[i] = max(dp[i], dp[j] + 1);
174            }
175        }
176    }
177
178    return *max_element(dp.begin(), dp.end());
179}
180
181// O(n log n)
182int lisNLogN(const vector<int>& arr) {
183    vector<int> tails;
184
185    for (int x : arr) {
186        auto it = lower_bound(tails.begin(), tails.end(), x);
187        if (it == tails.end()) {
188            tails.push_back(x);
189        } else {
190            *it = x;
191        }
192    }
193
194    return tails.size();
195}
196
197// LIS ์ˆ˜์—ด ๋ณต์›
198vector<int> lisWithSequence(const vector<int>& arr) {
199    int n = arr.size();
200    vector<int> tails;
201    vector<int> tailIdx;
202    vector<int> prev(n, -1);
203
204    for (int i = 0; i < n; i++) {
205        auto it = lower_bound(tails.begin(), tails.end(), arr[i]);
206        int pos = it - tails.begin();
207
208        if (it == tails.end()) {
209            tails.push_back(arr[i]);
210            tailIdx.push_back(i);
211        } else {
212            *it = arr[i];
213            tailIdx[pos] = i;
214        }
215
216        if (pos > 0) {
217            prev[i] = tailIdx[pos - 1];
218        }
219    }
220
221    // ์—ญ์ถ”์ 
222    vector<int> result;
223    for (int i = tailIdx.back(); i != -1; i = prev[i]) {
224        result.push_back(arr[i]);
225    }
226    reverse(result.begin(), result.end());
227
228    return result;
229}
230
231// =============================================================================
232// 5. ํŽธ์ง‘ ๊ฑฐ๋ฆฌ (Edit Distance)
233// =============================================================================
234
235int editDistance(const string& s1, const string& s2) {
236    int m = s1.length(), n = s2.length();
237    vector<vector<int>> dp(m + 1, vector<int>(n + 1));
238
239    for (int i = 0; i <= m; i++) dp[i][0] = i;
240    for (int j = 0; j <= n; j++) dp[0][j] = j;
241
242    for (int i = 1; i <= m; i++) {
243        for (int j = 1; j <= n; j++) {
244            if (s1[i-1] == s2[j-1]) {
245                dp[i][j] = dp[i-1][j-1];
246            } else {
247                dp[i][j] = 1 + min({dp[i-1][j],      // ์‚ญ์ œ
248                                    dp[i][j-1],      // ์‚ฝ์ž…
249                                    dp[i-1][j-1]});  // ๊ต์ฒด
250            }
251        }
252    }
253
254    return dp[m][n];
255}
256
257// =============================================================================
258// 6. ํ–‰๋ ฌ ์ฒด์ธ ๊ณฑ์…ˆ
259// =============================================================================
260
261int matrixChainMultiplication(const vector<int>& dims) {
262    int n = dims.size() - 1;
263    vector<vector<int>> dp(n, vector<int>(n, 0));
264
265    for (int len = 2; len <= n; len++) {
266        for (int i = 0; i + len - 1 < n; i++) {
267            int j = i + len - 1;
268            dp[i][j] = INT_MAX;
269
270            for (int k = i; k < j; k++) {
271                int cost = dp[i][k] + dp[k+1][j] +
272                           dims[i] * dims[k+1] * dims[j+1];
273                dp[i][j] = min(dp[i][j], cost);
274            }
275        }
276    }
277
278    return dp[0][n-1];
279}
280
281// =============================================================================
282// 7. ๋™์ „ ๊ตํ™˜ (Coin Change)
283// =============================================================================
284
285// ์ตœ์†Œ ๋™์ „ ๊ฐœ์ˆ˜
286int coinChange(const vector<int>& coins, int amount) {
287    vector<int> dp(amount + 1, INT_MAX);
288    dp[0] = 0;
289
290    for (int i = 1; i <= amount; i++) {
291        for (int coin : coins) {
292            if (coin <= i && dp[i - coin] != INT_MAX) {
293                dp[i] = min(dp[i], dp[i - coin] + 1);
294            }
295        }
296    }
297
298    return dp[amount] == INT_MAX ? -1 : dp[amount];
299}
300
301// ๊ฒฝ์šฐ์˜ ์ˆ˜
302int coinChangeWays(const vector<int>& coins, int amount) {
303    vector<int> dp(amount + 1, 0);
304    dp[0] = 1;
305
306    for (int coin : coins) {
307        for (int i = coin; i <= amount; i++) {
308            dp[i] += dp[i - coin];
309        }
310    }
311
312    return dp[amount];
313}
314
315// =============================================================================
316// 8. ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ (Kadane's Algorithm)
317// =============================================================================
318
319int maxSubarraySum(const vector<int>& arr) {
320    int maxSum = arr[0];
321    int currSum = arr[0];
322
323    for (int i = 1; i < (int)arr.size(); i++) {
324        currSum = max(arr[i], currSum + arr[i]);
325        maxSum = max(maxSum, currSum);
326    }
327
328    return maxSum;
329}
330
331// =============================================================================
332// 9. ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„๋ฌธ์ž์—ด
333// =============================================================================
334
335// ๊ฐ€์žฅ ๊ธด ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ€๋ถ„๋ฌธ์ž์—ด
336string longestPalindrome(const string& s) {
337    int n = s.length();
338    if (n == 0) return "";
339
340    vector<vector<bool>> dp(n, vector<bool>(n, false));
341    int start = 0, maxLen = 1;
342
343    // ๊ธธ์ด 1
344    for (int i = 0; i < n; i++) dp[i][i] = true;
345
346    // ๊ธธ์ด 2
347    for (int i = 0; i < n - 1; i++) {
348        if (s[i] == s[i+1]) {
349            dp[i][i+1] = true;
350            start = i;
351            maxLen = 2;
352        }
353    }
354
355    // ๊ธธ์ด 3 ์ด์ƒ
356    for (int len = 3; len <= n; len++) {
357        for (int i = 0; i + len - 1 < n; i++) {
358            int j = i + len - 1;
359            if (s[i] == s[j] && dp[i+1][j-1]) {
360                dp[i][j] = true;
361                start = i;
362                maxLen = len;
363            }
364        }
365    }
366
367    return s.substr(start, maxLen);
368}
369
370// ํŒฐ๋ฆฐ๋“œ๋กฌ ๋ถ„ํ•  ์ตœ์†Œ ํšŸ์ˆ˜
371int minPalindromeCuts(const string& s) {
372    int n = s.length();
373
374    // isPalin[i][j]: s[i..j]๊ฐ€ ํŒฐ๋ฆฐ๋“œ๋กฌ์ธ์ง€
375    vector<vector<bool>> isPalin(n, vector<bool>(n, false));
376    for (int i = n - 1; i >= 0; i--) {
377        for (int j = i; j < n; j++) {
378            if (i == j) {
379                isPalin[i][j] = true;
380            } else if (s[i] == s[j]) {
381                isPalin[i][j] = (j - i == 1) || isPalin[i+1][j-1];
382            }
383        }
384    }
385
386    // dp[i]: s[0..i]์˜ ์ตœ์†Œ ๋ถ„ํ•  ํšŸ์ˆ˜
387    vector<int> dp(n, 0);
388    for (int i = 0; i < n; i++) {
389        if (isPalin[0][i]) {
390            dp[i] = 0;
391        } else {
392            dp[i] = INT_MAX;
393            for (int j = 0; j < i; j++) {
394                if (isPalin[j+1][i]) {
395                    dp[i] = min(dp[i], dp[j] + 1);
396                }
397            }
398        }
399    }
400
401    return dp[n-1];
402}
403
404// =============================================================================
405// ํ…Œ์ŠคํŠธ
406// =============================================================================
407
408void printVector(const vector<int>& v) {
409    cout << "[";
410    for (size_t i = 0; i < v.size(); i++) {
411        cout << v[i];
412        if (i < v.size() - 1) cout << ", ";
413    }
414    cout << "]";
415}
416
417int main() {
418    cout << "============================================================" << endl;
419    cout << "๋™์  ํ”„๋กœ๊ทธ๋ž˜๋ฐ ์˜ˆ์ œ" << endl;
420    cout << "============================================================" << endl;
421
422    // 1. ํ”ผ๋ณด๋‚˜์น˜
423    cout << "\n[1] ํ”ผ๋ณด๋‚˜์น˜" << endl;
424    memo.assign(50, -1);
425    cout << "    fib(10) Top-down: " << fibTopDown(10) << endl;
426    cout << "    fib(10) Bottom-up: " << fibBottomUp(10) << endl;
427    cout << "    fib(10) Optimized: " << fibOptimized(10) << endl;
428
429    // 2. 0/1 ๋ฐฐ๋‚ญ
430    cout << "\n[2] 0/1 ๋ฐฐ๋‚ญ" << endl;
431    vector<int> weights = {2, 3, 4, 5};
432    vector<int> values = {3, 4, 5, 6};
433    int W = 8;
434    cout << "    ๋ฌด๊ฒŒ: [2,3,4,5], ๊ฐ€์น˜: [3,4,5,6], ์šฉ๋Ÿ‰: 8" << endl;
435    cout << "    ์ตœ๋Œ€ ๊ฐ€์น˜: " << knapsack01(W, weights, values) << endl;
436
437    // 3. LCS
438    cout << "\n[3] ์ตœ์žฅ ๊ณตํ†ต ๋ถ€๋ถ„์ˆ˜์—ด (LCS)" << endl;
439    string s1 = "ABCDGH", s2 = "AEDFHR";
440    cout << "    s1: \"ABCDGH\", s2: \"AEDFHR\"" << endl;
441    cout << "    LCS ๊ธธ์ด: " << lcs(s1, s2) << endl;
442    cout << "    LCS: \"" << lcsString(s1, s2) << "\"" << endl;
443
444    // 4. LIS
445    cout << "\n[4] ์ตœ์žฅ ์ฆ๊ฐ€ ๋ถ€๋ถ„์ˆ˜์—ด (LIS)" << endl;
446    vector<int> arr = {10, 9, 2, 5, 3, 7, 101, 18};
447    cout << "    ๋ฐฐ์—ด: [10,9,2,5,3,7,101,18]" << endl;
448    cout << "    LIS ๊ธธ์ด O(nยฒ): " << lisQuadratic(arr) << endl;
449    cout << "    LIS ๊ธธ์ด O(n log n): " << lisNLogN(arr) << endl;
450    cout << "    LIS: ";
451    printVector(lisWithSequence(arr));
452    cout << endl;
453
454    // 5. ํŽธ์ง‘ ๊ฑฐ๋ฆฌ
455    cout << "\n[5] ํŽธ์ง‘ ๊ฑฐ๋ฆฌ" << endl;
456    cout << "    \"horse\" โ†’ \"ros\": " << editDistance("horse", "ros") << endl;
457
458    // 6. ํ–‰๋ ฌ ์ฒด์ธ ๊ณฑ์…ˆ
459    cout << "\n[6] ํ–‰๋ ฌ ์ฒด์ธ ๊ณฑ์…ˆ" << endl;
460    vector<int> dims = {10, 30, 5, 60};
461    cout << "    ํ–‰๋ ฌ ํฌ๊ธฐ: 10ร—30, 30ร—5, 5ร—60" << endl;
462    cout << "    ์ตœ์†Œ ๊ณฑ์…ˆ ํšŸ์ˆ˜: " << matrixChainMultiplication(dims) << endl;
463
464    // 7. ๋™์ „ ๊ตํ™˜
465    cout << "\n[7] ๋™์ „ ๊ตํ™˜" << endl;
466    vector<int> coins = {1, 2, 5};
467    cout << "    ๋™์ „: [1,2,5], ๊ธˆ์•ก: 11" << endl;
468    cout << "    ์ตœ์†Œ ๊ฐœ์ˆ˜: " << coinChange(coins, 11) << endl;
469    cout << "    ๊ฒฝ์šฐ์˜ ์ˆ˜: " << coinChangeWays(coins, 11) << endl;
470
471    // 8. ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ
472    cout << "\n[8] ์ตœ๋Œ€ ๋ถ€๋ถ„ ๋ฐฐ์—ด ํ•ฉ" << endl;
473    vector<int> subArr = {-2, 1, -3, 4, -1, 2, 1, -5, 4};
474    cout << "    ๋ฐฐ์—ด: [-2,1,-3,4,-1,2,1,-5,4]" << endl;
475    cout << "    ์ตœ๋Œ€ ํ•ฉ: " << maxSubarraySum(subArr) << endl;
476
477    // 9. ํŒฐ๋ฆฐ๋“œ๋กฌ
478    cout << "\n[9] ํŒฐ๋ฆฐ๋“œ๋กฌ" << endl;
479    cout << "    \"babad\" ๊ฐ€์žฅ ๊ธด ํŒฐ๋ฆฐ๋“œ๋กฌ: \"" << longestPalindrome("babad") << "\"" << endl;
480    cout << "    \"aab\" ์ตœ์†Œ ๋ถ„ํ• : " << minPalindromeCuts("aab") << endl;
481
482    // 10. ๋ณต์žก๋„ ์š”์•ฝ
483    cout << "\n[10] ๋ณต์žก๋„ ์š”์•ฝ" << endl;
484    cout << "    | ๋ฌธ์ œ              | ์‹œ๊ฐ„๋ณต์žก๋„    | ๊ณต๊ฐ„๋ณต์žก๋„ |" << endl;
485    cout << "    |-------------------|---------------|------------|" << endl;
486    cout << "    | ํ”ผ๋ณด๋‚˜์น˜          | O(n)          | O(1)       |" << endl;
487    cout << "    | 0/1 ๋ฐฐ๋‚ญ          | O(nW)         | O(W)       |" << endl;
488    cout << "    | LCS               | O(mn)         | O(mn)      |" << endl;
489    cout << "    | LIS               | O(n log n)    | O(n)       |" << endl;
490    cout << "    | ํŽธ์ง‘ ๊ฑฐ๋ฆฌ         | O(mn)         | O(n)       |" << endl;
491    cout << "    | ํ–‰๋ ฌ ์ฒด์ธ         | O(nยณ)         | O(nยฒ)      |" << endl;
492
493    cout << "\n============================================================" << endl;
494
495    return 0;
496}