DP 패턴 | 동적 프로그래밍 유형별 풀이 전략
이 글의 핵심
DP 패턴에 대한 실전 가이드입니다. 동적 프로그래밍 유형별 풀이 전략 등을 예제와 함께 상세히 설명합니다.
들어가며
”DP 문제는 패턴이다”
대부분의 DP 문제는 몇 가지 패턴의 변형입니다. 패턴을 익히면 새로운 문제도 쉽게 풀 수 있습니다.
1. 1차원 DP 패턴
1차원 DP에서 dp[i]는 보통 “첫 번째부터 i번째까지” 또는 “길이 i인 부분 문제의 최적값”을 뜻합니다. 아래 두 예는 이전 칸의 값만으로 다음 칸을 채우는 대표 패턴입니다.
패턴 1: 이전 값 활용
def climb_stairs(n):
"""
계단 오르기 (1칸 또는 2칸)
dp[i] = dp[i-1] + dp[i-2]
"""
if n <= 2:
return n
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]
return dp[n]
print(climb_stairs(5)) # 8패턴 2: 최대/최소 선택
def rob(houses):
"""
집 털기 (인접한 집은 털 수 없음)
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
"""
if not houses:
return 0
if len(houses) == 1:
return houses[0]
dp = [0] * len(houses)
dp[0] = houses[0]
dp[1] = max(houses[0], houses[1])
for i in range(2, len(houses)):
dp[i] = max(dp[i-1], dp[i-2] + houses[i])
return dp[-1]
# 테스트
print(rob([2, 7, 9, 3, 1])) # 12 (2+9+1)2. 2차원 DP 패턴
패턴 1: 격자 경로
def unique_paths(m, n):
"""
m×n 격자에서 경로의 수
dp[i][j] = dp[i-1][j] + dp[i][j-1]
"""
dp = [[1] * n for _ in range(m)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[m-1][n-1]
print(unique_paths(3, 7)) # 28패턴 2: LCS (최장 공통 부분 수열)
def lcs(s1, s2):
"""
Longest Common Subsequence
"ABCDGH", "AEDFHR" → "ADH" (길이 3)
"""
m, n = len(s1), len(s2)
dp = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if s1[i-1] == s2[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(lcs("ABCDGH", "AEDFHR")) # 33. 배낭 문제 패턴
0-1 배낭
def knapsack_01(weights, values, capacity):
"""
각 물건을 0개 또는 1개만
"""
n = len(weights)
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, 3, 4, 5]
values = [3, 4, 5, 6]
capacity = 8
print(knapsack_01(weights, values, capacity)) # 10무한 배낭
def knapsack_unbounded(weights, values, capacity):
"""
각 물건을 무한대로
"""
dp = [0] * (capacity + 1)
for w in range(capacity + 1):
for i in range(len(weights)):
if weights[i] <= w:
dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
return dp[capacity]
# 테스트
weights = [1, 3, 4]
values = [15, 50, 60]
capacity = 8
print(knapsack_unbounded(weights, values, capacity)) # 1204. LIS (최장 증가 부분 수열)
O(n²) 풀이
def lis_n2(arr):
"""
Longest Increasing Subsequence
[10, 9, 2, 5, 3, 7, 101, 18] → 4 ([2,3,7,18])
"""
n = len(arr)
dp = [1] * n
for i in range(1, n):
for j in range(i):
if arr[j] < arr[i]:
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
# 테스트
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_n2(arr)) # 4O(n log n) 풀이
import bisect
def lis_nlogn(arr):
"""
이진 탐색 활용
"""
dp = []
for num in arr:
pos = bisect.bisect_left(dp, num)
if pos == len(dp):
dp.append(num)
else:
dp[pos] = num
return len(dp)
# 테스트
arr = [10, 9, 2, 5, 3, 7, 101, 18]
print(lis_nlogn(arr)) # 4실전 팁
DP 패턴 인식
# 1. 1D DP
# - 이전 값 활용: dp[i] = f(dp[i-1], dp[i-2])
# - 예: 피보나치, 계단 오르기
# 2. 2D DP
# - 격자: dp[i][j] = f(dp[i-1][j], dp[i][j-1])
# - 문자열: dp[i][j] = f(s1[i], s2[j])
# - 예: LCS, 편집 거리
# 3. 배낭
# - 선택/비선택: dp[i][w] = max(안넣음, 넣음)
# - 예: 0-1 배낭, 동전 문제정리
핵심 요약
- 1D DP: 이전 값 활용, 최대/최소 선택
- 2D DP: 격자, LCS, 배낭
- LIS: O(n²) 또는 O(n log n)
- 패턴 인식: 문제 → 패턴 매칭
추천 문제
백준:
프로그래머스:
관련 글
- 동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
- 알고리즘 시리즈 전체 목차
- 배열과 리스트
- 스택과 큐