개념
DP (Dynamic Programming) - 큰 문제를 작은 문제로 나누어 해결
중복되는 부분 문제의 결과를 저장하여 재사용
시간복잡도
| 방법 | 시간복잡도 | 공간복잡도 |
|---|---|---|
| 일반 재귀 | O(2^n) ~ O(n!) | O(n) |
| DP (메모이제이션) | O(n) ~ O(n²) | O(n) |
| DP (타뷸레이션) | O(n) ~ O(n²) | O(n) |
특징
DP를 사용하는 조건
-
최적 부분 구조 (Optimal Substructure)
- 큰 문제의 최적해가 작은 문제의 최적해로 구성
-
중복되는 부분 문제 (Overlapping Subproblems)
- 같은 부분 문제가 여러 번 계산됨
장점
- 시간 단축: 지수 시간 → 다항 시간
- 최적해 보장: 모든 경우를 고려
단점
- 메모리 사용: 결과 저장 공간 필요
- 문제 분석: DP 식 도출이 어려울 수 있음
구현 방법
1. 메모이제이션 (Memoization) - Top-Down
재귀 + 캐싱
# 피보나치 - 메모이제이션
def fibonacci_memo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibonacci_memo(n-1, memo) + fibonacci_memo(n-2, memo)
return memo[n]
print(fibonacci_memo(10)) # 55
# 시간복잡도: O(n)
# 공간복잡도: O(n)2. 타뷸레이션 (Tabulation) - Bottom-Up
반복문 + 배열
# 피보나치 - 타뷸레이션
def fibonacci_tab(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
print(fibonacci_tab(10)) # 55
# 시간복잡도: O(n)
# 공간복잡도: O(n)3. 공간 최적화
# 피보나치 - 공간 O(1)
def fibonacci_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(fibonacci_optimized(10)) # 55
# 시간복잡도: O(n)
# 공간복잡도: O(1)자주 나오는 문제 유형
1. 계단 오르기
문제: n개의 계단을 1칸 또는 2칸씩 오르는 방법의 수
def climb_stairs(n):
if n <= 2:
return n
dp = [0] * (n + 1)
dp[1] = 1
dp[2] = 2
for i in range(3, n + 1):
dp[i] = dp[i-1] + dp[i-2]
return dp[n]
# 테스트
print(climb_stairs(5)) # 8
# 시간복잡도: O(n)
# 공간복잡도: O(n)점화식: dp[i] = dp[i-1] + dp[i-2]
2. 배낭 문제 (0/1 Knapsack)
문제: 무게와 가치가 있는 물건들을 배낭에 넣어 가치 최대화
def knapsack(weights, values, capacity):
n = len(weights)
# dp[i][w]: i번째까지 물건, 무게 w일 때 최대 가치
dp = [[0] * (capacity + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for w in range(capacity + 1):
# 현재 물건을 넣지 않는 경우
dp[i][w] = dp[i-1][w]
# 현재 물건을 넣는 경우
if weights[i-1] <= w:
dp[i][w] = max(dp[i][w],
dp[i-1][w-weights[i-1]] + values[i-1])
return dp[n][capacity]
# 테스트
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
print(knapsack(weights, values, 5)) # 37
# 시간복잡도: O(n × capacity)
# 공간복잡도: O(n × capacity)핵심: 각 물건을 넣을지 말지 결정
3. 최장 증가 부분 수열 (LIS)
문제: 주어진 수열에서 증가하는 가장 긴 부분 수열의 길이
def longest_increasing_subsequence(nums):
if not nums:
return 0
n = len(nums)
dp = [1] * n # dp[i]: i를 마지막으로 하는 LIS 길이
for i in range(1, n):
for j in range(i):
if nums[j] < nums[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 테스트
print(longest_increasing_subsequence([10, 9, 2, 5, 3, 7, 101, 18])) # 4
# LIS: [2, 3, 7, 101] 또는 [2, 3, 7, 18]
# 시간복잡도: O(n²)
# 공간복잡도: O(n)점화식: dp[i] = max(dp[j] + 1) (j < i이고 nums[j] < nums[i])
4. 최장 공통 부분 수열 (LCS)
문제: 두 문자열의 최장 공통 부분 수열 길이
def longest_common_subsequence(text1, text2):
m, n = len(text1), len(text2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if text1[i-1] == text2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
return dp[m][n]
# 테스트
print(longest_common_subsequence("abcde", "ace")) # 3
# 시간복잡도: O(m × n)
# 공간복잡도: O(m × n)점화식:
text1[i] == text2[j]:dp[i][j] = dp[i-1][j-1] + 1- 다르면:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
5. 편집 거리 (Edit Distance)
문제: 문자열을 변환하는데 필요한 최소 연산 횟수
def edit_distance(word1, word2):
m, n = len(word1), len(word2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
# 초기화
for i in range(m + 1):
dp[i][0] = i
for j in range(n + 1):
dp[0][j] = j
for i in range(1, m + 1):
for j in range(1, n + 1):
if word1[i-1] == word2[j-1]:
dp[i][j] = dp[i-1][j-1]
else:
dp[i][j] = min(
dp[i-1][j] + 1, # 삭제
dp[i][j-1] + 1, # 삽입
dp[i-1][j-1] + 1 # 교체
)
return dp[m][n]
# 테스트
print(edit_distance("horse", "ros")) # 3
# 시간복잡도: O(m × n)
# 공간복잡도: O(m × n)핵심: 삽입, 삭제, 교체 연산 중 최소 선택
6. 동전 교환 (Coin Change)
문제: 동전으로 금액을 만드는 최소 개수
def coin_change(coins, amount):
dp = [float('inf')] * (amount + 1)
dp[0] = 0
for coin in coins:
for i in range(coin, amount + 1):
dp[i] = min(dp[i], dp[i - coin] + 1)
return dp[amount] if dp[amount] != float('inf') else -1
# 테스트
print(coin_change([1, 2, 5], 11)) # 3 (5+5+1)
# 시간복잡도: O(amount × len(coins))
# 공간복잡도: O(amount)점화식: dp[i] = min(dp[i], dp[i-coin] + 1)
추천 연습 문제
기초
중급
고급
핵심 요약
| 개념 | 설명 |
|---|---|
| 원리 | 중복 부분 문제의 결과 저장 |
| 방법 | 메모이제이션, 타뷸레이션 |
| 시간복잡도 | 지수 → 다항 시간으로 개선 |
| 활용 | 최적화 문제, 경우의 수 |
DP 문제 해결 템플릿
1. 1차원 DP
def dp_1d(n):
dp = [0] * (n + 1)
# 초기값 설정
dp[0] = base_case
# 점화식 적용
for i in range(1, n + 1):
dp[i] = f(dp[i-1], dp[i-2], ...)
return dp[n]2. 2차원 DP
def dp_2d(n, m):
dp = [[0] * (m + 1) for _ in range(n + 1)]
# 초기값 설정
for i in range(n + 1):
dp[i][0] = base_case
# 점화식 적용
for i in range(1, n + 1):
for j in range(1, m + 1):
dp[i][j] = f(dp[i-1][j], dp[i][j-1], ...)
return dp[n][m]3. 공간 최적화
def dp_optimized(n):
# 이전 값만 필요한 경우
prev = base_case
for i in range(1, n + 1):
current = f(prev)
prev = current
return currentDP vs 그리디 vs 분할정복
| 특성 | DP | 그리디 | 분할정복 |
|---|---|---|---|
| 접근 | 모든 경우 고려 | 현재 최선 선택 | 독립적 부분문제 |
| 최적해 | 보장 | 보장 안 됨 | 보장 |
| 중복 | 중복 있음 | 없음 | 없음 |
| 예시 | 배낭, LCS | 동전 거스름돈 | 병합 정렬 |
주의사항
1. 초기값 설정
# 최댓값 문제
dp = [0] * n
# 최솟값 문제
dp = [float('inf')] * n
dp[0] = 02. 인덱스 범위
# 1-based vs 0-based 주의
dp = [0] * (n + 1) # n까지 사용3. 메모리 초과
# 2차원 → 1차원으로 최적화
# dp[i][j] → dp[j] (이전 행만 필요한 경우)4. 점화식 도출
# 1. 작은 예제로 패턴 찾기
# 2. 이전 상태와의 관계 파악
# 3. 점화식 작성
# 4. 초기값 설정DP 최적화 기법
1. 슬라이딩 윈도우
# 일정 범위만 유지
for i in range(n):
# 최근 k개만 사용
window = dp[max(0, i-k):i+1]2. 비트마스킹 DP
# 상태를 비트로 표현
dp = [0] * (1 << n)3. 분할 정복 최적화
# Convex Hull Trick, Divide and Conquer OptimizationDP 문제 풀이 단계
-
DP 적용 가능 확인
- 최적 부분 구조
- 중복되는 부분 문제
-
상태 정의
dp[i]: i일 때의 최적값dp[i][j]: i, j일 때의 최적값
-
점화식 도출
- 이전 상태로부터 현재 상태 계산
-
초기값 설정
- Base case 정의
-
구현 및 최적화
- 메모이제이션 or 타뷸레이션
- 공간 최적화 고려