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

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

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

// factorial dp, 재귀함수 비교 예시 #include <iostream> #include <vector> int factorial(int n) { if (n <= 1) return 1; 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원을 만드는 경우 이것 또한 그리디 알고리즘의 하나로 볼 수 있다.

3원의 동전만 가지고 15원의 거스름을 가지려 좋지 않는 경우의수를 테이블을 만들어보자 | 금액 | 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원의 동전을 가지고 만들 수 있는 경우의 수를 생각해보자 | 금액 | 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 |

0+0 은 0 이기 때문에 (3,4) 조합으로 5원을 거슬러 줄 수 있다 dp[index] += dp[index - 현재 동전]

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> #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); } 문제점: F(5)를 계산할 때 F(5) / \ F(4) F(3) / \ / \ F(3) F(2) F(2) F(1) ... (중복 계산 발생) 시간복잡도: O(2^n) - 매우 비효율적!

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에서 얻을 수 있는 최대 가치

dp[i][w] = max( dp[i-1][w], // 현재 아이템을 선택하지 않는 경우 dp[i-1][w-weight[i]] + value[i] // 현재 아이템을 선택하는 경우 // 현재무게를 뺀 나머지 무게의 가치 + 현재무게의 가치 )

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

아이템 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