1️⃣ 2차원 DP란?
개념
상태를 2개의 변수로 표현해야 할 때 사용하는 DP.
dp[i][j]로 정의하며, 두 가지 조건이 동시에 영향을 줄 때 쓰임
1차원 DP와 차이:
1차원 dp[i] → "i번째 원소까지 봤을 때의 최적값" 2차원 dp[i][j] → "i번째 원소까지 봤고, 현재 상태가 j일 때의 최적값"
2차원 DP가 필요한 신호
✅ 두 문자열/수열을 동시에 비교할 때 → LCS
✅ 물건을 넣을지 말지 + 남은 용량이 있을 때 → 배낭 문제
✅ 구간 [i, j]에서의 최적값을 구할 때 → 구간 DP
✅ 행렬을 이동하며 최적값을 구할 때 → 격자 DP
2️⃣ LCS (Longest Common Subsequence, 최장 공통 부분 수열)
개념
두 문자열에서 공통으로 등장하는 부분 수열 중 가장 긴 것을 찾기. 부분 수열은 연속하지 않아도 되고, 순서만 유지하면 됨
예시:
A = "ACAYKP" B = "CAPCAK" LCS = "ACAK" (길이 4) A에서 A(0), C(1), A(2), K(4) 순서로 뽑고 B에서 C(0), A(1 or 5), C(3→아님)... → "ACAK"
dp 정의 & 점화식
dp[i][j] = A의 i번째까지, B의 j번째까지 봤을 때 LCS의 길이
점화식:
A[i] == B[j] 이면: dp[i][j] = dp[i-1][j-1] + 1
A[i] != B[j] 이면: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
LCS 구현
def lcs(A, B):
n, m = len(A), len(B)
# 1-indexed로 편하게 쓰기 위해 크기를 n+1, m+1로
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i-1] == B[j-1]: # 같으면 대각선 + 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[n][m]
A = "ACAYKP"
B = "CAPCAK"
print(lcs(A, B)) # 4
dp 테이블 시각화 (A="ACAK", B="CAK"):
"" C A K "" 0 0 0 0 A 0 0 1 1 C 0 1 1 1 A 0 1 2 2 K 0 1 2 3 ← 정답!
LCS 경로 역추적 (실제 수열 출력)
def lcs_trace(A, B):
n, m = len(A), len(B)
dp = [[0] * (m + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
for j in range(1, m + 1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
# 역추적
result = []
i, j = n, m
while i > 0 and j > 0:
if A[i-1] == B[j-1]:
result.append(A[i-1])
i -= 1
j -= 1
elif dp[i-1][j] > dp[i][j-1]:
i -= 1
else:
j -= 1
return ''.join(reversed(result))
print(lcs_trace("ACAYKP", "CAPCAK")) # ACAK
3️⃣ 0/1 배낭 문제 (Knapsack Problem)
개념
N개의 물건 (무게 w, 가치 v)이 있고, 배낭의 최대 용량이 K일 때 배낭에 넣을 수 있는 물건들의 가치 합의 최댓값을 구해라. 단, 각 물건은 한 번만 담을 수 있음
🎒 왜 그리디가 안 되냐?
가치/무게 비율이 높은 것부터 선택하면 최적이 아닐 수 있다!
예: (무게 5, 가치 10), (무게 3, 가치 6), (무게 3, 가치 6), 용량 6
→ 비율 기준: (5,10)먼저 → 가치 10, 근데 (3,6)+(3,6)=12가 최적!
dp 정의 & 점화식
dp[i][j] = i번째 물건까지 고려하고 배낭 용량이 j일 때 최대 가치
점화식:
물건 i를 안 넣을 때: dp[i][j] = dp[i-1][j]
물건 i를 넣을 때: dp[i][j] = dp[i-1][j - w[i]] + v[i] (j >= w[i]일 때만)
→ dp[i][j] = max(dp[i-1][j], dp[i-1][j-w[i]] + v[i])
배낭 구현
def knapsack(items, K):
# items = [(weight, value), ...]
n = len(items)
dp = [[0] * (K + 1) for _ in range(n + 1)]
for i in range(1, n + 1):
w, v = items[i-1]
for j in range(K + 1):
# 물건 i를 안 넣는 경우
dp[i][j] = dp[i-1][j]
# 물건 i를 넣는 경우 (용량이 충분할 때만)
if j >= w:
dp[i][j] = max(dp[i][j], dp[i-1][j-w] + v)
return dp[n][K]
items = [(6, 13), (4, 8), (3, 6), (5, 12)]
K = 7
print(knapsack(items, K)) # 14
dp 테이블 시각화 (물건 2개: (w=3,v=6), (w=4,v=8), K=7):
j: 0 1 2 3 4 5 6 7 i=0: 0 0 0 0 0 0 0 0 i=1: 0 0 0 6 6 6 6 6 ← (3,6) 고려 i=2: 0 0 0 6 8 8 8 14 ← (4,8) 고려, j=7: 6+8=14!
1차원 배열로 최적화
def knapsack_1d(items, K):
dp = [0] * (K + 1)
for w, v in items:
# 역순으로 순회! (같은 물건을 2번 쓰는 걸 방지)
for j in range(K, w - 1, -1):
dp[j] = max(dp[j], dp[j - w] + v)
return dp[K]
# 역순으로 순회하는 이유:
# 정순이면 dp[j-w]가 이미 이번 물건을 넣은 상태일 수 있음 (중복 사용)
# 역순이면 dp[j-w]는 무조건 이전 물건까지만 고려한 값
4️⃣ 구간 DP (Interval DP)
개념
구간 [i, j]에 대한 최적값을 구하는 DP. "전체 구간을 어떤 기준으로 나누면 최적인가?" 를 탐색한다
핵심 발상:
dp[i][j] = 구간 [i, j]를 처리하는 최적값 → 어떤 중간 지점 k로 나눌지 탐색 → dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + cost)
예시 - 연속합 최대 구간 (Kadane's Algorithm)
# 1차원이지만 구간 DP 사고방식
# dp[i] = i번째 원소로 끝나는 부분 배열의 최대 합
def max_subarray(arr):
dp = [0] * len(arr)
dp[0] = arr[0]
for i in range(1, len(arr)):
# arr[i]만 선택 vs 이전 합에 arr[i] 추가
dp[i] = max(arr[i], dp[i-1] + arr[i])
return max(dp)
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print(max_subarray(arr)) # 6 (4 + -1 + 2 + 1)
예시 - 파일 합치기 (구간 DP 전형)
k개 파일을 하나로 합칠 때 드는 최소 비용 (두 파일 합치는 비용 = 두 파일 크기의 합)
def file_merge(files):
n = len(files)
# prefix sum으로 구간 합을 빠르게 계산
prefix = [0] * (n + 1)
for i in range(n):
prefix[i+1] = prefix[i] + files[i]
# dp[i][j] = 파일 i~j를 합치는 최소 비용
dp = [[0] * n for _ in range(n)]
# 구간 길이 l을 2부터 n까지 늘려가며 채움
for l in range(2, n + 1): # 구간 길이
for i in range(n - l + 1): # 시작점
j = i + l - 1 # 끝점
dp[i][j] = float('inf')
cost = prefix[j+1] - prefix[i] # 구간 합
for k in range(i, j): # 분할 지점
dp[i][j] = min(dp[i][j], dp[i][k] + dp[k+1][j] + cost)
return dp[0][n-1]
files = [40, 30, 30, 50]
print(file_merge(files)) # 300
구간 DP 공통 패턴:
for l in range(2, n+1): # 구간 길이 2부터 for i in range(n-l+1): # 시작점 j = i + l - 1 # 끝점 for k in range(i, j): # 분할점 탐색 dp[i][j] = min/max(dp[i][k] + dp[k+1][j] + ...)
5️⃣ DP 최적화 기법
기법 1 - 메모이제이션 vs 타뷸레이션
# 재귀 + 메모이제이션 (Top-Down)
from functools import lru_cache
@lru_cache(maxsize=None)
def dp_topdown(i, j):
if 기저조건:
return 기저값
return 점화식
# 반복문 (Bottom-Up)
dp = [[0] * (m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
dp[i][j] = 점화식
기법 2 - 공간 최적화 (롤링 배열)
2차원 dp에서 현재 행이 이전 행만 참조할 때, 1차원으로 줄일 수 있다.
# LCS 공간 최적화: O(n*m) → O(m)
def lcs_optimized(A, B):
n, m = len(A), len(B)
prev = [0] * (m + 1)
for i in range(1, n + 1):
curr = [0] * (m + 1)
for j in range(1, m + 1):
if A[i-1] == B[j-1]:
curr[j] = prev[j-1] + 1
else:
curr[j] = max(prev[j], curr[j-1])
prev = curr
return prev[m]
기법 3 - 실전 DP 문제 풀이 전략
Step 1. dp[i] 또는 dp[i][j]의 의미를 명확하게 정의
Step 2. 기저 조건 (base case) 설정
Step 3. 마지막 선택/결정으로 점화식 도출
Step 4. 테이블을 채우는 순서 결정 (작은 값부터)
Step 5. 정답이 dp 테이블의 어디에 있는지 확인
❓ 점화식이 안 떠오를 때
→ dp[1], dp[2], dp[3]... 손으로 직접 채워보기
→ 반복되는 패턴이 보이면 일반화
6️⃣ 2차원 DP 5문제 풀이
✅ 문제 1 - LCS (최장 공통 부분 수열)
import sys
input = sys.stdin.readline
def solve():
A = input().strip()
B = input().strip()
n, m = len(A), len(B)
dp = [[0]*(m+1) for _ in range(n+1)]
for i in range(1, n+1):
for j in range(1, m+1):
if A[i-1] == B[j-1]:
dp[i][j] = dp[i-1][j-1] + 1
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
print(dp[n][m])
✅ 문제 2 - 평범한 배낭 (0/1 Knapsack)
import sys
input = sys.stdin.readline
def solve():
N, K = map(int, input().split())
dp = [0] * (K + 1)
for _ in range(N):
w, v = map(int, input().split())
for j in range(K, w-1, -1): # 역순 순회!
dp[j] = max(dp[j], dp[j-w] + v)
print(dp[K])
✅ 문제 3 - 연속합 (Kadane's Algorithm)
import sys
input = sys.stdin.readline
def solve():
n = int(input())
arr = list(map(int, input().split()))
dp = arr[0]
max_val = arr[0]
for i in range(1, n):
dp = max(arr[i], dp + arr[i])
max_val = max(max_val, dp)
print(max_val)
✅ 문제 4 - 가장 긴 증가하는 부분 수열 (LIS)
# O(n²) 풀이
def solve_n2(arr):
n = len(arr)
dp = [1] * n # dp[i] = arr[i]로 끝나는 LIS 길이
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)
# O(n log n) 풀이 (이분탐색 활용)
import bisect
def solve_nlogn(arr):
tails = [] # tails[i] = 길이 i+1인 증가 수열의 마지막 원소 최솟값
for num in arr:
pos = bisect.bisect_left(tails, num)
if pos == len(tails):
tails.append(num)
else:
tails[pos] = num # 더 작은 값으로 교체 (가능성 확장)
return len(tails)
arr = [10, 20, 10, 30, 20, 50]
print(solve_n2(arr)) # 4
print(solve_nlogn(arr)) # 4
⚠️ n이 크면 O(n²)은 시간초과!
LIS 길이만 필요하면 →bisect이용한 O(n log n)
실제 수열을 출력해야 하면 → 역추적 필요 (별도 구현)
✅ 문제 5 - 포도주 시식 (조건 있는 1차원 DP)
연속 3잔은 마시면 안 됨, 최대한 많이 마시기
def wine(arr):
n = len(arr)
if n == 1: return arr[0]
if n == 2: return arr[0] + arr[1]
dp = [0] * n
dp[0] = arr[0]
dp[1] = arr[0] + arr[1]
dp[2] = max(arr[0]+arr[2], arr[1]+arr[2], arr[0]+arr[1])
for i in range(3, n):
# 경우 1: i번째 안 마심
dp[i] = dp[i-1]
# 경우 2: i-1은 안 마시고 i만 마심
dp[i] = max(dp[i], dp[i-2] + arr[i])
# 경우 3: i-1, i 연속으로 마심 (i-2는 안 마심)
dp[i] = max(dp[i], dp[i-3] + arr[i-1] + arr[i])
return dp[n-1]
arr = [6, 10, 13, 9, 8, 1]
print(wine(arr)) # 33
7주차 핵심 요약
✅ 2차원 DP
→ dp[i][j]: 두 가지 상태를 동시에 추적할 때
→ LCS, 배낭, 격자 DP가 대표 유형
✅ LCS
→ dp[i][j] = 두 수열의 i, j번째까지 봤을 때 최장 공통 부분 수열 길이
→ 같으면: dp[i-1][j-1]+1 / 다르면: max(dp[i-1][j], dp[i][j-1])
✅ 배낭 문제 (0/1 Knapsack)
→ dp[j] = 용량 j에서 담을 수 있는 최대 가치
→ 역순 순회가 핵심! (같은 물건 중복 사용 방지)
✅ 구간 DP
→ dp[i][j] = 구간 [i,j] 처리의 최적값
→ 구간 길이 l → 시작점 i → 분할점 k 순으로 3중 루프
✅ LIS
→ O(n²): dp[i] = dp[j]+1 if arr[j] < arr[i]
→ O(n log n): bisect로 tails 배열 유지
풀이 비교 토론 - 같은 문제, 다른 접근법
LIS (가장 긴 증가하는 부분 수열) O(n²) DP → 직관적이지만 n=10,000이면 시간초과 O(n log n) bisect → 이분탐색으로 tails 배열 유지, 빠르지만 이해 어려움 → n ≤ 1,000이면 O(n²), n이 크면 O(n log n) 필수
배낭 문제 2차원 dp[i][j] → 메모리 O(n×K), 직관적 1차원 dp[j] 역순 순회 → 메모리 O(K), 공간 절약 → K가 크면 메모리 초과 가능, 1차원 버전 익혀두기
연속합 O(n²) 완전 탐색 → 모든 구간 다 확인, 느림 O(n) Kadane's → dp[i] = max(arr[i], dp[i-1]+arr[i]), 압도적으로 빠름 → 연속합류 문제 보이면 Kadane's 바로 떠올려야 함