DP 패턴 | 동적 프로그래밍 유형별 풀이 전략 | 핵심 개념과 실전 활용
이 글의 핵심
DP 패턴: 동적 프로그래밍 유형별 풀이 전략. 1차원 DP 패턴·2차원 DP 패턴.
시리즈 안내
들어가며
”DP 문제는 패턴이다”
대부분의 DP 문제는 몇 가지 패턴의 변형입니다. 패턴을 익히면 새로운 문제도 쉽게 풀 수 있습니다.
코딩 테스트 준비하며 깨달은 것
알고리즘 문제를 풀다 보면 “이게 실무에 무슨 도움이 될까?” 하는 의문이 들 때가 있습니다. 저도 그랬습니다. 하지만 실제 프로젝트에서 성능 문제에 부딪히면, 알고리즘 지식이 얼마나 중요한지 깨닫게 됩니다. 예를 들어, 사용자 검색 기능이 느려서 고민하다가 해시 테이블을 적용하니 응답 시간이 10초에서 0.1초로 줄어든 경험이 있습니다. 코딩 테스트는 단순히 취업을 위한 관문이 아니라, 문제 해결 능력을 키우는 훈련장입니다. 처음엔 브루트 포스로 풀다가, 시간 복잡도를 개선하는 과정에서 “아, 이렇게 생각하면 되는구나” 하는 깨달음을 얻을 때의 쾌감은 말로 표현하기 어렵습니다. 이 글에서는 단순히 정답 코드만 제시하는 게 아니라, 문제를 어떻게 접근하고 최적화하는지 사고 과정을 함께 공유하겠습니다.
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)
- 패턴 인식: 문제 → 패턴 매칭
추천 문제
백준
관련 글
자주 묻는 질문 (FAQ)
Q. 이 내용을 실무에서 언제 쓰나요?
A. DP 패턴: 동적 프로그래밍 유형별 풀이 전략. 1차원 DP 패턴·2차원 DP 패턴로 흐름을 잡고 원리·코드·실무 적용을 한글로 정리합니다. 알고리즘·DP·동적프로그래밍 중심으로 설명합니다. Start now. 실무에서는 위 본문의 예제와 선택 가이드를 참고해 적용하면 됩니다.
Q. 선행으로 읽으면 좋은 글은?
A. 각 글 하단의 이전 글 또는 관련 글 링크를 따라가면 순서대로 배울 수 있습니다. C++ 시리즈 목차에서 전체 흐름을 확인할 수 있습니다.
Q. 더 깊이 공부하려면?
A. cppreference와 해당 라이브러리 공식 문서를 참고하세요. 글 말미의 참고 자료 링크도 활용하면 좋습니다.
같이 보면 좋은 글 (내부 링크)
이 주제와 연결되는 다른 글입니다.
- 동적 프로그래밍(DP) | 코딩 테스트 필수 알고리즘 완벽 정리
- DP 실전 문제 | 코딩 테스트 DP 문제 풀이 전략
- DP Patterns | Dynamic Programming Problem-Solving Strategies
이 글에서 다루는 키워드 (관련 검색어)
알고리즘, DP, 동적프로그래밍, 패턴, 코딩테스트, LCS, LIS 등으로 검색하시면 이 글이 도움이 됩니다.