동적 계획법 — DP와 메모이제이션

이 토픽을 마치면

동적 계획법이 필요한 상황을 판단할 수 있고, 탑다운(메모이제이션)과 바텀업(타뷸레이션) 두 방식으로 문제를 풀 수 있습니다.

같은 계산을 반복하는 문제

피보나치 수열을 재귀로 구현하면:

def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

print(fib(35))  # 9227465 — 약 4초
print(fib(50))  # ... 끝나지 않음

fib(5)를 계산할 때 fib(3)이 2번, fib(2)가 3번 호출됩니다. fib(50)이면 중복 호출이 수십억 번에 달합니다.

fib(5)
├── fib(4)
│   ├── fib(3)        ← 여기서도 계산
│   │   ├── fib(2)
│   │   └── fib(1)
│   └── fib(2)        ← 또 계산
└── fib(3)            ← 또 계산
    ├── fib(2)        ← 또 계산
    └── fib(1)

시간 복잡도: O(2^n). 이미 계산한 답을 기억하면 이 문제가 사라집니다.

동적 계획법의 조건

DP를 적용하려면 두 가지가 필요합니다:

1. 중복 부분 문제 (Overlapping Subproblems)

같은 작은 문제가 여러 번 반복됩니다. 피보나치의 fib(3)처럼.

2. 최적 부분 구조 (Optimal Substructure)

큰 문제의 최적해가 작은 문제의 최적해로 구성됩니다. fib(n) = fib(n-1) + fib(n-2)처럼.

둘 다 만족하면 DP를 적용할 수 있습니다. 하나라도 안 되면 다른 방법(탐욕, 분할 정복 등)을 써야 합니다.

탑다운 — 메모이제이션

"위에서 아래로" 재귀를 유지하되, 계산 결과를 딕셔너리(또는 배열)에 저장합니다:

def fib(n, memo={}):
    if n <= 1:
        return n
    if n in memo:
        return memo[n]
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)
    return memo[n]

print(fib(50))   # 12586269025 — 즉시 완료
print(fib(100))  # 354224848179261915075

fib(50)이 4초에서 즉시로 바뀝니다. 각 fib(k)를 한 번만 계산하므로 시간 복잡도는 O(n)입니다.

Python에서는 functools.lru_cache로 더 깔끔하게 쓸 수 있습니다:

from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n <= 1:
        return n
    return fib(n - 1) + fib(n - 2)

데코레이터 한 줄로 메모이제이션이 완성됩니다.

바텀업 — 타뷸레이션

"아래에서 위로" 작은 문제부터 차례로 풀어 올라갑니다:

def fib(n):
    if n <= 1:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

재귀를 전혀 쓰지 않으므로 스택 오버플로우 위험이 없습니다. fib(10000)도 문제없습니다.

공간 최적화: 피보나치는 직전 2개 값만 있으면 되므로:

def fib(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for _ in range(2, n + 1):
        a, b = b, a + b
    return b

O(n) 시간, O(1) 공간.

탑다운 vs 바텀업

일반적으로 바텀업이 약간 더 빠르고(함수 호출 오버헤드 없음), 공간 최적화가 쉽습니다. 하지만 점화식을 반복문으로 바꾸는 게 직관적이지 않은 경우도 있어서, 상황에 따라 고릅니다.

대표 문제: 계단 오르기

계단이 n개 있고, 한 번에 1칸 또는 2칸 오를 수 있습니다. 꼭대기까지 가는 방법의 수는?

def climb_stairs(n):
    if n <= 2:
        return n
    dp = [0] * (n + 1)
    dp[1] = 1  # 1칸: 1가지
    dp[2] = 2  # 2칸: 1+1 또는 2, 2가지
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]
    return dp[n]

print(climb_stairs(5))   # 8
print(climb_stairs(10))  # 89

i번째 칸에 도달하려면 (i-1)에서 1칸 오르거나, (i-2)에서 2칸 오르면 됩니다. dp[i] = dp[i-1] + dp[i-2] — 피보나치와 같은 구조입니다.

대표 문제: 0-1 배낭

배낭 용량 W, 물건 n개. 각 물건은 넣거나 안 넣거나(0-1). 가치 합 최대화:

def knapsack(W, items):
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]

    for i in range(1, n + 1):
        weight, value = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]  # 안 넣는 경우
            if w >= weight:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - weight] + value)

    return dp[n][W]

items = [(2, 3), (3, 4), (4, 5), (5, 6)]  # (무게, 가치)
print(knapsack(8, items))  # 10

dp[i][w]는 "처음 i개 물건으로 용량 w를 채울 때의 최대 가치"입니다. 각 물건마다 "넣는다 vs 안 넣는다" 두 선택지의 최댓값을 기록합니다.

DP 문제 풀이 패턴

1. 상태 정의: dp[i]가 무엇을 의미하는지 명확히 한다
2. 점화식 도출: dp[i]를 이전 상태들로 표현한다
3. 초기값 설정: 가장 작은 문제의 답을 채운다
4. 순서 결정: 어떤 순서로 테이블을 채울지 정한다
5. 결과 추출: dp[n] 또는 max(dp)에서 답을 가져온다

코딩 테스트에서 "경우의 수", "최소/최대", "가능한지 여부"를 묻는 문제의 상당수가 DP입니다. 입력 크기가 수백~수천이면 O(n²) DP를 의심해보세요.

DP가 아닌 문제와 구분

DP와 탐욕법은 둘 다 "최적 부분 구조"를 활용하지만, 탐욕은 되돌림 없이 한 방향으로 가고, DP는 모든 선택지의 결과를 테이블에 기록합니다.

핵심 한 줄: 동적 계획법은 "같은 계산을 반복하지 않겠다"는 전략입니다. 메모이제이션(위→아래, 재귀+캐시)과 타뷸레이션(아래→위, 반복문+테이블) 두 방식으로 구현하며, O(2^n)을 O(n)이나 O(n²)으로 바꿉니다.