강의 20: 동적 프로그래밍 기초 (Dynamic Programming Basics)

단순 재귀 vs DP — 피보나치 예시

단순 재귀 fib(5):
    fib(5)
   /      \
fib(4)   fib(3)    ← fib(3) 중복!
 /   \   /   \
fib(3) fib(2) fib(2) fib(1)   ← fib(2) 3번 중복!
...
→ 시간: O(2^n), 공간: O(n)

DP 메모이제이션 fib(5):
    fib(5)
   /      \
fib(4)   [캐시: 3]  ← 이미 계산됨
 /   \
fib(3) [캐시: 2]
...
→ 시간: O(n), 공간: O(n)

1. 상태(State) 정의:
   dp[i] = "i번째까지 고려했을 때 ..."
   dp[i][j] = "i번째, j번째까지 고려했을 때 ..."

2. 점화식(Recurrence Relation):
   dp[i] = f(dp[i-1], dp[i-2], ...)

3. 초기값(Base Case):
   dp[0] = ..., dp[1] = ...

┌──────────────────┬────────────────────────┬──────────────────────────────┐
│ 특성             │ 메모이제이션 (Top-down) │ 타뷸레이션 (Bottom-up)       │
├──────────────────┼────────────────────────┼──────────────────────────────┤
│ 방향             │ 큰 문제 → 작은 문제     │ 작은 문제 → 큰 문제          │
│ 구현             │ 재귀 + 캐시             │ 반복문 + 테이블              │
│ 필요한 계산      │ 실제 필요한 것만        │ 모든 하위 문제 계산          │
│ 공간             │ O(n) + 재귀 스택        │ O(n) (스택 없음)             │
│ 속도             │ 함수 호출 오버헤드      │ 보통 더 빠름                 │
│ 구현 난이도      │ 직관적                  │ 순서 고려 필요               │
└──────────────────┴────────────────────────┴──────────────────────────────┘

┌──────────────────────┬───────────┬──────────┐
│ 방법                 │ 시간      │ 공간     │
├──────────────────────┼───────────┼──────────┤
│ 단순 재귀            │ O(2^n)    │ O(n)     │
│ 메모이제이션         │ O(n)      │ O(n)     │
│ 타뷸레이션           │ O(n)      │ O(n)     │
│ 공간 최적화          │ O(n)      │ O(1)     │
└──────────────────────┴───────────┴──────────┘

dp[i] = i번째 계단까지 오르는 경우의 수 (한 번에 1칸 또는 2칸)

dp[1] = 1   (1칸짜리: {1})
dp[2] = 2   (2칸짜리: {1,1}, {2})
dp[i] = dp[i-1] + dp[i-2]   (마지막에 1칸 왔거나 2칸 왔거나)

→ 피보나치와 동일한 점화식!

동전: [1, 5, 6, 9], 거스름돈: 11

그리디: 9 + 1 + 1 = 3개
DP:     5 + 6 = 2개  ← 최적!

그리디가 실패하는 이유: 지역 최적해 ≠ 전역 최적해

DP 점화식:
dp[i] = i원을 만드는 데 필요한 최소 동전 수
dp[0] = 0
dp[i] = min(dp[i - coin] + 1) for coin in coins if coin ≤ i