동적 프로그래밍(DP): 메모이제이션과 타뷸레이션, 점화식 세우는 법
이 글의 핵심
DP가 어려운 이유는 코드보다 dp[i]가 무엇을 뜻하는지 정하는 단계에 있습니다. 문제가 DP인지 판단하는 신호부터 점화식 세우기, 초기값 설정, 구현 방식 선택까지 4단계로 나눠 설명하고, 테이블 전체 대신 직전 값만 남기는 공간 최적화와 디버깅 요령도 함께 정리합니다.
시리즈 안내
들어가며
동적 프로그래밍(DP)은 중복 계산을 저장해서 O(2ⁿ) → O(n)으로 최적화하는 기법입니다.
“동적 프로그래밍”이라는 이름은 기법의 내용과 거의 관계가 없습니다. 1950년대에 이 방법을 정리한 Richard Bellman이 연구비를 받기 좋은 이름을 고르다 붙였다는 일화가 유명합니다. 실제 핵심은 단순합니다. 큰 문제를 작은 문제로 나누되, 같은 작은 문제가 여러 번 나오면 한 번만 풀고 답을 재사용하는 것입니다.
DP를 처음 배울 때 가장 어려운 부분은 코드가 아니라 dp[i]가 무엇을 뜻하는지 한 문장으로 정의하는 단계입니다. 이 정의만 정확하면 점화식과 초기값은 거의 자동으로 따라오고, 정의가 흐릿하면 코드를 아무리 고쳐도 답이 맞지 않습니다. 이 글은 피보나치로 중복 계산이 왜 문제인지 확인한 뒤, 같은 문제를 Top-Down과 Bottom-Up 두 방식으로 풀고, 1차원·2차원·배낭 문제에서 “상태 정의 → 점화식 → 초기값 → 계산 순서”를 차례로 세우는 과정을 보여 줍니다.
사전 지식 (초보자를 위한 기초)
재귀(Recursion)란?
재귀는 함수가 자기 자신을 호출하는 것입니다. 마치 거울 앞에 거울을 놓으면 무한히 반복되는 것처럼요.
# 간단한 재귀 예시: 팩토리얼
# 5! = 5 × 4 × 3 × 2 × 1 = 120
def factorial(n):
# 기저 조건 (재귀를 멈추는 조건)
if n <= 1:
return 1
# 재귀 호출 (자기 자신을 호출)
return n * factorial(n - 1)
print(factorial(5)) # 120
# 실행 과정:
# factorial(5) = 5 × factorial(4)
# = 5 × (4 × factorial(3))
# = 5 × (4 × (3 × factorial(2)))
# = 5 × (4 × (3 × (2 × factorial(1))))
# = 5 × (4 × (3 × (2 × 1)))
# = 5 × 4 × 3 × 2 × 1
# = 120재귀의 핵심:
- 기저 조건: 재귀를 멈추는 조건 (없으면 무한 반복!)
- 재귀 호출: 문제를 작은 문제로 쪼개서 해결
기저 조건이 없으면 실제로는 “무한 반복”이 아니라 호출 스택이 넘쳐서 프로그램이 멈춥니다. Python은 기본 재귀 깊이 제한이 약 1000이라 RecursionError: maximum recursion depth exceeded가 나고, C++이나 Java에서는 스택 오버플로(세그멘테이션 폴트, StackOverflowError)가 납니다. 이 제한은 기저 조건이 있어도 적용된다는 점이 중요합니다. factorial(5000)은 올바른 코드지만 Python 기본 설정에서는 깊이 제한에 걸립니다. 뒤에서 Top-Down DP의 단점으로 “스택 오버플로 위험”을 드는 이유가 이것입니다.
중복 계산 문제
재귀를 사용하면 같은 계산을 여러 번 하게 됩니다.
# 피보나치 수열: 1, 1, 2, 3, 5, 8, 13, ...
# fib(n) = fib(n-1) + fib(n-2)
def fib(n):
if n <= 1:
return n
return fib(n-1) + fib(n-2)
# fib(5)를 계산하면:
#
# fib(5)
# / \
# fib(4) fib(3)
# / \ / \
# fib(3) fib(2) fib(2) fib(1)
# / \ / \ / \
# fib(2) fib(1) f(1) f(0) f(1) f(0)
# / \
# f(1) f(0)
#
# fib(3)이 2번 계산됨! (중복!)
# fib(2)가 3번 계산됨! (중복!)
# fib(1)이 5번 계산됨! (중복!)
#
# 너무 비효율적입니다!문제점:
fib(40)을 계산하면 함수가 약 3억 3천만 번 호출됨- Python에서는 수십 초 걸림
호출 횟수는 정확히 계산할 수 있습니다. fib(n)의 호출 횟수를 C(n)이라 하면 C(n) = C(n-1) + C(n-2) + 1이고, 이것을 풀면 C(n) = 2·fib(n+1) - 1입니다. fib(41)이 165,580,141이므로 fib(40) 한 번에 331,160,281번의 호출이 일어납니다. 흔히 “O(2ⁿ)“이라고 말하지만 실제 증가율은 황금비 φ ≈ 1.618의 n제곱, 즉 O(φⁿ)입니다. 어느 쪽이든 n이 1 늘 때마다 계산량이 1.6배씩 늘어나는 지수 시간이라는 점은 같고, n이 50이면 호출이 수백억 번이 되어 사실상 끝나지 않습니다.
반면 서로 다른 부분 문제는 fib(0)부터 fib(40)까지 41개뿐입니다. 수억 번의 호출이 겨우 41개의 답을 반복해서 다시 구하고 있는 셈이고, DP는 바로 이 격차를 없애는 기법입니다.
동적 프로그래밍(DP)이란?
DP는 한 번 계산한 결과를 저장해두며, 다음에 필요할 때 저장된 값을 재사용하는 기법입니다. 비유:
- 재귀: 전화번호를 매번 계산해서 찾기
- DP: 전화번호를 메모장에 적어두고 필요할 때 메모장 보기
# DP를 사용한 피보나치
def fib_dp(n, memo={}):
# 이미 계산했으면 저장된 값 반환
if n in memo:
return memo[n]
# 기저 조건
if n <= 1:
return n
# 계산 후 저장
memo[n] = fib_dp(n-1, memo) + fib_dp(n-2, memo)
return memo[n]
print(fib_dp(40)) # 즉시 출력! (0.001초)
# fib(40) 비교:
# 일반 재귀: 약 3억 3천만 번 호출 (수십 초)
# DP: 각 값을 한 번씩, 약 40번만 계산 (즉시)여기서 memo={}를 기본 인자로 쓴 것은 짧게 보여 주기 위한 것이고, 아래 “메모이제이션 주의사항”에서 설명하는 함정이 있습니다. 피보나치처럼 입력만으로 답이 결정되는 함수에서는 호출 사이에 캐시가 공유되어도 결과가 틀리지 않지만, 문제마다 입력 데이터가 달라지는 함수에서 같은 패턴을 쓰면 이전 문제의 답이 섞입니다.
DP를 사용하는 문제의 특징
DP는 다음 2가지 조건이 있을 때 사용합니다: 1) 최적 부분 구조 (Optimal Substructure)
- 큰 문제의 답이 작은 문제의 답으로 구할 수 있음
- 예:
fib(5) = fib(4) + fib(3)2) 중복되는 부분 문제 (Overlapping Subproblems) - 같은 작은 문제를 여러 번 계산함
- 예:
fib(3)을 여러 번 계산 DP 문제 키워드: - “최대/최소 값 구하기”
- “경우의 수 구하기”
- “가능한지 판단하기”
- 피보나치, 계단 오르기, 배낭 문제 등
두 조건 중 하나만 있으면 DP가 아닙니다. 최적 부분 구조는 있지만 부분 문제가 겹치지 않는 경우(병합 정렬처럼 왼쪽 절반과 오른쪽 절반이 완전히 다른 문제)는 분할 정복이고, 저장할 것이 없으니 메모이제이션을 해도 빨라지지 않습니다. 반대로 부분 문제는 겹치지만 최적 부분 구조가 없는 경우도 있습니다. 대표적인 예가 가장 긴 단순 경로 문제로, A→C의 가장 긴 경로가 A→B의 가장 긴 경로와 B→C의 가장 긴 경로를 이어 붙인 것이 아닐 수 있습니다(두 경로가 같은 정점을 지나면 단순 경로가 아니게 됨). 이런 문제에 DP 점화식을 억지로 세우면 틀린 답이 나옵니다.
“최대/최소”, “경우의 수” 같은 키워드는 신호일 뿐 판정 기준은 아닙니다. 최소 동전 개수 문제는 동전 단위가 500, 100, 50, 10처럼 배수 관계일 때는 그리디로 풀리지만, 1, 3, 4원처럼 배수 관계가 아니면 DP가 필요합니다(6원을 만들 때 그리디는 4+1+1로 3개, DP는 3+3으로 2개). 키워드를 보면 먼저 “작은 입력의 답으로 큰 입력의 답을 만들 수 있는가”를 확인하는 것이 순서입니다.
DP의 2가지 방법
Top-Down (하향식 - 재귀)
# 큰 문제부터 시작 → 작은 문제로 쪼갬
# fib(5) → fib(4) → fib(3) → ...
def fib_topdown(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_topdown(n-1, memo) + fib_topdown(n-2, memo)
return memo[n]Bottom-Up (상향식 - 반복문)
# 작은 문제부터 시작 → 큰 문제로 쌓아감
# fib(0), fib(1), fib(2), ... → fib(5)
def fib_bottomup(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]비교:
- Top-Down: 이해하기 쉬움, 필요한 것만 계산
- Bottom-Up: 더 빠름, 메모리 효율적
두 방식은 같은 점화식을 다른 순서로 계산할 뿐이라 시간 복잡도는 같습니다. Top-Down은 “fib(5)를 구하려면 fib(4)와 fib(3)이 필요하다”는 의존 관계를 재귀가 알아서 따라가 주므로, 계산 순서를 고민할 필요가 없습니다. Bottom-Up은 “dp[i]를 채우기 전에 dp[i-1], dp[i-2]가 이미 채워져 있어야 한다”는 순서를 사람이 정해 반복문으로 써야 합니다. 1차원에서는 당연해 보이지만, 2차원 이상에서 어느 방향으로 테이블을 채울지 틀리면 아직 계산하지 않은 0을 읽어 조용히 틀린 답이 나옵니다.
DP 기본 개념
피보나치 수열로 이해하기
문제: n번째 피보나치 수 구하기
# ❌ 단순 재귀 (O(2ⁿ) - 매우 느림!)
def fib_naive(n):
if n <= 1:
return n
return fib_naive(n-1) + fib_naive(n-2)
print(fib_naive(40)) # 수십 초 걸림!문제점: 같은 값을 여러 번 계산
fib(5)
├─ fib(4)
│ ├─ fib(3)
│ │ ├─ fib(2) ← 중복!
│ │ └─ fib(1)
│ └─ fib(2) ← 중복!
└─ fib(3) ← 중복!
├─ fib(2)
└─ fib(1)Top-Down (메모이제이션)
재귀 + 캐싱 (메모이제이션)
메모이제이션은 한 번 구한 fib(k) 값을 딕셔너리에 저장해 두었다가, 같은 k가 다시 필요할 때 재귀 호출 대신 저장된 값을 꺼내 씁니다. 전화번호를 외운 뒤에는 매번 계산하지 않고 메모장만 보는 것과 같습니다.
# ✅ 메모이제이션 (O(n))
def fib_memo(n, memo={}):
# 이미 계산한 값이면 바로 반환 (O(1))
if n in memo:
return memo[n]
# 기저 조건
if n <= 1:
return n
# 재귀 호출 + 결과 저장
# fib(n) = fib(n-1) + fib(n-2)
memo[n] = fib_memo(n-1, memo) + fib_memo(n-2, memo)
return memo[n]
print(fib_memo(40)) # 즉시 출력! (0.001초 미만)
# 단순 재귀 vs 메모이제이션 비교:
# fib_naive(40): 약 3억 3천만 번 호출 (수십 초)
# fib_memo(40): 각 값을 한 번씩만 계산 (즉시)
#
# 탐색 과정 (n=5):
# fib_memo(5) 호출
# → fib_memo(4) 호출
# → fib_memo(3) 호출
# → fib_memo(2) 호출
# → fib_memo(1) = 1 (기저)
# → fib_memo(0) = 0 (기저)
# → memo[2] = 1
# → fib_memo(1) = 1 (기저)
# → memo[3] = 2
# → fib_memo(2) = 1 (memo에서 가져옴, 재계산 안 함!)
# → memo[4] = 3
# → fib_memo(3) = 2 (memo에서 가져옴)
# → memo[5] = 5
#
# 각 값은 딱 한 번만 계산됨!메모이제이션 주의사항:
# ❌ 잘못된 사용: memo를 기본 인자로 사용
def fib_bad(n, memo={}):
# 기본 인자는 함수 정의 시 한 번만 생성됨
# 여러 번 호출 시 같은 dict를 공유
pass
# 첫 호출
fib_bad(10) # memo에 0~10 저장
# 두 번째 호출
fib_bad(5) # 이미 저장된 값 사용 (의도치 않은 공유)
# ✅ 올바른 사용: memo를 None으로 초기화
def fib_good(n, memo=None):
if memo is None:
memo = {} # 매 호출마다 새로운 dict 생성
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_good(n-1, memo) + fib_good(n-2, memo)
return memo[n]Python의 기본 인자는 함수를 정의할 때 한 번만 평가되어 모든 호출이 같은 객체를 공유합니다. 리스트나 딕셔너리 같은 가변 객체를 기본값으로 두면 이전 호출에서 바꾼 내용이 다음 호출에 남아 있는 이유가 이것이고, Python에서 가장 유명한 함정 중 하나입니다.
DP에서 이 함정이 실제 버그가 되는 것은 캐시 키가 상태를 전부 담지 못할 때입니다. 예를 들어 def solve(i, memo={})가 전역 배열 arr을 읽는다면, arr이 바뀐 다음 문제에서도 이전 arr로 계산한 memo[i]를 그대로 반환합니다. 코딩 테스트에서 테스트 케이스가 여러 개인 문제(첫 줄에 T가 주어지는 형식)를 풀 때 첫 케이스만 맞고 나머지가 틀리는 원인으로 자주 보입니다. memo=None 패턴이나 케이스마다 새 딕셔너리를 만드는 것으로 해결됩니다.
Python 데코레이터
from functools import lru_cache
@lru_cache(maxsize=None)
def fib_cached(n):
if n <= 1:
return n
return fib_cached(n-1) + fib_cached(n-2)
print(fib_cached(100)) # 매우 빠름lru_cache(Python 3.9+에서는 functools.cache)는 인자를 키로 결과를 자동 저장해 주므로, 원래 재귀 함수에 데코레이터 한 줄만 붙이면 메모이제이션이 됩니다. 직접 딕셔너리를 관리할 때보다 실수가 적어 코딩 테스트에서 특히 유용합니다.
몇 가지 제약도 있습니다. 인자가 해시 가능해야 하므로 리스트를 인자로 넘기면 TypeError: unhashable type: 'list'가 나고, 튜플로 바꿔야 합니다. 캐시는 함수 객체에 붙어 있어 프로그램이 끝날 때까지 남으므로, 테스트 케이스가 여러 개인 문제에서는 fib_cached.cache_clear()로 비워야 합니다. 그리고 메모이제이션을 해도 재귀 깊이는 줄지 않습니다. 처음 fib_cached(5000)을 호출하면 5000단계 깊이로 내려가야 하므로 RecursionError가 납니다. sys.setrecursionlimit으로 제한을 늘릴 수 있지만 너무 크게 올리면 인터프리터 자체가 크래시할 수 있어서, 깊이가 수천 이상인 문제라면 Bottom-Up으로 바꾸는 편이 안전합니다.
Bottom-Up (타뷸레이션)
반복문 + 테이블 (Bottom-Up)
Bottom-Up은 작은 문제부터 순서대로 풀어 테이블을 채웁니다:
# ✅ Bottom-Up (O(n), 재귀보다 빠름)
def fib_dp(n):
# 기저 조건
if n <= 1:
return n
# DP 테이블 생성
# dp[i]: i번째 피보나치 수
dp = [0] * (n + 1)
# 초기값 설정
dp[0] = 0 # fib(0) = 0
dp[1] = 1 # fib(1) = 1
# 작은 문제부터 순서대로 해결
for i in range(2, n + 1):
# 점화식: fib(i) = fib(i-1) + fib(i-2)
# 이미 계산된 값(dp[i-1], dp[i-2])을 사용
dp[i] = dp[i-1] + dp[i-2]
# 최종 답 반환
return dp[n]
print(fib_dp(100)) # 즉시 출력
# 계산 과정 (n=5):
# dp = [0, 0, 0, 0, 0, 0]
#
# 초기화:
# dp = [0, 1, 0, 0, 0, 0]
#
# i=2: dp[2] = dp[1] + dp[0] = 1 + 0 = 1
# dp = [0, 1, 1, 0, 0, 0]
#
# i=3: dp[3] = dp[2] + dp[1] = 1 + 1 = 2
# dp = [0, 1, 1, 2, 0, 0]
#
# i=4: dp[4] = dp[3] + dp[2] = 2 + 1 = 3
# dp = [0, 1, 1, 2, 3, 0]
#
# i=5: dp[5] = dp[4] + dp[3] = 3 + 2 = 5
# dp = [0, 1, 1, 2, 3, 5]
#
# return dp[5] = 5Top-Down vs Bottom-Up 비교:
# Top-Down (메모이제이션)
# 장점:
# - 재귀로 직관적
# - 필요한 부분만 계산 (일부 문제에서 유리)
# 단점:
# - 재귀 호출 오버헤드
# - 스택 오버플로우 위험 (깊이 제한)
# - 상대적으로 느림
# Bottom-Up (타뷸레이션)
# 장점:
# - 반복문으로 빠름
# - 스택 오버플로우 없음
# - 공간 최적화 쉬움
# 단점:
# - 모든 부분 문제를 계산 (불필요한 계산 가능)
# - 점화식을 찾기 어려울 수 있음
# 실전에서는 Bottom-Up을 더 많이 사용“Bottom-Up이 더 빠르다”는 말은 상수 차이를 뜻합니다. Python에서 함수 호출은 비싼 연산이라, 같은 O(n)이라도 반복문으로 배열을 채우는 쪽이 재귀 + 딕셔너리 조회보다 몇 배 빠른 경우가 흔합니다. 하지만 Top-Down이 더 빠른 경우도 있습니다. 상태 공간은 크지만 실제로 필요한 상태가 일부뿐인 문제입니다. 예를 들어 f(n) = f(n/2) + f(n/3)처럼 n이 10¹²까지 가는 점화식은 Bottom-Up으로 10¹²칸 테이블을 만들 수 없지만, Top-Down은 실제로 도달하는 수천 개 상태만 계산합니다.
제가 코딩 테스트 문제를 풀 때 쓰는 방식은 Top-Down으로 먼저 맞히고, 필요하면 Bottom-Up으로 옮기는 것입니다. 재귀 버전은 점화식을 그대로 코드로 옮긴 것이라 정확성을 확인하기 쉽고, 시간 초과나 재귀 깊이 문제가 생길 때만 반복문으로 바꿉니다. 이때 Top-Down 코드에서 “어떤 상태가 어떤 상태를 참조하는지”를 보면 Bottom-Up의 반복 순서가 자연스럽게 정해집니다.
공간 최적화
# ✅ O(1) 공간
def fib_optimized(n):
if n <= 1:
return n
prev2, prev1 = 0, 1
for _ in range(2, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current
return prev1
print(fib_optimized(100))dp[i]가 dp[i-1]과 dp[i-2]만 참조하므로, 그보다 앞의 값은 한 번 쓰고 나면 다시 필요 없습니다. 그래서 배열 전체 대신 변수 두 개만 들고 다니면 공간이 O(n)에서 O(1)로 줄어듭니다. prev2, prev1 = prev1, current는 Python의 동시 대입이라 오른쪽이 먼저 모두 계산된 뒤 왼쪽에 들어가므로 순서 문제가 없습니다. C++이나 Java로 옮길 때는 임시 변수를 써야 하고, 대입 순서를 바꾸면 값이 덮어써져 틀린 답이 나옵니다.
fib(100)은 354224848179261915075로 64비트 정수 범위(약 9.2×10¹⁸)를 넘습니다. Python은 정수 크기에 제한이 없어 그대로 출력되지만, C++이나 Java에서는 fib(93)부터 long long이 오버플로합니다. 그래서 코딩 테스트의 경우의 수 문제는 대부분 “10,007로 나눈 나머지를 출력하라”처럼 모듈러 연산을 요구하고, 이때는 덧셈할 때마다 % MOD를 적용해야 중간값이 넘치지 않습니다.
DP 문제 풀이 패턴
패턴 1: 1차원 DP
예제: 계단 오르기
def climb_stairs(n):
"""
1칸 또는 2칸씩 올라갈 수 있을 때 경우의 수
문제 이해:
- n=1: 1가지 (1칸)
- n=2: 2가지 (1+1칸, 2칸)
- n=3: 3가지 (1+1+1칸, 1+2칸, 2+1칸)
- n=4: 5가지
- n=5: 8가지
"""
# 기저 조건
if n <= 2:
return n
# DP 테이블 생성
# dp[i]: i번째 계단에 도달하는 경우의 수
dp = [0] * (n + 1)
# 초기값 설정
dp[1] = 1 # 1번 계단: 1가지 (1칸)
dp[2] = 2 # 2번 계단: 2가지 (1+1칸, 2칸)
# 점화식: dp[i] = dp[i-1] + dp[i-2]
# i번째 계단에 도달하는 방법:
# 1. (i-1)번째 계단에서 1칸 올라오기: dp[i-1]가지
# 2. (i-2)번째 계단에서 2칸 올라오기: dp[i-2]가지
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(climb_stairs(5)) # 8
# 계산 과정 (n=5):
# dp = [0, 1, 2, 0, 0, 0]
#
# i=3: dp[3] = dp[2] + dp[1] = 2 + 1 = 3
# (2번에서 1칸) + (1번에서 2칸)
# dp = [0, 1, 2, 3, 0, 0]
#
# i=4: dp[4] = dp[3] + dp[2] = 3 + 2 = 5
# (3번에서 1칸) + (2번에서 2칸)
# dp = [0, 1, 2, 3, 5, 0]
#
# i=5: dp[5] = dp[4] + dp[3] = 5 + 3 = 8
# (4번에서 1칸) + (3번에서 2칸)
# dp = [0, 1, 2, 3, 5, 8]
#
# return 8공간 최적화 버전:
def climb_stairs_optimized(n):
if n <= 2:
return n
# 이전 두 값만 저장 (O(1) 공간)
prev2, prev1 = 1, 2 # dp[1], dp[2]
for i in range(3, n + 1):
current = prev1 + prev2
prev2, prev1 = prev1, current # 값 이동
return prev1
# 공간복잡도: O(n) → O(1)
# dp[i]는 dp[i-1]과 dp[i-2]만 필요하므로
# 전체 배열을 유지할 필요 없음계단 오르기의 점화식이 피보나치와 같다는 것은 우연이 아닙니다. 핵심은 마지막 한 걸음으로 경우를 나누는 것입니다. i번째 계단에 도착하는 모든 방법은 마지막 걸음이 1칸이었거나 2칸이었거나 둘 중 하나이고, 두 경우는 겹치지 않으며 빠지는 경우도 없습니다. 그래서 두 경우의 수를 더하면 됩니다. 이 “마지막 선택으로 나누기”는 경우의 수 DP 대부분에 적용되는 사고방식입니다. 한 번에 1, 2, 3칸을 오를 수 있다면(백준 9095번) dp[i] = dp[i-1] + dp[i-2] + dp[i-3]이 됩니다.
초기값에서 흔히 실수하는 부분은 dp[0]의 의미입니다. 이 코드는 dp[1], dp[2]를 직접 정하고 3부터 시작해서 문제가 없지만, dp[0] = 1(“0칸을 오르는 방법은 아무것도 안 하는 1가지”)로 두면 dp[2] = dp[1] + dp[0] = 2가 자연스럽게 나와 예외 처리가 줄어듭니다. 반대로 dp[0] = 0으로 두고 2부터 반복하면 dp[2] = 1이 되어 전체 답이 틀립니다. 초기값은 “그 상태의 정의를 문자 그대로 적용했을 때 답이 무엇인가”로 정해야 합니다.
패턴 2: 2차원 DP
예제: 최소 경로 합
def min_path_sum(grid):
"""
(0,0)에서 (n-1,m-1)까지 최소 합
"""
n, m = len(grid), len(grid[0])
dp = [[0] * m for _ in range(n)]
# 초기값
dp[0][0] = grid[0][0]
# 첫 행
for j in range(1, m):
dp[0][j] = dp[0][j-1] + grid[0][j]
# 첫 열
for i in range(1, n):
dp[i][0] = dp[i-1][0] + grid[i][0]
# 나머지
for i in range(1, n):
for j in range(1, m):
dp[i][j] = min(dp[i-1][j], dp[i][j-1]) + grid[i][j]
return dp[n-1][m-1]
# 테스트
grid = [
[1, 3, 1],
[1, 5, 1],
[4, 2, 1]
]
print(min_path_sum(grid)) # 7 (1→3→1→1→1)이 문제의 상태 정의는 “dp[i][j] = (0,0)에서 (i,j)까지 오는 경로의 최소 합”입니다. 오른쪽이나 아래로만 움직일 수 있으므로 (i,j)에 오는 직전 칸은 위(i-1,j) 아니면 왼쪽(i,j-1)이고, 둘 중 작은 쪽에 현재 칸 값을 더하면 됩니다. 첫 행과 첫 열을 따로 채운 것은 이 칸들에 들어오는 방향이 하나뿐이기 때문입니다. 이 처리를 빼고 dp를 0으로 둔 채 min을 계산하면, 존재하지 않는 바깥 칸의 0을 최솟값으로 골라 답이 작게 나옵니다. 경계를 무한대(float('inf'))로 채운 테이블을 한 칸 크게 만드는 것도 흔한 대안입니다.
이 DP가 성립하는 전제는 이동 방향이 오른쪽과 아래로 제한된다는 것입니다. 네 방향으로 모두 움직일 수 있다면 (i,j)의 답이 (i+1,j)의 답에 의존하고, (i+1,j)도 다시 (i,j)에 의존하는 순환이 생겨 테이블을 채울 순서가 없어집니다. 이런 문제는 DP가 아니라 다익스트라 같은 최단 경로 알고리즘으로 풀어야 합니다. “상태 사이에 순환이 없는가(DAG인가)“를 확인하는 것이 DP 적용 가능성을 판단하는 또 하나의 기준입니다.
패턴 3: 배낭 문제 (Knapsack)
0-1 배낭 문제는 각 물건을 넣거나 넣지 않는 선택을 최적화합니다:
def knapsack(weights, values, capacity):
"""
0-1 배낭 문제
문제: 배낭 용량 capacity 이하로 물건을 담아 가치 최대화
제약: 각 물건은 0개 또는 1개만 선택 가능 (0-1)
입력:
- weights: 각 물건의 무게
- values: 각 물건의 가치
- capacity: 배낭 용량
"""
n = len(weights)
# DP 테이블 생성
# dp[i][w]: i번째 물건까지 고려했을 때, 용량 w에서의 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# i=0: 물건이 없으면 가치 0 (이미 초기화됨)
# w=0: 용량이 0이면 가치 0 (이미 초기화됨)
for i in range(1, n + 1):
for w in range(capacity + 1):
# 선택 1: i번째 물건을 넣지 않는 경우
# 이전 상태(i-1번째까지)의 가치를 그대로 가져옴
dp[i][w] = dp[i-1][w]
# 선택 2: i번째 물건을 넣는 경우
# 조건: 현재 물건의 무게가 용량 이하여야 함
if weights[i-1] <= w:
# i번째 물건을 넣으면:
# - 남은 용량: w - weights[i-1]
# - 가치: dp[i-1][w - weights[i-1]] + values[i-1]
# 두 선택 중 최대값 선택
dp[i][w] = max(
dp[i][w], # 넣지 않는 경우
dp[i-1][w - weights[i-1]] + values[i-1] # 넣는 경우
)
# 모든 물건을 고려했을 때, 전체 용량에서의 최대 가치
return dp[n][capacity]
# 테스트
weights = [2, 3, 4, 5] # 무게
values = [3, 4, 5, 6] # 가치
capacity = 8 # 배낭 용량
print(knapsack(weights, values, capacity)) # 10
# DP 테이블 계산 (일부):
# dp[i][w]: i번째까지, 용량 w
#
# w: 0 1 2 3 4 5 6 7 8
# i=0: 0 0 0 0 0 0 0 0 0 (물건 없음)
# i=1: 0 0 3 3 3 3 3 3 3 (무게2, 가치3)
# i=2: 0 0 3 4 4 7 7 7 7 (무게3, 가치4)
# i=3: 0 0 3 4 5 7 8 9 9 (무게4, 가치5)
# i=4: 0 0 3 4 5 7 8 9 10 (무게5, 가치6)
#
# 최종 답: dp[4][8] = 10
# 선택된 물건: 무게3(가치4) + 무게5(가치6) = 총 무게8, 총 가치10배낭 문제는 상태를 두 개의 차원으로 정의해야 하는 첫 번째 예입니다. “지금까지 몇 번째 물건까지 고려했는가”와 “남은 용량이 얼마인가”를 모두 알아야 다음 선택의 결과가 결정되기 때문입니다. 물건 번호만으로 상태를 정의하면(dp[i] = i번째까지의 최대 가치) 용량 정보가 사라져서 점화식을 세울 수 없습니다. DP가 막힐 때는 대개 상태에 필요한 정보가 빠져 있는 경우라서, “다음 결정을 내리려면 무엇을 알아야 하는가”를 하나씩 적어 보면 필요한 차원이 보입니다.
이 문제를 그리디로 풀면 틀리는 이유도 이 표에서 볼 수 있습니다. 가치/무게 비율이 가장 높은 물건은 무게 2(비율 1.5)인데, 이것부터 담으면 2+3=5, 가치 7 이후 남은 용량 3에 들어갈 수 있는 물건이 없어 가치 7에서 멈춥니다(2+4=6, 가치 8도 가능하지만 최적은 아님). 실제 최적은 비율이 낮은 무게 3과 5를 조합한 10입니다. 물건을 쪼갤 수 있는 분할 배낭 문제에서만 그리디가 최적이고, 0-1 배낭은 DP가 필요합니다.
시간 복잡도는 O(n × capacity)입니다. 입력 크기가 아니라 용량 숫자의 크기에 비례한다는 점이 중요한데, 용량이 10⁹이면 테이블을 만들 수 없습니다. 이런 알고리즘을 의사 다항 시간(pseudo-polynomial)이라고 부르며, 0-1 배낭 문제 자체는 NP-난해 문제입니다. 코딩 테스트에서 용량 범위가 10⁵ 이하로 주어지는 것은 이 DP를 쓰라는 신호입니다. 공간 최적화 (1차원 배열):
def knapsack_optimized(weights, values, capacity):
n = len(weights)
dp = [0] * (capacity + 1)
for i in range(n):
# 뒤에서부터 업데이트 (덮어쓰기 방지)
for w in range(capacity, weights[i] - 1, -1):
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 공간복잡도: O(n*capacity) → O(capacity)1차원으로 줄일 때 용량을 거꾸로 순회하는 것이 이 코드의 핵심이자 가장 흔한 버그 지점입니다. 2차원 버전의 dp[i][w]는 이전 행 dp[i-1][w - weight]를 참조합니다. 1차원 배열 하나를 덮어쓰면서 w를 작은 쪽부터 올라가면, dp[w - weight]가 이미 이번 물건을 반영해 갱신된 값이 되어 같은 물건을 여러 번 담는 결과가 나옵니다. 큰 w부터 내려가면 아직 갱신되지 않은 이전 행의 값을 읽게 됩니다.
재미있는 점은 순방향으로 순회하는 “버그 버전”이 정확히 완전 배낭(unbounded knapsack) 문제, 즉 각 물건을 무제한으로 담을 수 있는 문제의 정답이라는 것입니다. 루프 방향 하나로 문제의 의미가 바뀌므로, 공간 최적화 코드를 쓸 때는 “이 칸이 참조하는 값이 이번 단계 값이어야 하는가, 이전 단계 값이어야 하는가”를 반드시 확인해야 합니다. 앞의 FAQ에서 말한 것처럼 1차원으로 줄이면 어떤 물건을 골랐는지 복원할 수 없다는 대가도 있습니다.
DP 문제 접근법
1단계: DP인지 판단
✅ DP 신호:
- "최대/최소 값"
- "경우의 수"
- "가능 여부"
- 중복되는 부분 문제
❌ DP 아님:
- 그리디로 풀림
- 단순 시뮬레이션2단계: 점화식 세우기
# 예: 계단 오르기
# dp[i] = i번째 계단까지 가는 경우의 수
# dp[i] = dp[i-1] + dp[i-2]3단계: 초기값 설정
# 예: 계단 오르기
dp[1] = 1 # 1칸: 1가지
dp[2] = 2 # 2칸: 2가지 (1+1, 2)4단계: 구현 선택
# Top-Down: 재귀가 자연스러울 때
# Bottom-Up: 반복문이 명확할 때 (더 빠름)네 단계 중 가장 많은 시간을 써야 하는 것은 2단계 앞부분의 상태 정의입니다. 좋은 정의는 “dp[i]는 ~한 조건에서 ~의 최댓값”처럼 한 문장으로 말할 수 있고, 그 문장에 조건이 빠짐없이 들어 있어야 합니다. 예를 들어 “가장 긴 증가하는 부분 수열”에서 dp[i]를 “앞에서 i개 원소 중 가장 긴 증가 부분 수열의 길이”로 정의하면 점화식이 세워지지 않습니다. 다음 원소를 붙일 수 있는지 알려면 부분 수열의 마지막 원소가 무엇인지 알아야 하기 때문입니다. “i번째 원소로 끝나는 가장 긴 증가 부분 수열의 길이”로 정의를 바꾸면 dp[i] = max(dp[j] + 1) (j < i, a[j] < a[i])가 바로 나옵니다.
점화식을 세운 뒤에는 작은 입력으로 손 계산을 해 보는 것이 가장 확실한 검증입니다. n=1, 2, 3, 4 정도의 답을 직접 나열해 보고, 점화식이 같은 값을 내는지 확인합니다. 이 글의 계단 오르기 docstring에 n=1~5의 답을 적어 둔 것도 이 과정입니다.
DP 코드가 틀렸을 때 확인할 것
# DP 테이블 출력
def print_dp_table(dp):
for row in dp:
print(row)
# 중간 과정 확인
print(f"dp[{i}] = {dp[i]}")DP 코드가 틀렸을 때는 최종 답만 보면 원인을 찾기 어렵습니다. 작은 입력으로 테이블 전체를 출력해 손 계산 결과와 첫 번째로 달라지는 칸을 찾으면, 대부분 그 칸의 점화식 분기나 초기값, 참조 순서 중 하나가 원인입니다. 이 방법이 가장 빠르게 효과를 보는 것은 앞에서 말한 두 유형, 즉 경계(첫 행·첫 열) 처리를 빠뜨린 경우와 공간 최적화에서 순회 방향을 잘못 잡은 경우입니다.
작은 입력에서 맞는데 큰 입력에서 틀린다면 오버플로나 초기값의 크기를 의심합니다. 최솟값 DP에서 “아직 도달 불가”를 10**9로 두었는데 실제 답이 그보다 클 수 있거나, 그 값에 더하기를 하다 C++에서 int 범위를 넘는 경우가 흔합니다. 정답은 맞는데 시간 초과가 난다면, 같은 상태를 여러 번 계산하고 있지 않은지(메모이제이션 누락) 먼저 확인합니다. Top-Down 코드에서 memo에 저장하는 줄을 return 뒤에 두거나, 저장한 키와 조회하는 키가 다르면(memo[n]에 저장하고 memo[(n, k)]를 조회) 메모이제이션이 동작하지 않아 지수 시간으로 돌아갑니다.
Top-Down과 Bottom-Up 중 무엇으로 쓸지
점화식이 떠오르긴 했는데 어떤 순서로 채워야 할지 헷갈린다면 Top-Down(재귀 + 메모이제이션)으로 먼저 맞는 답을 만드는 것이 빠릅니다. 다만 Python에서는 재귀 깊이가 발목을 잡습니다. 1로 만들기(1463번)는 N이 10⁶까지라서 재귀로 짜면 기본 재귀 한도 1000을 한참 넘기므로, 이런 문제는 처음부터 반복문으로 표를 채우는 Bottom-Up이 맞습니다. 채우는 순서가 명확한 1차원·격자 DP는 Bottom-Up, 상태가 드문드문 필요해서 전부 채우기 아까운 문제는 Top-Down이라고 기준을 잡으면 됩니다.
백준:
프로그래머스:
같이 보면 좋은 글
- DP 패턴 | 동적 프로그래밍 유형별 풀이 전략
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐
- 그리디 알고리즘
- 백트래킹: 가지치기로 모든 경우의 수를 줄이는 방법과 N-Queen·순열·조합
자주 묻는 질문 (FAQ)
Q. Bottom-Up DP에서 테이블 전체를 저장하지 않고 공간을 줄일 수 있나요?
A. 점화식이 바로 앞의 몇 칸만 참조한다면 배열 전체 대신 그 값들만 변수로 들고 다니면 됩니다. 피보나치처럼 dp[i]가 dp[i-1]과 dp[i-2]만 쓰면 변수 두 개로 O(1) 공간이 되고, 2차원 DP도 이전 행만 쓰면 1차원 배열 하나로 줄일 수 있습니다. 다만 공간을 줄이면 중간 테이블이 사라져 실제 선택 경로를 복원하기 어려워지므로, 경로가 필요한 문제에서는 테이블을 남겨 두어야 합니다.