💡
DP·그리디
LCS·LIS·배낭·행렬 곱셈
강의 21: DP 심화 (Advanced Dynamic Programming)
대표 DP 패턴들(공통부분 수열·증가 수열·배낭·행렬 곱)을 정리합니다.
LCSLIS0/1 배낭
소요 시간
⏱ 약 1.5시간
난이도
📊 고급
선수 조건
🎯 단원 20
결과물
대표 DP 패턴들(공통부분 수열·증가 수열·배낭·행렬 곱)을 정리합니다.
이 강의에서 배우는 것
- 1LCS의 2D DP 테이블을 채우고, 역추적으로 실제 수열을 복원할 수 있다.
- 2LIS를 O(n²) DP와 O(n log n) bisect 방식 모두 구현하고, 원리의 차이를 설명할 수 있다.
- 30/1 배낭 문제를 O(nW) 2D에서 O(W) 1D로 공간 최적화할 수 있다.
소개
DP 심화에서는 **2차원 DP와 고전적인 알고리즘 문제**들을 다룹니다.
- **LCS (최장 공통 부분 수열)**: 두 시퀀스의 가장 긴 공통 부분을 찾는 문제
- **LIS (최장 증가 부분 수열)**: 수열에서 가장 긴 증가하는 부분 수열
- **0/1 배낭 문제**: 무게 제한이 있을 때 최대 가치 선택
- **행렬 체인 곱셈**: 행렬 곱 순서 최적화
이 문제들은 면접과 경쟁 프로그래밍의 **핵심 패턴**입니다.
핵심 개념
LCS (Longest Common Subsequence)
text
A = "ABCBDAB", B = "BDCAB"
dp[i][j] = A[0:i]와 B[0:j]의 LCS 길이
점화식:
A[i-1] == B[j-1]: dp[i][j] = dp[i-1][j-1] + 1
A[i-1] != B[j-1]: dp[i][j] = max(dp[i-1][j], dp[i][j-1])
"" B D C A B
"" 0 0 0 0 0 0
A 0 0 0 0 1 1
B 0 1 1 1 1 2
C 0 1 1 2 2 2
B 0 1 1 2 2 3
D 0 1 2 2 2 3
A 0 1 2 2 3 3
B 0 1 2 2 3 4 ← LCS = 4 ("BCAB" 또는 "BDAB")LIS (Longest Increasing Subsequence)
text
배열: [10, 9, 2, 5, 3, 7, 101, 18]
LIS: [2, 3, 7, 18] 길이 = 4
O(n²) DP:
dp[i] = i번째 원소로 끝나는 최장 증가 부분 수열 길이
dp[i] = max(dp[j] + 1) for j < i if arr[j] < arr[i]
O(n log n) patience sorting:
tails[]: 각 길이의 LIS에서 가장 작은 마지막 원소
새 원소: tails에서 bisect_left로 교체 위치 찾기0/1 배낭 (Knapsack)
text
물건: [(무게, 가치)] = [(2,6), (2,10), (3,12)]
최대 무게: W = 5
dp[i][w] = i번째 물건까지 고려, 무게 w 이하 최대 가치
w=0 w=1 w=2 w=3 w=4 w=5
물건0 0 0 6 6 6 6
물건1 0 0 10 10 16 16
물건2 0 0 10 12 16 22 ← 최적 = 22복잡도 비교
text
┌──────────────────────────┬──────────────┬──────────────┐
│ 알고리즘 │ 시간 │ 공간 │
├──────────────────────────┼──────────────┼──────────────┤
│ LCS │ O(nm) │ O(nm) → O(m) │
│ LIS O(n²) │ O(n²) │ O(n) │
│ LIS O(n log n) │ O(n log n) │ O(n) │
│ 0/1 배낭 2D │ O(nW) │ O(nW) │
│ 0/1 배낭 1D (최적화) │ O(nW) │ O(W) │
│ 행렬 체인 │ O(n³) │ O(n²) │
└──────────────────────────┴──────────────┴──────────────┘예제로 보기
| 파일 | 내용 |
|---|---|
| `src/01_lcs.py` | LCS dp 테이블, 수열 복원 |
| `src/02_lis.py` | LIS O(n²) DP + O(n log n) bisect |
| `src/03_knapsack.py` | 0/1 배낭, 공간 최적화 |
| `src/04_matrix_chain.py` | 행렬 체인 곱셈 순서 최적화 |
자주 하는 실수
- **LCS 인덱스 오프바이원**: `dp[i][j]`가 `A[0:i]`와 `B[0:j]`를 의미할 때, `A[i-1]`과 `B[j-1]`을 비교해야 함 — `A[i]`, `B[j]` 사용 시 IndexError
- **0/1 배낭 내부 루프 순서**: 1D 최적화 시 `w`를 **역방향**(W→coin)으로 순회해야 함 — 정방향이면 같은 물건을 여러 번 사용하는 unbounded knapsack이 됨
- **LIS 복원 오류**: tails 배열은 실제 LIS가 아닌 최적 tail 배열 — 실제 LIS 복원은 별도 역추적 필요
- **행렬 체인 대각선 순서**: dp[i][j] 계산 시 길이 2부터 시작해야 함 — 대각선 방향으로 채워야 올바른 순서
- **LCS 공간 최적화 시 역추적 불가**: O(m) 공간으로 줄이면 실제 수열 복원이 불가능 — 길이만 필요하면 최적화, 복원도 필요하면 2D 유지
정리
- **LCS**: 2D DP O(nm), 역추적으로 실제 수열 복원
- **LIS**: O(n²) DP vs O(n log n) bisect (patience sorting)
- **배낭**: 2D → 1D 역방향 루프로 공간 O(W) 최적화
- **행렬 체인**: 길이별로 대각선 방향으로 DP 채우기 O(n³)
직접 해 보기
- LCS의 공간을 O(min(n,m))으로 최적화해보기 (롤링 배열)
- LIS 개수 구하기 (길이가 아닌 개수)
- 편집 거리(Edit Distance / Levenshtein) 구현
과제
📂 `homework/README.md` 참조
- 백준 9251 (LCS) — Gold V
- 백준 11053 (가장 긴 증가하는 부분 수열) — Silver II
- 백준 12865 (평범한 배낭) — Gold V