11. 다이나믹 프로그래밍 (DP)

입문의 최종 보스입니다. 큰 문제를 작은 문제로 쪼개고, 한 번 구한 답을 저장(메모)해 재사용합니다. 앞의 기법들로 쌓은 사고력이 여기서 종합돼요. 겁먹지 말고 "점화식 하나 세우기"부터 시작합니다.

소수 챕터에서 배운 완전탐색은 강력하지만, 같은 계산을 몇 번씩 반복하면 순식간에 느려집니다. DP는 바로 그 "이미 구한 답을 다시 구하지 않기" 를 무기로 완전탐색을 살려내는 기법이에요. 어렵게 느껴지는 이유는 딱 하나, 점화식 세우기입니다. 그것만 넘으면 코드는 오히려 짧습니다.

이 한 챕터에서 배우는 것:

완전탐색 → 메모이제이션 → 타뷸레이션으로 이어지는 발전 흐름
점화식(작은 문제로 큰 문제를 표현하는 식) 세우는 법
대표 예제: 피보나치, 계단 오르기, 배낭(knapsack)
그리디로 풀 문제와 DP로 풀 문제를 구분하는 감각

DP가 통하는 문제의 조건

아무 문제나 DP로 푸는 게 아닙니다. 두 조건이 맞아야 해요.

작은 문제의 답으로 큰 문제의 답이 만들어진다 (최적 부분 구조)
같은 작은 문제가 여러 번 다시 등장한다 (중복되는 부분 문제)

이 두 개가 보이면 "아, DP구나" 하고 점화식을 세우면 됩니다. 가장 유명한 예인 피보나치로 그림을 그려볼게요.

1단계: 완전탐색 (그냥 재귀)

피보나치 수열은 1, 1, 2, 3, 5, 8, 13, ... 처럼 앞의 두 수를 더한 값입니다. 정의 그대로 재귀로 옮기면 됩니다.

def fib(n):
    if n <= 2:            # 1번째, 2번째 항은 1
        return 1
    return fib(n - 1) + fib(n - 2)   # 정의 그대로

print(fib(10))   # 55

f(n) = f(n-1) + f(n-2) 이 식이 바로 점화식입니다. 큰 문제 f(n)을 더 작은 문제 f(n-1), f(n-2)로 표현했죠. 잘 돌아갑니다. 그런데...

잠깐, 이게 왜 느릴까?

fib(5)를 부르면 안에서 무슨 일이 벌어지는지 보세요. 같은 값을 몇 번씩 다시 계산합니다.

f(3)이 두 번, f(2)는 세 번이나 다시 계산됩니다. n이 커지면 이 중복이 폭발해요. 이 재귀는 O(2ⁿ) 입니다. fib(50)만 해도 호출 횟수가 수십억 번이라 사실상 멈춘 것처럼 느껴집니다. 소수 챕터에서 배운 "1초에 약 1억 번" 감각으로 보면 완전히 시간 초과죠.

💡 여기서 핵심 관찰이 나옵니다. 같은 문제를 또 푼다. 그렇다면 답을 한 번만 구하고 어딘가에 적어두면 되지 않을까요? 이게 DP의 전부입니다.

2단계: 메모이제이션 (위에서 아래로)

한 번 구한 답을 저장(memo)해두고, 또 물어보면 저장된 걸 바로 돌려줍니다. 재귀 구조는 그대로 두고 "메모장"만 추가하면 돼요.

def fib(n, memo={}):
    if n <= 2:
        return 1
    if n in memo:            # 이미 구해둔 답이면
        return memo[n]       # 다시 계산하지 않고 바로 반환
    memo[n] = fib(n - 1, memo) + fib(n - 2, memo)   # 처음이면 구해서 적어둠
    return memo[n]

print(fib(10))   # 55
print(fib(50))   # 12586269025  (이제 순식간에!)

메모장 덕분에 각 f(k)는 딱 한 번씩만 진짜로 계산됩니다. 호출 트리에서 회색 중복 노드들이 전부 사라지는 셈이죠. 그래서 시간복잡도가 O(2ⁿ) → O(n) 으로 확 줄어듭니다. fib(50)도 눈 깜짝할 새예요.

이렇게 큰 문제에서 시작해 재귀로 파고들며 답을 메모하는 방식을 메모이제이션, 또는 탑다운(top-down) 이라고 합니다.

💡 딕셔너리로 "이미 봤나?"를 즉시(O(1)) 확인하는 이 패턴, 소수 챕터에서 set으로 소수 여부를 즉시 확인하던 것과 똑같은 감각입니다. 자료구조로 "기억"을 만드는 거예요.

3단계: 타뷸레이션 (아래에서 위로)

메모이제이션을 뒤집어봅시다. 재귀로 위에서 내려가는 대신, 가장 작은 답부터 표(table)에 차곡차곡 채워 올라갑니다. 이게 타뷸레이션, 바텀업(bottom-up) 이에요.

def fib(n):
    dp = [0] * (n + 1)       # dp[i] = i번째 피보나치 수
    dp[1] = dp[2] = 1        # 가장 작은 답부터 직접 채움
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 점화식 그대로, 앞에서부터
    return dp[n]

print(fib(10))   # 55
print(fib(50))   # 12586269025

리스트 dp를 "답을 적어두는 표" 로 씁니다. 소수 챕터에서 [True] * (N+1) 배열을 칠판처럼 쓰던 것과 판박이예요. 시간복잡도는 똑같이 O(n) 이고, 재귀 호출이 없어서 대체로 더 빠르고 안전합니다(파이썬은 재귀가 깊어지면 에러가 나거든요).

사실 피보나치는 값 두 개만 기억하면 되니 표 없이도 됩니다.

def fib(n):
    a, b = 1, 1              # 직전 두 항만 들고 감
    for _ in range(n - 2):
        a, b = b, a + b      # 한 칸씩 앞으로
    return b

print(fib(10))   # 55

이건 O(n) 시간에 O(1) 공간입니다. "표 전체가 필요 없고 최근 몇 개만 필요하다"는 걸 관찰하면 공간까지 줄일 수 있어요.

💡 탑다운과 바텀업은 같은 점화식을 방향만 바꿔 푼 겁니다. 헷갈리면 탑다운(재귀+memo)이 점화식 그대로라 직관적이고, 바텀업(반복문+표)이 빠르고 안전합니다. 둘 다 손에 익히세요.

예제: 계단 오르기

이제 진짜 문제입니다. 계단이 n칸 있고, 한 번에 1칸 또는 2칸씩 오를 수 있을 때, 꼭대기까지 오르는 방법의 수는?

점화식을 어떻게 세울까요? DP의 핵심 질문은 언제나 "마지막 한 수를 어떻게 두었나?" 입니다.

n번째 칸에 도착하는 마지막 걸음은 둘 중 하나예요.

(n-1)칸에서 1칸 올라왔거나
(n-2)칸에서 2칸 올라왔거나

그래서 방법(n) = 방법(n-1) + 방법(n-2). 어라, 피보나치와 똑같은 점화식이네요!

def climb(n):
    if n <= 2:
        return n             # 1칸은 1가지, 2칸은 2가지(1+1, 2)
    dp = [0] * (n + 1)
    dp[1], dp[2] = 1, 2
    for i in range(3, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]   # 마지막에 1칸 or 2칸
    return dp[n]

print(climb(2))   # 2
print(climb(3))   # 3
print(climb(5))   # 8

시간복잡도 O(n). 겉모습이 전혀 다른 문제인데 점화식이 같다는 게 신기하죠? "마지막 선택으로 경우를 나눈다" 는 사고법이 몸에 배면, 처음 보는 문제에서도 점화식이 보이기 시작합니다.

예제: 0/1 배낭 (knapsack)

DP의 간판 문제입니다. 무게 한도 W인 배낭에, 각각 무게와 가치가 있는 물건들을 담아 가치 합을 최대로 만드는 문제예요. 물건은 쪼갤 수 없고, 각각 담거나(1) 안 담거나(0) 둘 중 하나입니다.

여기서 잠깐. "가치 대비 무게가 좋은 것부터 욕심껏 담으면 안 되나?" 싶죠. 그게 바로 그리디입니다. 그런데 0/1 배낭에서는 그리디가 틀립니다.

물건	무게	가치
A	6	60
B	3	40
C	3	40

한도 W=6일 때, 가치가 제일 큰 A(60)를 먼저 담으면 무게가 꽉 차서 끝, 총 60. 하지만 B+C를 담으면 무게 6에 가치 80입니다. 당장 좋아 보이는 선택이 전체 최적이 아닌 거죠. 그래서 모든 조합을 따지되 중복 계산은 피하는 DP가 필요합니다.

점화식은 또 "마지막 물건을 담았나 안 담았나" 로 나눕니다. dp[i][w]를 "앞에서 i개 물건까지 고려하고 무게 한도가 w일 때 최대 가치"로 정의하면,

i번째를 안 담으면: dp[i-1][w] (그대로)
i번째를 담으면: dp[i-1][w - 무게] + 가치 (담을 공간이 있을 때만)

둘 중 큰 값을 고릅니다.

def knapsack(items, 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]                  # i번째 물건을 안 담는 경우
            if w >= weight:                          # 담을 공간이 있으면
                take = dp[i - 1][w - weight] + value # 담아본 값과
                dp[i][w] = max(dp[i][w], take)       # 비교해 큰 쪽 선택
    return dp[n][W]

items = [(6, 60), (3, 40), (3, 40)]
print(knapsack(items, 6))    # 80  (B+C, 그리디의 60을 이김)

items2 = [(1, 6), (2, 10), (3, 12)]
print(knapsack(items2, 5))   # 22  (무게 2짜리 + 무게 3짜리)

표가 2차원이라 시간복잡도는 O(n × W) 입니다. 물건 수와 무게 한도의 곱이죠. 지금까지의 1차원 DP에서 한 단계 올라온 형태인데, "마지막 물건을 담느냐 마느냐"로 경우를 나누는 사고법은 완전히 똑같습니다.

💡 배낭 문제가 알려주는 교훈: 눈앞의 최선(그리디)이 전체 최선이 아닐 수 있다. 반대로, 물건을 쪼갤 수 있는 "분할 가능 배낭"은 가치/무게 비율 순 그리디가 정답입니다. 문제 조건 하나로 그리디와 DP가 갈리는 거예요.

그리디와 DP의 갈림길

10장에서 배운 그리디와 DP는 자주 헷갈립니다. 기준은 이겁니다.

그리디: 매 순간 최선을 고르면 그게 전체 최선이 보장될 때. 빠르지만 아무 문제에나 통하지 않음.
DP: 지금의 최선이 나중을 망칠 수 있어서 모든 경우를 따져봐야 할 때. 대신 중복 계산은 메모/표로 피함.

판단이 안 서면 작은 반례를 만들어보세요. 0/1 배낭의 A vs B+C처럼, 그리디 선택이 깨지는 예시 하나만 찾으면 "아, DP구나" 하고 넘어가면 됩니다.

정리

단계	방식	시간복잡도	특징
완전탐색	그냥 재귀	O(2ⁿ)	중복 계산 폭발. 개념용
메모이제이션	재귀 + 메모(탑다운)	O(n)	점화식 그대로라 직관적
타뷸레이션	반복문 + 표(바텀업)	O(n)	빠르고 안전(재귀 없음)
2차원 DP	표가 격자(예: 배낭)	O(n × W)	상태가 2개일 때

💡 DP 문제를 만나면 ① "마지막 선택"으로 경우를 나눠 점화식을 세우고 → ② 겹치는 부분 문제가 있는지 확인하고 → ③ 메모(탑다운) 또는 표(바텀업)로 중복을 제거한다. 소수의 "무식하게 풀고 → 복잡도 따지고 → 줄인다"와 정확히 같은 흐름입니다. 다룬 도구가 재귀+메모로 바뀌었을 뿐이에요.

직접 풀어보기

계단 오르기에서 한 번에 1칸, 2칸, 3칸까지 오를 수 있다면 점화식은 어떻게 바뀔까요? dp[i] = dp[i-1] + dp[i-2] + dp[i-3]으로 고쳐 climb3(5)를 구해보세요. (정답: 13)
타뷸레이션 피보나치를 O(1) 공간 버전으로 직접 바꿔보세요. (힌트: 리스트 대신 변수 두 개 a, b만 갱신)
배낭 문제에서 어떤 물건들을 담았는지 목록까지 출력해보세요. (힌트: dp[i][w] != dp[i-1][w]이면 i번째 물건을 담은 것)