# [06-04] 동적 계획법 (Dynamic Programming)
동적 계획법은 복잡한 문제를 작은 부분 문제로 나누고, 한 번 계산한 결과를 저장하여 중복 계산을 피하는 효율적인 알고리즘 설계 기법입니다.
🎯 동적 계획법 (Dynamic Programming, DP) 이란 무엇인가
동적 계획법의 기본 개념
동적 계획법은 큰 문제를 작은 부분 문제로 나누어 해결하되,
한 번 계산한 결과를 저장해두고 필요할 때 다시 사용하는 방법입니다.
실생활 비유:
수학 문제 풀기:
일반적인 방법:
- 같은 계산을 여러 번 반복
- (2+3) × 4를 계산할 때마다 2+3을 다시 계산
DP 방법:
- 2+3 = 5를 한 번 계산하고 메모
- 다음에는 "5 × 4"로 바로 계산
- 중복 계산 제거!또 다른 예시:
- 요리: 미리 손질해 둔 재료 사용 (매번 손질하지 않음)
- 학습: 공식을 외워두고 응용 (매번 유도하지 않음)
- 게임: 저장 포인트 활용 (처음부터 다시 하지 않음)
DP의 핵심 요소
동적 계획법이 적용되려면 두 가지 조건이 필요합니다:
1. 최적 부분 구조 (Optimal Substructure)
큰 문제의 최적해가 작은 문제의 최적해로 구성됩니다.
예: 서울 → 부산 최단거리 = 서울 → 대전 최단거리 + 대전 → 부산 최단거리
작은 문제의 최적해를 합치면 큰 문제의 최적해!2. 중복되는 부분 문제 (Overlapping Subproblems)
같은 부분 문제가 여러 번 반복됩니다.
예: 피보나치 수열
fib(5)를 계산하려면:
fib(5) = fib(4) + fib(3)
fib(4) = fib(3) + fib(2)
fib(3) = fib(2) + fib(1)
fib(3)이 2번, fib(2)가 3번 계산됨!
→ 중복 제거하면 빨라짐DP vs 분할 정복
둘 다 "작은 문제로 나눈다"는 공통점이 있지만, 차이가 있습니다:
분할 정복:
- 부분 문제가 독립적
- 중복 계산 없음
- 예: 병합 정렬
동적 계획법:
- 부분 문제가 중복됨
- 중복 계산 제거가 핵심
- 예: 피보나치
문제
/ \
부분1 부분2
/ \ / \
A B B C ← B가 중복!
분할 정복: B를 2번 계산
DP: B를 1번만 계산하고 저장📊 피보나치 수열
문제 설명
피보나치 수열은 DP를 설명하는 가장 기본적인 예시입니다.
F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2)
수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...문제: F(n)을 계산하세요.
방법 1: 순수 재귀 (비효율적)
def fib_recursive(n):
"""
피보나치 - 순수 재귀
문제점: 엄청난 중복 계산!
"""
# 기저 조건
if n <= 1:
return n
# 재귀 호출
return fib_recursive(n - 1) + fib_recursive(n - 2)
# 사용 예시
print(fib_recursive(5)) # 5
print(fib_recursive(10)) # 55
# print(fib_recursive(40)) # 매우 느림!문제점: 중복 계산
fib(5) 계산 과정:
fib(5)
/ \
fib(4) fib(3)
/ \ / \
fib(3) fib(2) fib(2) fib(1)
/ \ / \ / \
fib(2) fib(1) ...
fib(3): 2번 계산
fib(2): 3번 계산
fib(1): 5번 계산
총 함수 호출: 15번
시간복잡도: O(2^n) - 매우 느림!방법 2: 메모이제이션 (Memoization) → Top Down DP
메모이제이션은 동일한 계산을 반복해야 할 때,
이전에 계산한 결과값을 메모리에 저장해 두었다가 동일한 입력이 들어오면 재계산 없이 저장된 값을 반환하여
프로그램 실행 속도를 높이는 최적화 기법입니다.
def fib_memoization(n, memo=None):
"""
피보나치 - 메모이제이션 (Top-Down DP)
한 번 계산한 값을 memo에 저장, 필요할 때 다시 계산하지 않고 memo에서 가져옴
n: 구할 피보나치 수
memo: 계산 결과를 저장할 딕셔너리
Returns: F(n)
"""
# memo 초기화
if memo is None:
memo = {}
# 이미 계산한 값이면 바로 반환
if n in memo:
return memo[n]
# 기저 조건
if n <= 1:
return n
# 재귀 호출 + 결과 저장
memo[n] = fib_memoization(n - 1, memo) + fib_memoization(n - 2, memo)
return memo[n]
# 사용 예시
print(fib_memoization(5)) # 5
print(fib_memoization(10)) # 55
print(fib_memoization(100)) # 354224848179261915075 (빠름!)
시간복잡도: O(n)실행 과정:
fib_memo(5) 호출:
1. fib(5) 계산 필요
memo = {}
2. fib(4) 계산 필요
memo = {}
3. fib(3) 계산 필요
memo = {}
4. fib(2) 계산 필요
memo = {}
5. fib(1) = 1 (기저 조건)
memo = {1: 1}
6. fib(0) = 0 (기저 조건)
memo = {1: 1, 0: 0}
7. fib(2) = 1 + 0 = 1
memo = {1: 1, 0: 0, 2: 1}
8. fib(3) 계산 중... fib(1) 필요
memo에 있음! 1 사용
fib(3) = 1 + 1 = 2
memo = {1: 1, 0: 0, 2: 1, 3: 2}
9. fib(4) 계산 중... fib(2) 필요
memo에 있음! 1 사용
fib(4) = 2 + 1 = 3
memo = {1: 1, 0: 0, 2: 1, 3: 2, 4: 3}
10. fib(5) = 3 + 2 = 5
memo = {1: 1, 0: 0, 2: 1, 3: 2, 4: 3, 5: 5}
각 값을 단 1번만 계산!방법 3: 타뷸레이션 (Tabulation) → Bottom-Up DP
타뷸레이션은 작은 부분 문제부터 차례대로 해결하여 테이블(배열)에 저장하고,
이를 이용해 큰 문제를 해결하는 상향식 접근 방식입니다.
반복문을 사용하여 재귀 호출없이 데이터를 채워 나가며, 필요한 모든 값을 미리 계산하는 Eager-Evaluation 특성을 가집니다.
def fib_tabulation(n):
"""
피보나치 - 타뷸레이션 (Bottom-Up DP)
작은 문제(F(0), F(1))부터 시작해서 순서대로 F(n)까지 계산
n: 구할 피보나치 수
Returns: F(n)
"""
# 기저 조건
if n <= 1:
return n
# DP 테이블 초기화
dp = [0] * (n + 1)
dp[0] = 0 # F(0) = 0
dp[1] = 1 # F(1) = 1
# 작은 것부터 순서대로 계산
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 사용 예시
print(fib_tabulation(5)) # 5
print(fib_tabulation(10)) # 55
print(fib_tabulation(100)) # 354224848179261915075
시간복잡도: O(n)
공간복잡도: O(n)실행 과정:
fib_tab(5) 호출:
초기 상태:
dp = [0, 1, 0, 0, 0, 0]
↑ ↑
F(0) F(1)
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]
반환: dp[5] = 5방법 4: 공간 최적화
공간 최적화는 2차원 테이블(DP table) 전체를 저장하지 않고, 이전 단계의 결과(들)만 기억하여
O(N^2) 공간을 O(N) 또는 O(1)로 줄이는 기법입니다.
DP 테이블 전체가 필요 없다면 메모리를 절약할 수 있습니다.
def fib_optimized(n):
"""
피보나치 - 공간 최적화
F(n)을 계산할 때 F(n-1)과 F(n-2)만 필요 → 2개 변수만 사용
"""
if n <= 1:
return n
# 2개 변수만 유지
prev2 = 0 # F(n-2)
prev1 = 1 # F(n-1)
for i in range(2, n + 1):
current = prev1 + prev2
# 다음 단계를 위해 업데이트
prev2 = prev1
prev1 = current
return prev1
# 사용 예시
print(fib_optimized(5)) # 5
print(fib_optimized(100)) # 354224848179261915075
시간복잡도: O(n)
공간복잡도: O(1)피보나치 방법 비교
방법 시간 공간 장점
-------------------------------------------------
순수 재귀 O(2^n) O(n) 이해 쉬움
메모이제이션 O(n) O(n) 직관적
타뷸레이션 O(n) O(n) 반복문, 안정적
공간 최적화 O(n) O(1) 메모리 효율
n=40일 때:
순수 재귀: 수십 초
DP: 1ms 미만🪜 계단 오르기 문제
문제 설명
n개의 계단이 있습니다.
한 번에 1칸 또는 2칸씩 오를 수 있습니다.
n번째 계단에 도착하는 방법의 수는?
예:
n=1: 1가지 (1)
n=2: 2가지 (1+1, 2)
n=3: 3가지 (1+1+1, 1+2, 2+1)
n=4: 5가지 (1+1+1+1, 1+1+2, 1+2+1, 2+1+1, 2+2)점화식 찾기
핵심 통찰: n번째 계단에 도착하는 방법은?
n번째 계단에 도착하려면:
1. (n-1)번째 계단에서 1칸 오르기
2. (n-2)번째 계단에서 2칸 오르기
따라서:
dp[n] = dp[n-1] + dp[n-2]
이것은 피보나치와 같은 점화식!시각화:
계단 3개:
[3]
/ \
1칸/ \2칸
/ \
[2] [1]
/ \ |
1칸/ \2칸 1칸
/ \ |
[1] [0] [0]
|
1칸
|
[0]
dp[3] = dp[2] + dp[1]
dp[2] = dp[1] + dp[0]
dp[1] = dp[0] + dp[-1] (불가능하지만 1로 정의)
dp[0] = 1 (0번째는 이미 도착)구현
def climb_stairs(n):
"""
계단 오르기 - DP
점화식: dp[i] = dp[i-1] + dp[i-2]
n: 계단 수
Returns: n번째 계단에 도착하는 방법의 수
"""
# 기저 조건
if n <= 2:
return n
# DP 테이블
dp = [0] * (n + 1) # [0, 0, 0, ...] 0이 n + 1개인 배열
dp[1] = 1 # 1개 계단: 1가지
dp[2] = 2 # 2개 계단: 2가지
# Bottom-Up
for i in range(3, n + 1):
# i번째 계단 = (i-1)에서 1칸 + (i-2)에서 2칸
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
# 사용 예시
for i in range(1, 6):
print(f"{i}개 계단: {climb_stairs(i)}가지")
# 출력:
# 1개 계단: 1가지
# 2개 계단: 2가지
# 3개 계단: 3가지
# 4개 계단: 5가지
# 5개 계단: 8가지💰 동전 거스름돈 문제
문제 설명
동전 종류: [1원, 5원, 10원, 25원]
목표 금액: 11원
최소 몇 개의 동전으로 거슬러줄 수 있나?
정답: 2개 (10원 + 1원)주의: 이 문제는 그리디로 안 풀립니다!
반례:
동전: [1원, 3원, 4원]
목표: 6원
그리디 (큰 것부터):
4원 + 1원 + 1원 = 3개 ✗
최적해:
3원 + 3원 = 2개 ✓동적 계획법 (DP) 접근
핵심은 "마지막에 어떤 동전을 하나 딱 놓았을 때, 그전 단계까지의 최적해(최소 개수)는 무엇이었나?"를 찾는 것입니다.
i원을 만들려면:
1. 동전 하나를 사용하고
2. 나머지 금액을 만들면 됨
예: 11원을 만들려면?
- 1원 동전 사용 → 10원을 만들고 + 1개(1원)
- 5원 동전 사용 → 6원을 만들고 + 1개(5원)
- 10원 동전 사용 → 1원을 만들고 + 1개(10원)
이 중 가장 적은 개수!점화식:
dp[i] = i원을 만드는 최소 동전 개수
dp[i] = min(
dp[i - coin1] + 1,
dp[i - coin2] + 1,
dp[i - coin3] + 1,
...
)
여기서:
- dp[i - coin]: 동전을 사용하기 전 금액
- +1: 지금 사용하는 동전 1개
- min: 모든 경우 중 최소값구체적 예시: dp[11] 계산하기
동전: [1원, 5원, 10원, 25원]
목표: 11원 만들기
dp[11]을 구하려면, 사용 가능한 각 동전을 시도:
1. 1원 동전 사용:
11 - 1 = 10원이 필요
dp[11] = dp[10] + 1
의미: "10원 만드는 법을 알고 있다면, 1원 동전 1개 추가"
2. 5원 동전 사용:
11 - 5 = 6원이 필요
dp[11] = dp[6] + 1
의미: "6원 만드는 법을 알고 있다면, 5원 동전 1개 추가"
3. 10원 동전 사용:
11 - 10 = 1원이 필요
dp[11] = dp[1] + 1
의미: "1원 만드는 법을 알고 있다면, 10원 동전 1개 추가"
4. 25원 동전 사용:
11 - 25 = -14원 (음수!)
사용 불가 (금액보다 동전이 큼)
최종:
dp[11] = min(
dp[10] + 1, ← 10원을 만드는 방법 + 1원 동전
dp[6] + 1, ← 6원을 만드는 방법 + 5원 동전
dp[1] + 1 ← 1원을 만드는 방법 + 10원 동전
)단계별 이해:
왜 dp[10], dp[6], dp[1]을 사용하나?
dp[10]을 이미 계산했다면:
→ "10원을 최소 동전으로 만드는 방법을 안다" → 여기에 1원 동전 1개만 추가하면 11원!
dp[6]을 이미 계산했다면:
→ "6원을 최소 동전으로 만드는 방법을 안다" → 여기에 5원 동전 1개만 추가하면 11원!
dp[1]을 이미 계산했다면:
→ "1원을 최소 동전으로 만드는 방법을 안다" → 여기에 10원 동전 1개만 추가하면 11원!
이 중 가장 적은 개수를 선택!실제 계산 예시:
이미 계산된 값들:
dp[1] = 1 (1원 동전 1개)
dp[6] = 2 (5원 + 1원)
dp[10] = 1 (10원 동전 1개)
dp[11] 계산:
= min(
dp[10] + 1, → 1 + 1 = 2
dp[6] + 1, → 2 + 1 = 3
dp[1] + 1 → 1 + 1 = 2
)
= min(2, 3, 2)
= 2
답: 11원은 최소 2개 동전으로 가능
방법: 10원 + 1원 또는 1원 + 10원일반화:
for 각 금액 i in [1...목표금액]:
for 각 동전 coin in [사용 가능한 동전들]:
if i >= coin: # 이 동전을 사용할 수 있으면
dp[i] = min(dp[i], dp[i - coin] + 1) # 현재 최소값 vs (coin 사용 전 금액 + 1개)
이렇게 작은 금액부터 순서대로 계산하면,
큰 금액을 계산할 때 필요한 작은 금액의 답을 이미 알고 있습니다!구현
def coin_change(coins, amount):
"""
동전 거스름돈 - DP
목표 금액을 만드는 최소 동전 개수
coins: 동전 종류 리스트
amount: 목표 금액
Returns: 최소 동전 개수 (불가능하면 -1)
"""
# DP 테이블 초기화
# dp[i]: i원을 만드는 최소 동전 개수
dp = [float('inf')] * (amount + 1) # float('inf'): 양의 무한대, * (amount + 1): 리스트의 길이(인덱스 0,...,amount)
# dp는 min() 함수로 최솟값을 갱신할 것인데, 어떤 숫자가 들어와도 그 숫자가 '최솟값'이 될 수 있도록,
# 가장 큰 무한대로 초기화. 만약 0으로 초기화하면, min(0, 3)을 했을 때 0이 계속 남게 되어 계산이 망가짐.
dp[0] = 0 # 0원은 0개, 모든 계산의 기초가 되는 '기본값'으로 0원부터 차근차근 돈을 쌓아 올릴 예정.
# 1원부터 amount원까지 순서대로
for i in range(1, amount + 1):
for coin in coins: # 각 동전을 시도
if i >= coin: # 이 동전을 사용할 수 있으면
dp[i] = min(dp[i], dp[i - coin] + 1)
# dp[i - coin] + 1: 목표 금액(i)에서 coin을 썼을 때,
# 남은 돈 i-coin원을 만드는 최소 개수에 방금 쓴 coin 1개를 더함
# min(dp[i], dp[i - coin] + 1): 이미 계산된 다른 방법들과 비교해서 가장 작은 값을 골라 업데이트
# 결과
return dp[amount] if dp[amount] != float('inf') else -1
# 사용 예시
coins = [1, 5, 10, 25]
for amount in [11, 15, 27]:
result = coin_change(coins, amount)
print(f"{amount}원: {result}개")
# 출력:
# 11원: 2개 (10 + 1)
# 15원: 2개 (10 + 5)
# 27원: 3개 (25 + 1 + 1)실행 과정 (coins=[1,5,10,25], amount=11):
초기: dp = [0, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
i=1: 동전 1 사용 → dp[1] = dp[0] + 1 = 1
dp = [0, 1, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
i=2: 동전 1 사용 → dp[2] = dp[1] + 1 = 2
dp = [0, 1, 2, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞, ∞]
i=5: 동전 1 사용 → dp[5] = dp[4] + 1 = 5
동전 5 사용 → dp[5] = dp[0] + 1 = 1 (더 작음!)
dp = [0, 1, 2, 3, 4, 1, ∞, ∞, ∞, ∞, ∞, ∞]
i=10: 동전 1 사용 → dp[10] = dp[9] + 1 = 10
동전 5 사용 → dp[10] = dp[5] + 1 = 2
동전 10 사용 → dp[10] = dp[0] + 1 = 1 (최소!)
dp = [0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, ∞]
i=11: 동전 1 사용 → dp[11] = dp[10] + 1 = 2
동전 5 사용 → dp[11] = dp[6] + 1 = 3
동전 10 사용 → dp[11] = dp[1] + 1 = 2
dp = [0, 1, 2, 3, 4, 1, 2, 3, 4, 5, 1, 2]
답: dp[11] = 2🎒 0-1 배낭 문제
0-1 배낭 문제는 각 물건에 대해 '선택하거나(1)', '포기하거나(0)' 딱 두 가지의 선택지만 있는 문제입니다.
0-1의 구체적인 의미
- 1 (Keep): 그 물건을 통째로 배낭에 넣는다.
- 0 (Leave): 그 물건을 아예 넣지 않는다.
즉, 이 문제의 핵심은 "물건을 쪼갤 수 없다"는 데 있습니다.
예를 들어, 10kg짜리 금덩이가 하나 있는데 내 배낭에는 5kg의 여유밖에 없다면,
0-1 배낭 문제에서는 그 금덩이를 넣지 못하고 포기(0)해야 합니다.
문제 설명
배낭 용량: 10kg
물건 (무게, 가치):
A: 5kg, $10
B: 4kg, $40
C: 6kg, $30
D: 3kg, $50
목표: 최대 가치
제약: 각 물건은 0개 또는 1개만 (쪼갤 수 없음)그리디로 안 되는 이유:
가치/무게 비율로 정렬:
D: $50/3kg = 16.7
B: $40/4kg = 10
C: $30/6kg = 5
A: $10/5kg = 2
그리디: D(3kg, $50) + B(4kg, $40) = 7kg, $90
남은 용량: 3kg → A와 C 둘 다 못 담음
최적해: B(4kg, $40) + C(6kg, $30) = 10kg, $70
또는: D(3kg, $50) + B(4kg, $40) = 7kg, $90
실제 최적: D + B = $90 (그리디와 우연히 일치)
하지만 다른 경우에는 그리디 실패!DP 접근
2차원 DP 테이블:
핵심은 "현재 물건을 넣을까 말까?"를 고민할 때,
그 결정이 가져올 미래의 가치를 이전 단계의 기록(DP 테이블)을 보고 판단하는 것입니다.
dp[i][w] = 처음 i개 물건을 고려했을 때 용량 w에서의 최대 가치
선택지:
1. i번째 물건을 담지 않음 → dp[i][w] = dp[i-1][w] # 이전 상태 유지
2. i번째 물건을 담음 (가능하면) → dp[i][w] = dp[i-1][w - weight[i]] + value[i] # "i번째 물건을 넣고 남은 공간을 최적으로 채움
dp[i][w] = max(선택지 1, 선택지 2) # 목표는 가치의 극대화이므로 max를 사용, 숫자가 큰 쪽(이득인 쪽)을 선택하여 dp[i][w]에 기록구현
def knapsack_01(weights, values, capacity):
"""
0-1 배낭 문제 - DP
각 물건을 담거나 안 담거나 (쪼갤 수 없음)
weights: 물건들의 무게 리스트
values: 물건들의 가치 리스트
capacity: 배낭 용량
Returns: 최대 가치
"""
n = len(weights)
# DP 테이블 초기화
# dp[i][w]: 처음 i개 물건, 용량 w일 때 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
# Bottom-Up으로 테이블 채우기
for i in range(1, n + 1):
for w in range(capacity + 1):
# i-1번째 물건 (0-indexed)
weight = weights[i - 1]
value = values[i - 1]
# 선택 1: 이 물건을 담지 않음
dp[i][w] = dp[i - 1][w]
# 선택 2: 이 물건을 담음 (가능하면)
if w >= weight:
dp[i][w] = max(
dp[i][w], # 안 담는 경우
dp[i - 1][w - weight] + value # 담는 경우
)
return dp[n][capacity]
# 사용 예시
weights = [5, 4, 6, 3]
values = [10, 40, 30, 50]
capacity = 10
max_value = knapsack_01(weights, values, capacity)
print(f"최대 가치: ${max_value}")
# 최대 가치: $90DP 테이블 시각화 (일부):
물건: A(5kg,$10), B(4kg,$40), C(6kg,$30), D(3kg,$50)
용량: 10kg
w=0 1 2 3 4 5 6 7 8 9 10
i=0 0 0 0 0 0 0 0 0 0 0 0 (물건 없음)
i=1 0 0 0 0 0 10 10 10 10 10 10 (A만)
i=2 0 0 0 0 40 40 40 40 40 50 50 (A,B)
i=3 0 0 0 0 40 40 40 40 40 50 70 (A,B,C)
i=4 0 0 0 50 50 50 50 90 90 90 90 (A,B,C,D)
↑
답: 90
핵심 계산 예시 (i=4, w=7):
dp[4][7] = max(
dp[3][7], # D를 안 담음 = 40
dp[3][7-3] + 50 # D를 담음 = dp[3][4] + 50 = 40 + 50 = 90
) = 90📝 최장 공통 부분 수열 (Longest Common Subsequence, LCS)
최장 공통 부분 수열은 두 개 이상의 수열이 주어졌을 때, 모두의 부분 수열이 되는 가장 긴 공통된 수열을 찾는 알고리즘입니다.
단, 공통 부분 수열의 문자열은 연속일 필요는 없습니다.
* 최장 공통 문자열(Longest Common Substring)은 부분 문자열이 아니라 한번에 이어져 있는 문자열만 해당합니다.
"ABCDEF"와 "GABCHD" 의 최장 공통 부분 수열은 "ABCD" 이고, 최장 공통 문자열은 "ABC" 입니다.문제 설명
두 문자열의 공통 부분 수열 중 가장 긴 것을 찾습니다.
문자열1: "ABCDGH"
문자열2: "AEDFHR"
공통 부분 수열:
"A", "D", "H"
"AD", "AH", "DH"
"ADH" ← 최장 (길이 3)동적 계획법(DP) 접근
점화식:
두 문자열을 비교하며 "지금까지 본 문자들 중 겹치는 가장 긴 부분은 무엇인가?"를 기록하는 과정입니다.
dp[i][j] = str1[0:i]와 str2[0:j]의 LCS 길이 # dp[i][j]: 그 두 문자열 조각 사이의 가장 긴 공통 부분의 길이
# str1[0:i]: 첫 번째 문자열의 i번째 글자까지 잘랐을 때
# str2[0:j]: 두 번째 문자열의 j번째 글자까지 잘랐을 때
경우 1: str1[i-1] == str2[j-1] (문자 같음)
→ dp[i][j] = dp[i-1][j-1] + 1
경우 2: str1[i-1] != str2[j-1] (문자 다름)
→ dp[i][j] = max(dp[i-1][j], dp[i][j-1])구현
def lcs(str1, str2):
"""
최장 공통 부분 수열 (LCS) - DP
str1, str2: 비교할 두 문자열
Returns: (LCS 길이, LCS 문자열)
예시:
str1 = "ABCDGH"
str2 = "AEDFHR"
결과: (3, "ADH")
"""
m, n = len(str1), len(str2)
# DP 테이블 초기화
# dp[i][j] = str1의 처음 i개 문자와 str2의 처음 j개 문자의 LCS 길이
# 예: dp[3][2] = "ABC"와 "AE"의 LCS 길이 = 1
dp = [[0] * (n + 1) for _ in range(m + 1)] # [0] * (n + 1): 0이 n+1개 있는 리스트(행렬의 열이 됨)
# for _ in range(m + 1): 위 리스트 생성을 m+1번 반복(행렬의 행이 됨)
# + 1 : 인덱스를 0부터 m까지, 0부터 n까지 그대로 사용하기 위함
# ===== 1단계: DP 테이블 채우기 =====
# 작은 문제부터 순서대로 해결 (Bottom-Up)
for i in range(1, m + 1):
for j in range(1, n + 1):
# 현재 비교하는 문자
# i-1, j-1을 쓰는 이유: 인덱스는 0부터, dp는 1부터 사용하기 위해
char1 = str1[i - 1] # str1의 i번째 문자
char2 = str2[j - 1] # str2의 j번째 문자
# 경우 1: 두 문자가 같은 경우 이 문자를 LCS에 포함!
if char1 == char2:
# 이전 LCS 길이에 1을 더함
# 예: "ABC"와 "AEC"를 비교 중 C==C이면, "AB"와 "AE"의 LCS + 1
# 왜 dp[i-1][j-1] → 이 문자를 제외한 나머지 부분의 LCS
dp[i][j] = dp[i - 1][j - 1] + 1
# 경우 2: 두 문자가 다른 경우 이 문자는 LCS에 포함되지 않음
else:
# 둘 중 하나를 제외했을 때의 최댓값 선택
# dp[i-1][j]: str1의 현재 문자 제외
# dp[i][j-1]: str2의 현재 문자 제외
# 예: "ABC"와 "AED"를 비교 중 C != D이면 "AB"와 "AED"의 LCS vs "ABC"와 "AE"의 LCS 중 더 큰 값
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
# 여기까지 오면 dp[m][n]에 최종 LCS 길이가 저장됨
# ===== 2단계: LCS 문자열 역추적 =====
# DP 테이블을 거꾸로 따라가며 실제 문자열 찾기
lcs_str = ""
i, j = m, n # 끝에서 시작
# 시작점(0,0)에 도달할 때까지
while i > 0 and j > 0:
# 경우 1: 현재 두 문자가 같은 경우 이 문자가 LCS에 포함됨!
if str1[i - 1] == str2[j - 1]:
# 왜 앞에 붙이나? → 역순으로 탐색하므로 뒤에서 앞으로
# 예: 현재 'H'를 찾음. lcs_str = "H" + "" = "H"
# 다음 'D'를 찾음. lcs_str = "D" + "H" = "DH"
lcs_str = str1[i - 1] + lcs_str
i -= 1 # 대각선 위로 이동 (둘 다 한 칸씩 뒤로), 이 문자를 사용했으므로 둘 다 제외
j -= 1
# 경우 2: 두 문자가 다른 경우 어느 쪽에서 왔는지 확인
elif dp[i - 1][j] > dp[i][j - 1]: # 위쪽 값이 크면 → str1의 현재 문자는 LCS에 없었음 → 위로 이동(str1만 한 칸 뒤로)
i -= 1
else: # 왼쪽 값이 더 크거나 같으면 → str2의 현재 문자는 LCS에 없었음 → 왼쪽으로 이동 (str2만 한 칸 뒤로)
j -= 1
# 최종 결과 반환
return dp[m][n], lcs_str
# ===== 실행 예시로 이해하기 =====
str1 = "AC" (길이 2)
str2 = "ABC" (길이 3)
# DP 테이블 채우기 과정:
#
# "" A B C
# "" 0 0 0 0 ← 빈 문자열과의 LCS는 항상 0
# A 0 1 1 1 ← A==A이므로 dp[1][1] = dp[0][0] + 1 = 1
# C 0 1 1 2 ← C==C이므로 dp[2][3] = dp[1][2] + 1 = 2
# ↑
# 빈 문자열과의 LCS는 항상 0
# LCS 길이: 2
# 역추적 과정:
#
# 시작: (2, 3) - dp[2][3] = 2
# str1[1]='C', str2[2]='C' → 같음!
# lcs_str = "C", (1, 2)로 이동
#
# (1, 2) - dp[1][2] = 1
# str1[0]='A', str2[1]='B' → 다름
# dp[0][2]=0 < dp[1][1]=1 → 왼쪽으로
# (1, 1)로 이동
#
# (1, 1) - dp[1][1] = 1
# str1[0]='A', str2[0]='A' → 같음!
# lcs_str = "A" + "C" = "AC", (0, 0)으로 이동
#
# (0, 0) → 종료
#
# LCS: "AC"
# 사용 예시
str1 = "ABCDGH"
str2 = "AEDFHR"
length, sequence = lcs(str1, str2)
print(f"LCS 길이: {length}")
print(f"LCS: {sequence}")
# 출력:
# LCS 길이: 3
# LCS: ADHDP 테이블 시각화:
str1 = "ABCDGH"
str2 = "AEDFHR"
"" A E D F H R
"" 0 0 0 0 0 0 0
A 0 1 1 1 1 1 1
B 0 1 1 1 1 1 1
C 0 1 1 1 1 1 1
D 0 1 1 2 2 2 2
G 0 1 1 2 2 2 2
H 0 1 1 2 2 3 3
↑
LCS 길이: 3
역추적 (H에서 시작):
(6,5): H==H → "H" 추가, (5,4)로
(5,4): G!=F, dp[4][4]=2 > dp[5][3]=2 → (4,4)로
(4,4): D!=F, dp[3][4]=1 < dp[4][3]=2 → (4,3)로
(4,3): D==D → "D" 추가, (3,2)로
(3,2): C!=E, dp[2][2]=1 = dp[3][1]=1 → (3,1)로
(3,1): C!=A, dp[2][1]=1 > dp[3][0]=0 → (2,1)로
(2,1): B!=A, dp[1][1]=1 > dp[2][0]=0 → (1,1)로
(1,1): A==A → "A" 추가, (0,0)로 → 종료
LCS: "ADH"💡 실무 팁
동적 계획법(DP)을 사용할 때
- 최적 부분 구조 확인: 작은 문제의 최적해가 큰 문제에 사용되는가?
- 중복 부분 문제 확인: 같은 계산이 반복되는가?
- 점화식 도출: 작은 문제와 큰 문제의 관계는?
Top-Down vs Bottom-Up
Top-Down (메모이제이션):
장점: 필요한 것만 계산, 직관적
단점: 재귀 스택 오버플로우 위험
Bottom-Up (타뷸레이션):
장점: 반복문으로 안정적, 일반적으로 더 빠름
단점: 불필요한 것도 계산할 수 있음
추천: 일반적으로 Bottom-Up 사용공간 최적화
- 이전 행/열만 필요하면 1차원 배열로 축소
- 슬라이딩 윈도우 기법 활용
디버깅 팁
- 작은 예제로 손으로 DP 테이블 그려보기
- 기저 조건(base case) 확인
- 점화식이 올바른지 검증
🎯 핵심 정리
동적 계획법의 본질
- 작은 문제의 해를 저장하여 재사용
- 중복 계산 제거가 핵심
- 최적 부분 구조 + 중복 부분 문제
주요 문제 유형
문제 점화식 시간복잡도
-----------------------------------------------------
피보나치 dp[n] = dp[n-1] + dp[n-2] O(n)
계단 오르기 dp[n] = dp[n-1] + dp[n-2] O(n)
동전 거스름돈 dp[i] = min(...) O(n×m)
0-1 배낭 dp[i][w] = max(...) O(n×W)
LCS dp[i][j] = ... O(m×n)DP vs 다른 기법
그리디:
- 지역 최적 → 전역 최적 (보장 안 됨)
- 빠름, 간단
- 예: 동전 (특정 조건)
DP:
- 모든 경우 고려 → 전역 최적 보장
- 느림, 복잡
- 예: 동전 (일반)
분할 정복:
- 독립적 부분 문제
- 중복 없음
- 예: 병합 정렬🔗 다음 글에서는
[06-05] 백트래킹 (Backtracking)
- 백트래킹의 개념: 가능성이 없는 경로를 조기에 포기하는 탐색 기법
- N-Queen 문제: 체스판에 퀸을 배치하는 고전적인 백트래킹 문제
- 스도쿠 풀이: 제약 조건을 만족하며 빈 칸을 채우는 방법
- 가지치기 최적화: 불필요한 탐색을 줄여 성능 향상시키기
이전 글: [06-03] 그리디
다음 글: [06-05] 백트래킹
시리즈: P1. Computer Science 기초
AI 전문가를 꿈꾸는 도전자