동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
이 글의 핵심
동적 프로그래밍(DP)에 대한 실전 가이드입니다. 코딩 테스트 필수 알고리즘 완벽 정리 등을 예제와 함께 상세히 설명합니다.
들어가며
”같은 계산을 반복하지 마세요”
동적 프로그래밍(DP)은 중복 계산을 저장해서 O(2ⁿ) → O(n)으로 최적화하는 기법입니다.
사전 지식 (초보자를 위한 기초)
1. 재귀(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재귀의 핵심:
- 기저 조건: 재귀를 멈추는 조건 (없으면 무한 반복!)
- 재귀 호출: 문제를 작은 문제로 쪼개서 해결
2. 중복 계산 문제
재귀를 사용하면 같은 계산을 여러 번 하게 됩니다.
# 피보나치 수열: 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)을 계산하면 10억 번 이상 계산- 컴퓨터가 수십 초 걸림
3. 동적 프로그래밍(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) 비교:
# 일반 재귀: 10억 번 계산 (수십 초)
# DP: 40번만 계산 (즉시)4. DP를 사용하는 문제의 특징
DP는 다음 2가지 조건이 있을 때 사용합니다:
1) 최적 부분 구조 (Optimal Substructure)
- 큰 문제의 답이 작은 문제의 답으로 구할 수 있음
- 예:
fib(5) = fib(4) + fib(3)
2) 중복되는 부분 문제 (Overlapping Subproblems)
- 같은 작은 문제를 여러 번 계산함
- 예:
fib(3)을 여러 번 계산
DP 문제 키워드:
- “최대/최소 값 구하기”
- “경우의 수 구하기”
- “가능한지 판단하기”
- 피보나치, 계단 오르기, 배낭 문제 등
5. 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: 더 빠름, 메모리 효율적
1. 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)2. 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): 2^40 = 약 1조 번 계산 (수십 초)
# fib_memo(40): 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 데코레이터
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)) # 매우 빠름3. 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을 더 많이 사용공간 최적화
# ✅ 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))4. 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]만 필요하므로
# 전체 배열을 유지할 필요 없음패턴 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)패턴 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공간 최적화 (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)5. 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: 반복문이 명확할 때 (더 빠름)실전 팁
디버깅 팁
# DP 테이블 출력
def print_dp_table(dp):
for row in dp:
print(row)
# 중간 과정 확인
print(f"dp[{i}] = {dp[i]}")최적화 팁
# 1. 공간 최적화: 이전 행만 필요하면 1차원 배열
# 2. 시간 최적화: 불필요한 계산 스킵
# 3. 메모 초기화: defaultdict 활용정리
핵심 요약
- DP: 중복 계산 저장, O(2ⁿ) → O(n)
- Top-Down: 재귀 + 메모이제이션
- Bottom-Up: 반복문 + 테이블 (더 빠름)
- 점화식: dp[i] = f(dp[i-1], dp[i-2], …)
추천 문제
백준:
프로그래머스:
관련 글
- DP 패턴 | 동적 프로그래밍 유형별 풀이 전략
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐