한양과기고 에듀테크 수업도구 대시보드

동적 계획법 (Dynamic Programming)

큰 문제를 작은 부분문제로 쪼갰더니, 같은 부분문제가 몇 번이고 다시 등장한다. 매번 다시 푸는 대신 한 번 푼 답을 표(table)에 적어두고 필요할 때 꺼내 쓰면 지수 시간이 다항 시간으로 줄어든다. 이것이 동적 계획법이다. 두 조건이 필요하다 — 겹치는 부분문제(overlapping subproblems) 와 최적 부분구조(optimal substructure).

1. 왜 필요한가 — 피보나치 재귀의 폭발

fib(n) = fib(n-1) + fib(n-2) 를 그대로 재귀로 계산하면 fib(n-2) 는 두 번, fib(n-3) 은 세 번… 호출된다. 호출 수는 대략 1.6ⁿ 로 늘어난다. 이미 계산한 값을 배열에 저장(메모이제이션)하면 각 fib(k) 를 딱 한 번만 계산한다.

단순 재귀 O(1.6ⁿ)

—

함수 호출 0 회

메모이제이션 O(n)

—

함수 호출 0 회

n=30 이면 단순 재귀는 260만 회, 메모이제이션은 59회. n을 1씩 올려보며 격차를 확인해 보라.

2. 동전 교환 — 1차원 표 채우기 (Bottom-Up)

주어진 동전들로 금액 A 를 만들 때 필요한 최소 동전 개수는? dp[x] = 금액 x 를 만드는 최소 개수. dp[x] = min(dp[x - coin] + 1) — 마지막에 낸 동전이 coin 이라고 가정하고 남은 금액 x-coin 의 답에 1을 더한다. dp[0]=0 에서 시작해 작은 금액부터 채운다.

동전 (쉼표로 구분)

목표 금액

동전과 금액을 정하고 ▶ 한 단계 를 누르세요.

주황 = 지금 계산 중인 dp[x] · 파랑 = 참조 중인 dp[x-coin] · 초록 = 최종 답. 탐욕법(제일 큰 동전부터)은 1,3,4 로 6을 만들 때 4+1+1=3개 를 내지만 DP는 3+3=2개 를 찾는다.

3. 0/1 배낭 문제 — 2차원 표 채우기

무게 한도 W 의 배낭에 물건을 담아 가치 합을 최대로. 각 물건은 넣거나 안 넣거나(0/1). dp[i][w] = 앞에서 i 개 물건만 고려하고 한도가 w 일 때 최대 가치. dp[i][w] = max( dp[i-1][w], dp[i-1][w - wᵢ] + vᵢ ) — i번째를 안 넣기 vs 넣기 중 큰 값.

물건 무게:가치 (공백 구분)

배낭 한도 W

물건과 한도를 정하고 ▶ 한 단계 를 누르세요.

채운 칸 수

완전 탐색 경우의 수 (2ⁿ)

—

최대 가치

행 = 물건을 하나씩 추가, 열 = 무게 한도 0…W. 각 칸은 바로 윗칸(안 넣기)과 왼쪽 위 어딘가(넣기)만 참조한다 → 이미 푼 부분문제 재활용.

4. Top-Down vs Bottom-Up

Top-Down (메모이제이션)

재귀를 그대로 두되, 결과를 memo 에 저장. 처음 보는 부분문제만 실제로 계산. 필요한 부분문제만 방문한다는 장점.

Bottom-Up (타뷸레이션)

가장 작은 부분문제부터 반복문으로 표를 채운다. 재귀 호출 스택이 없어 빠르고 스택 오버플로가 없다.

상태(state) 설계가 핵심

dp[...] 가 정확히 무엇을 의미하는지 한 문장으로 정의할 수 있어야 한다. 그다음 점화식과 초기값이 따라온다.

DP가 아닌 경우

부분문제가 겹치지 않으면(예: 병합 정렬) 그냥 분할 정복이다. 부분 최적이 전체 최적을 보장하지 않으면(예: 일부 그래프) DP를 못 쓴다.

5. 파이썬 구현

# 피보나치 — Top-Down 메모이제이션
from functools import lru_cache

@lru_cache(maxsize=None)
def fib(n):
    if n < 2:
        return n
    return fib(n - 1) + fib(n - 2)   # 같은 n은 한 번만 실제 계산

# 동전 교환 — Bottom-Up 1차원 DP, O(A · 동전수)
def min_coins(coins, amount):
    INF = float('inf')
    dp = [0] + [INF] * amount        # dp[0]=0, 나머지는 아직 모름
    for x in range(1, amount + 1):
        for c in coins:
            if c <= x:
                dp[x] = min(dp[x], dp[x - c] + 1)
    return dp[amount] if dp[amount] != INF else -1

# 0/1 배낭 — Bottom-Up 2차원 DP, O(n · W)
def knapsack(items, W):     # items = [(weight, value), ...]
    n = len(items)
    dp = [[0] * (W + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        wi, vi = items[i - 1]
        for w in range(W + 1):
            dp[i][w] = dp[i - 1][w]                     # i번째 안 넣기
            if wi <= w:
                dp[i][w] = max(dp[i][w], dp[i - 1][w - wi] + vi)  # 넣기
    return dp[n][W]

세 문제 모두 패턴이 같다 — ① dp 의 의미를 정의하고 ② 점화식을 세우고 ③ 초기값을 넣고 ④ 작은 것부터 채운다.