Dynamic Programming(DP 다이나믹 프로그래밍 알고리즘)

fib(5) / \ fib(4) fib(3) ← fib(3)이 여기서 1번 / \ / \ fib(3) fib(2) fib(2) fib(1) / \ ↑ ↑ fib(2) fib(1) | | └───────┴─── 중복 계산 발생! fib(3)은 2번, fib(2)는 3번 계산됩니다. 큰 숫자일수록 중복은 기하급수적으로 증가합니다!

예시: fib(5)를 계산할 때 fib(3), fib(2)가 여러 번 등장 → 한 번만 계산하고 저장하면, 나머지는 그냥 꺼내 쓰면 됨!

예시: "15원 거스름돈의 최소 동전 개수" = min( "14원의 최소 개수 + 1원 동전 1개", "10원의 최소 개수 + 5원 동전 1개", ... ) → 작은 문제(14원, 10원)의 최적해를 알면, 큰 문제(15원)도 풀 수 있음!

// Top-down (재귀 + 메모) int memo[100]; int fib_memo(int n) { if (n <= 1) return n; if (memo[n] != 0) return memo[n]; // 이미 계산했으면 바로 리턴! return memo[n] = fib_memo(n-1) + fib_memo(n-2); } // Bottom-up (반복문 + 테이블) int fib_dp(int n) { vector<int> dp(n+1); dp[0] = 0; dp[1] = 1; for (int i = 2; i <= n; i++) dp[i] = dp[i-1] + dp[i-2]; // 작은 것부터 차례로 계산 return dp[n]; }

재귀 (중복 계산): - fib(5): 15번의 함수 호출 - fib(10): 177번의 함수 호출 - fib(40): 약 20억 번의 함수 호출! 💀 → 시간복잡도: O(2^n) - 지수 시간 DP (중복 제거): - fib(5): 5번의 계산 (각 숫자당 1번) - fib(10): 10번의 계산 - fib(40): 40번의 계산 → 시간복잡도: O(n) - 선형 시간 결론: 중복 계산을 제거하면 지수 → 선형으로 극적 개선!

위 문제를 해결하기 위한 대표적인 알고리즘 세가지를 고려해 볼 수 있다. 1. 모든 경우의 수를 다 해볼것인가? 브루트포스(DFS,BFS)

2. 최적의 해를 향상 그리기에 찾는다. 그리디 알고리즘 과거 선택에대한 고려가 전혀 없어 미래를 선택하는 부분도 전혀 고려를 하지 않고 현재의 한때 선택한다. 3. DP 이전단계에서 구했던 최적의 값과, 현재상황에서 구한 값을 비교하여 더 최적의 값을 찾는 알고리즘이다.

// factorial dp, 재귀함수 비교 예시 #include <iostream> #include <vector> int factorial(int n) { if (n <= 1) return 1; //int result = n * factorial(n - 1); //return result; return n * factorial(n - 1); } int factorial_dp(int n) { if (n < 0) return -1; std::vector<int> dp(n + 1); dp[0] = 1; for (size_t i = 1; i < n + 1; i++) dp[i] = dp[i - 1] * i; return dp[n]; } int main() { int fact = factorial(5); fact = factorial_dp(5); return 0; }

화폐단위: 500원, 100원, 50원, 10원 손님이 받을 개수: 2개, 2개, 1개, 1개 1260원을 만드는 경우 이것 또한 그리디 알고리즘의 하나로 볼 수 있다.

vector<int> dp(amount + 1, 0); // 모두 0으로 초기화 dp[0] = 1; // 0원은 1가지 방법 (기저 조건)

3원의 동전만 가지고 15원의 거스름을 만드는 경우의수를 테이블로 만들어보자 단계별 계산 과정: dp[0] = 1 (초기값) dp[3] = dp[3-3] = dp[0] = 1 (3원 1개) dp[6] = dp[6-3] = dp[3] = 1 (3원 2개) dp[9] = dp[9-3] = dp[6] = 1 (3원 3개) dp[12] = dp[12-3] = dp[9] = 1 (3원 4개) dp[15] = dp[15-3] = dp[12] = 1 (3원 5개) 나머지는 모두 0 (3원으로 만들 수 없음) | 금액 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 3원 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | ↑ ↑ ↑ ↑ ↑ 초기값 3원×1개 3원×2개 3원×3개 3원×5개

4원 동전 추가 후 변화: dp[4] = dp[4] + dp[4-4] = 0 + dp[0] = 0 + 1 = 1 ↑ ↑ 기존값 4원 1개 사용 dp[7] = dp[7] + dp[7-4] = 0 + dp[3] = 0 + 1 = 1 ↑ ↑ 기존값 "3원 1개" + "4원 1개" dp[8] = dp[8] + dp[8-4] = 0 + dp[4] = 0 + 1 = 1 ↑ "4원 2개" dp[12] = dp[12] + dp[12-4] = 1 + dp[8] = 1 + 1 = 2 ↑ ↑ 3원×4개(기존) 4원×3개(새로운) | 금액 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 3원 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | | 3,4원| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | ↑ ↑ 4원 추가 3원×4 + 4원×3 2가지 방법!

1차원 배열 기반 dp[i] += dp[i - coin] ↑ ↑ | └─ 현재 동전을 1개 사용한 후 남은 금액을 만드는 경우의 수 └────────── 기존 경우의 수에 "추가" 2차원 배열 기반 dp[i][j] = dp[i - 1][j] + dp[i][j - coin];

예시: 7원을 만드는 경우 1단계 (3원 동전만): dp[7] = 0 (3원으로는 7원을 만들 수 없음) 2단계 (4원 동전 추가): dp[7] = dp[7] + dp[7-4] = 0 + dp[3] = 0 + 1 = 1 ↑ ↑ 기존값 새로운 방법 (3원 1개 + 4원 1개) 만약 '='를 사용했다면: dp[7] = dp[3] = 1 (기존 값 0이 사라짐, 하지만 여기선 기존값이 0이라 상관없음) 더 명확한 예시 - 12원: 3원만: dp[12] = 1 (3원×4개) 4원 추가: dp[12] += dp[8] = 1 + 1 = 2 ↑ ↑ 기존 새로운 '='를 썼다면 기존 방법(3원×4개)이 사라집니다!

질문: "15원을 만드는 경우의 수는?" 생각의 흐름: 1. 5원 동전을 "사용 안함" → dp[15] (5원 추가 전 값) 2. 5원 동전을 "1개 사용" → 남은 10원을 만드는 경우의 수 = dp[10] 3. 5원 동전을 "2개 사용" → 남은 5원을 만드는 경우의 수 = dp[5] 4. 5원 동전을 "3개 사용" → 남은 0원을 만드는 경우의 수 = dp[0] 핵심 통찰: "5원을 1개 이상 사용하는 모든 경우" = dp[10] (1개 사용 후 남은 금액) 왜냐하면: - 5원을 정확히 1개 쓰는 경우는 dp[10]에 5원 동전이 없는 조합들 - 5원을 2개 이상 쓰는 경우는 dp[10]에 5원 동전이 포함된 조합들 - dp[10]을 계산할 때 이미 "5원을 또 쓸 수 있는지" 고려했기 때문! 따라서: dp[15] = dp[15](5원 안씀) + dp[10](5원 1개 이상 씀)

// 동전별로 순차 처리 (올바른 방법) for (int coin : coins) // 각 동전에 대해 for (int i = coin; i <= amount; i++) // 모든 금액 업데이트 dp[i] += dp[i - coin]; // 만약 순서를 바꾸면? for (int i = 0; i <= amount; i++) // 각 금액에 대해 for (int coin : coins) // 모든 동전 시도 dp[i] += dp[i - coin]; // 문제: (3원, 4원)과 (4원, 3원)을 다른 경우로 중복 계산!

0+0 은 0 이기 때문에 (3,4) 조합으로 5원을 거슬러 줄 수 없다 dp[i] += dp[i - coin] // 핵심 점화식

4원 부터는 달라진다. | 금액 | 0 | 1 | 2 | 3 | 4 | |------|---|---|---|---|---| | 3원 | 1 | 0 | 0 | 1 | 0 | | 3,4원| 1 | 0 | 0 | 1 | 1 | 5원의 경우에는 3,4원으로 만들 수 있는 경우의수가 없다. 그렇다면 3,4원으로 5원을 거슬러 줄 경우에는 4원을 내주고 1원을 거슬러 줄 수 있는 경우의 조합이 있을 것이 불 수 있다. | 금액 | 0 | 1 | 2 | 3 | 4 | 5 | |------|---|---|---|---|---|---| | 3원 | 1 | 0 | 0 | 1 | 0 | 0 | | 3,4원| 1 | 0 | 0 | 1 | 1 | 0 | |3,4,5 | 1 | 0 | 0 | 1 | 1 | 1 |

#include <iostream> #include <vector> using namespace std; int main() { // 동전 집합과 목표 금액 vector<int> coins = {3, 4, 5}; int amount = 15; // DP 테이블 초기화: (동전 개수+1) x (금액+1) vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 0)); dp[0][0] = 1; // 아무 동전도 사용하지 않고 0원을 만드는 경우 1가지 // DP 채우기 for (int i = 1; i <= coins.size(); i++) // 각 동전별 { int coin = coins[i - 1]; for (int j = 0; j <= amount; j++) { if (j < coin) dp[i][j] = dp[i - 1][j]; // 해당 동전을 못 쓰는 경우 else dp[i][j] = dp[i - 1][j] + dp[i][j - coin]; // 점화식 } } // 결과 출력 cout << "DP 테이블 (행: 동전개수, 열: 금액)" << endl; for (int i = 0; i <= coins.size(); i++) { for (int j = 0; j <= amount; j++) cout << dp[i][j] << " "; cout << endl; } cout << "\n" << amount << "원을 만드는 경우의 수: " << dp[coins.size()][amount] << endl; return 0; }

#include <iostream> #include <vector> #include <algorithm> #include <climits> using namespace std; int main() { // 동전 집합과 목표 금액 vector<int> coins = {3, 4, 5}; int amount = 15; // DP 테이블 초기화 vector<int> dp(amount + 1, 0); dp[0] = 1; // 0원을 만드는 방법은 1가지 (아무것도 선택하지 않기) // 각 동전에 대해 for (int coin : coins) { // 해당 동전부터 목표 금액까지 for (int i = coin; i <= amount; i++) { dp[i] += dp[i - coin]; // 점화식 } } // 결과 출력 if (dp[amount] == 0) { cout << "해당 금액을 만들 수 없습니다." << endl; } else { cout << amount << "원을 만들기 위한 최소 동전 개수: " << dp[amount] << endl; } return 0; }

coin = 3일 때: i=3: dp[3] += dp[0] = 0 + 1 = 1 i=6: dp[6] += dp[3] = 0 + 1 = 1 i=9: dp[9] += dp[6] = 0 + 1 = 1 ...

coin = 4일 때: i=4: dp[4] += dp[0] = 0 + 1 = 1 i=7: dp[7] += dp[3] = 0 + 1 = 1 i=8: dp[8] += dp[4] = 0 + 1 = 1 ...

coin = 5일 때: i=5: dp[5] += dp[0] = 0 + 1 = 1 i=8: dp[8] += dp[3] = 1 + 1 = 2 (3+5 또는 4+4) i=10: dp[10] += dp[5] = 1 + 1 = 2 ...

결과적으로 이것들은 패턴이 보이기 시작한다. | 금액 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| 11| 12| 13| 14| 15| |------|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---| | 3원 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | | 3,4원| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 2 | 1 | 1 | 2 | 7원의 경우 (현재 동전) 추가되지전 거슬러 줄 수 있는 경우의수 0) + (4원 거슬러주고 남은 3원 거슬러 줄 수 있는 경우의수 1) = 1이 된다.

dp[i] = i원을 만들 수 있는 경우의 수

dp[0] = 1; // 0원을 만드는 방법은 1가지

dp[i] += dp[i - coin]; // 현재 동전을 사용해서 만드는 경우

dp[i][w] = max(dp[i-1][w], dp[i-1][w-weight[i]] + value[i]);

dp[i] = dp[i-1] + dp[i-2];

수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... F(10) = 55를 구해보자

int fibonacci_recursive(int n) { if (n <= 1) return n; return fibonacci_recursive(n-1) + fibonacci_recursive(n-2); } // clean code int fibonacci_recursive(int n) { if (n <= 1) return n; int n_1 = fibonacci_recursive(n - 1); int n_2 = fibonacci_recursive(n - 2); return n_1 + n_2; } 문제점: F(5)를 계산할 때의 함수 호출 트리 F(5) ────────────────┐ / \ │ F(4) F(3) ←───────┐ │ / \ / \ │ │ F(3) F(2) F(2) F(1) │ │ / \ / \ / \ │ │ F(2) F(1)F(1)F(0)F(1)F(0) │ │ / \ │ │ F(1) F(0) │ │ │ │ 중복 계산 현황: │ │ F(3): 2번 ─────────────────────────┘ │ F(2): 3번 ────────────────────────────┘ F(1): 5번 F(0): 3번 총 함수 호출: 15번! int main() { int result = fibonacci_recursive(5); return 0; }

각 함수는 2개의 자식 함수를 호출합니다 (n-1, n-2) 깊이(depth)별 함수 호출 수: 깊이 0: 1개 (F(5)) 깊이 1: 2개 (F(4), F(3)) 깊이 2: 4개 (F(3), F(2), F(2), F(1)) 깊이 3: 최대 8개 ... 깊이 n: 최대 2^n개 전체 호출 수 ≈ 2^0 + 2^1 + 2^2 + ... + 2^n ≈ 2^(n+1) - 1 따라서 시간복잡도: O(2^n) 실제 숫자로 보면: F(10): 177번 호출 F(20): 21,891번 호출 F(30): 2,692,537번 호출 F(40): 331,160,281번 호출 (약 3억 번!) 💀

int fibonacci_dp(int n) { vector<int> dp(n + 1); dp[0] = 0; // 기저조건 dp[1] = 1; // 기저조건 for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; // 점화식 } return dp[n]; } 시간복잡도: O(n) - 효율적!

F(10)을 구하는 과정: | i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10| |----|---|---|---|---|---|---|---|---|---|---|---| |dp[i]| 0 | 1 | 1 | 2 | 3 | 5 | 8 |13 |21 |34 |55 | 단계별 계산: dp[2] = dp[1] + dp[0] = 1 + 0 = 1 dp[3] = dp[2] + dp[1] = 1 + 1 = 2 dp[4] = dp[3] + dp[2] = 2 + 1 = 3 dp[5] = dp[4] + dp[3] = 3 + 2 = 5 ... dp[10] = dp[9] + dp[8] = 34 + 21 = 55

#include <iostream> #include <vector> using namespace std; int main() { int n = 10; // F(10) 구하기 // DP 테이블 초기화 vector<int> dp(n + 1); // 기저 조건 dp[0] = 0; dp[1] = 1; cout << "피보나치 수열 계산 과정:" << endl; cout << "F(0) = " << dp[0] << endl; cout << "F(1) = " << dp[1] << endl; // Bottom-up 방식으로 계산 for (int i = 2; i <= n; i++) { dp[i] = dp[i-1] + dp[i-2]; //cout << "F(" << i << ") = F(" << (i-1) << ") + F(" << (i-2) //<< ") = " << dp[i-1] << " + " << dp[i-2] << " = " << dp[i] << endl; } cout << "\n최종 결과: F(" << n << ") = " << dp[n] << endl; return 0; }

🎒 인벤토리 용량: 5칸 💎 발견한 아이템들: ┌──────────────────────────────────────────┐ │ 💍 마법반지 │ 2칸 │ 가치 3 │ 💰💰💰 │ │ ⚔️ 신검 │ 3칸 │ 가치 4 │ 💰💰💰💰 │ │ 🛡️ 용방패 │ 4칸 │ 가치 5 │ 💰💰💰💰💰 │ │ 👑 왕의왕관 │ 5칸 │ 가치 6 │ 💰💰💰💰💰💰 │ └──────────────────────────────────────────┘ ❓ 문제: 인벤토리에 담을 수 있는 최대 가치는?

dp[i][w] = i번째 아이템까지 고려했을 때, 용량 w에서 얻을 수 있는 최대 가치

1차원으로는 표현 불가능한 상황: "용량 5칸일 때 최대 가치"는 - 아이템 1개만 봤을 때: 3 - 아이템 2개 봤을 때: 7 - 아이템 3개 봤을 때: 7 → 용량이 같아도 고려한 아이템에 따라 답이 다름! 따라서 dp[아이템수][용량] 2차원 필요!

dp[i][w] = max ( dp[i-1][w], // 선택 1: 현재 아이템을 선택하지 않는 경우 dp[i-1][w-weight[i]] + value[i] // 선택 2: 현재 아이템을 선택하는 경우 )

상황: 마법반지(2칸, 가치3)와 신검(3칸, 가치4)이 있고, 현재 용량 5칸에서 신검을 고려 중 질문: "신검을 넣을까, 말까?" ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 선택 1: 신검을 넣지 않는다 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ dp[2][5] = dp[1][5] // 이전 아이템까지의 최선 = 3 // 마법반지만 넣은 상태 유지 🎒 [💍 반지(2칸)] [빈공간 3칸] → 가치 3 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 선택 2: 신검을 넣는다 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ dp[2][5] = dp[1][5-3] + 4 // 신검(3칸) 넣으면 남은 2칸에서 최선 + 신검 가치 = dp[1][2] + 4 = 3 + 4 = 7 ↑ "용량 2칸일 때 마법반지까지 고려한 최대 가치" 🎒 [💍 반지(2칸)] [⚔️ 신검(3칸)] → 가치 7 ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━ 결론: max(3, 7) = 7 선택! ━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

"현재 아이템을 넣으려면, 그 공간을 비워야 한다" 예시: 용량 5칸에 신검(3칸)을 넣으려면 → 3칸을 비우고, 남은 2칸으로 최선을 다해야 함 → 하지만! 신검은 아직 안 본 상태에서 2칸의 최선을 구해야 함 → 따라서 dp[i-1][2] (신검 보기 "전"의 2칸 최대 가치) 만약 dp[i][2]를 썼다면? → 신검을 이미 고려한 상태 (순환 참조!) → 신검을 2번 넣는 오류 발생 가능 i-1을 쓰는 이유: "아직 현재 아이템을 고려하지 않은 세계"의 값을 가져오기 위해!

if (weight[i] > w) { dp[i][w] = dp[i-1][w]; // 용량 초과 시 선택 불가 }

예시: 용량 2칸인데 신검(3칸)을 고려하는 경우 물리적으로 불가능! → 선택지가 1개뿐 → dp[2][2] = dp[1][2] (신검을 넣지 않은 경우만 가능)

아이템 1: 💍 마법반지 (2칸, 가치 3) 아이템 2: ⚔️ 신검 (3칸, 가치 4) 아이템 3: 🛡️ 용방패 (4칸, 가치 5) 아이템 4: 👑 왕의왕관 (5칸, 가치 6)

용량 → 0 1 2 3 4 5 아이템 ↓ 0개 (없음) 0 0 0 0 0 0

💭 각 용량별 계산: - 용량 0~1: 마법반지(2칸)이 안들어감 → 0 - 용량 2~5: 마법반지 들어감 → 가치 3 용량 → 0 1 2 3 4 5 아이템 ↓ 0개 (없음) 0 0 0 0 0 0 1개 (반지) 0 0 3 3 3 3

💭 핵심 계산 (용량 5): dp[2][5] = max ( dp[1][5], // 신검 안가져가기 = 3 dp[1][5-3] + 4 // 신검 가져가기 = dp[1][2] + 4 = 3 + 4 = 7 ) → max(3, 7) = 7 선택! (반지 + 신검) 용량 → 0 1 2 3 4 5 아이템 ↓ 0개 (없음) 0 0 0 0 0 0 1개 (반지) 0 0 3 3 3 3 2개 (신검) 0 0 3 4 4 7

💭 핵심 계산 (용량 5): dp[3][5] = max( dp[2][5], // 용방패 안가져가기 = 7 dp[2][5-4] + 5 // 용방패 가져가기 = dp[2][1] + 5 = 0 + 5 = 5 ) → max(7, 5) = 7 선택! (반지 + 신검이 더 좋음) 용량 → 0 1 2 3 4 5 아이템 ↓ 0개 (없음) 0 0 0 0 0 0 1개 (반지) 0 0 3 3 3 3 2개 (신검) 0 0 3 4 4 7 3개 (용방패) 0 0 3 4 5 7

💭 핵심 계산 (용량 5): dp[4][5] = max( dp[3][5], // 왕관 안가져가기 = 7 dp[3][5-5] + 6 // 왕관 가져가기 = dp[3][0] + 6 = 0 + 6 = 6 ) → max(7, 6) = 7 선택! (반지 + 신검 조합이 최고) 용량 → 0 1 2 3 4 5 아이템 ↓ 0개 (없음) 0 0 0 0 0 0 1개 (반지) 0 0 3 3 3 3 2개 (신검) 0 0 3 4 4 7 3개 (용방패) 0 0 3 4 5 7 4개 (왕관) 0 0 3 4 5 7 ← 최종!

#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; int main() { // 게임 설정 int capacity = 5; vector<string> items = { "💍마법반지", "⚔️신검", "🛡️용방패", "👑왕의왕관" }; vector<int> weights = { 2, 3, 4, 5 }; vector<int> values = { 3, 4, 5, 6 }; int n = items.size(); // DP 테이블 초기화 vector<vector<int>> dp(n + 1, vector<int>(capacity + 1, 0)); cout << "🎮 RPG 게임 - 던전 아이템 수집하기" << endl; cout << "🎒 인벤토리 용량: " << capacity << "칸\n" << endl; // 아이템 정보 출력 cout << "💎 발견한 아이템들:" << endl; for (int i = 0; i < n; i++) { cout << " " << (i + 1) << ". " << items[i] << " (용량: " << weights[i] << "칸, 가치: " << values[i] << ")" << endl; } cout << endl; // DP 계산 for (int i = 1; i <= n; i++) { cout << "📋 " << i << "단계: " << items[i - 1] << " 검토 중..." << endl; for (int w = 0; w <= capacity; w++) { if (weights[i - 1] > w) { // 현재 아이템이 용량을 초과하는 경우 dp[i][w] = dp[i - 1][w]; } else { // 선택하지 않는 경우와 선택하는 경우 중 최대값 int not_take = dp[i - 1][w]; int take = dp[i - 1][w - weights[i - 1]] + values[i - 1]; dp[i][w] = max(not_take, take); // 최대 용량에서의 계산 과정 출력 if (w == capacity) { cout << " 용량 " << w << "칸: max(" << not_take << ", " << take << ") = " << dp[i][w] << endl; } } } cout << endl; } // 최종 DP 테이블 출력 cout << "📊 최종 DP 테이블:" << endl; cout << " "; for (int w = 0; w <= capacity; w++) { cout << "c" << w << " "; } cout << endl; for (int i = 0; i <= n; i++) { if (i == 0) { cout << "없음: "; } else { cout << i << "개: "; } for (int w = 0; w <= capacity; w++) { cout << dp[i][w] << " "; } cout << endl; } cout << "\n🏆 최대 가치: " << dp[n][capacity] << endl; // 선택된 아이템 역추적 cout << "\n🎒 선택된 아이템들:" << endl; vector<bool> selected(n, false); int w = capacity; for (int i = n; i > 0 && w > 0; i--) { if (dp[i][w] != dp[i - 1][w]) { selected[i - 1] = true; cout << " ✅ " << items[i - 1] << " (용량: " << weights[i - 1] << "칸, 가치: " << values[i - 1] << ")" << endl; w -= weights[i - 1]; } else { cout << " ❌ " << items[i - 1] << " (선택하지 않음)" << endl; } } // 최종 요약 int total_weight = 0, total_value = 0; for (int i = 0; i < n; i++) { if (selected[i]) { total_weight += weights[i]; total_value += values[i]; } } cout << "\n📋 최종 요약:" << endl; cout << " 총 사용 용량: " << total_weight << "/" << capacity << "칸" << endl; cout << " 총 가치: " << total_value << endl; cout << " 남은 용량: " << (capacity - total_weight) << "칸" << endl; return 0; }

🎒 선택된 아이템 조합: ✅ 💍 마법반지 (2칸, 가치 3) ✅ ⚔️ 신검 (3칸, 가치 4) ❌ 🛡️ 용방패 (선택하지 않음) ❌ 👑 왕의왕관 (선택하지 않음) 총 사용 용량: 2 + 3 = 5칸 (꽉 참!) 총 가치: 3 + 4 = 7

1. dp[4][5] = 7, dp[3][5] = 7 → 왕관 선택 안함 ❌ 2. dp[3][5] = 7, dp[2][5] = 7 → 용방패 선택 안함 ❌ 3. dp[2][5] = 7, dp[1][5] = 3 → 신검 선택! ✅ (남은 용량: 5-3=2) 4. dp[1][2] = 3, dp[0][2] = 0 → 마법반지 선택! ✅

다른 가능한 조합들: - 👑 왕관만: 5칸, 가치 6 - 🛡️ 용방패만: 4칸, 가치 5 - 💍 반지 + ⚔️ 신검: 5칸, 가치 7 ← 최고! 작은 아이템들의 조합이 큰 아이템 하나보다 더 효율적!

각 단계에서 두 가지 선택: 1. 현재 아이템 선택 안함 → 이전 상태 그대로 2. 현재 아이템 선택함 → 남은 공간의 최적해 + 현재 아이템 가치

문제를 본다 → "어... 뭔가 복잡하네?" → 그리디로 시도 → 반례 발견 😱 → 브루트포스로 시도 → 시간초과 😵 → "이게 뭔 문제지?" → 답 확인 → "아, DP구나..."

5-10문제 후: "어? 이거 아까 본 패턴 같은데?" 20-30문제 후: "이런 키워드 나오면 DP일 확률 높아" 50문제 후: "문제 읽자마자 DP 냄새가 난다" 100문제 후: "이건 1차원 DP, 저건 2차원 DP"

// 1. 일부러 재귀로 먼저 풀어보기 int slowFib(int n) { if (n <= 1) return n; return slowFib(n-1) + slowFib(n-2); } // 2. "어? 너무 느리네" 경험하기 // 3. 같은 계산 반복 발견하기 // 4. "아하! 이걸 저장하면 되겠다" 깨달음

그냥 외워버리는 것도 방법: - "경우의 수" → DP 의심 - "최소 개수" → DP 의심 - "배낭, 동전, 계단" → 무조건 DP - "피보나치 같은 점화식" → DP