DP 패턴 정리 — 배낭, LIS, LCS, 구간 DP
DP가 어려운 진짜 이유는 "이 문제에 어떤 패턴을 적용해야 하는지" 모르기 때문입니다. 자주 나오는 패턴을 정리해두면 점화식이 보입니다.
DP 점화식 도출 3단계
- **상태 정의 **: dp[i]가 무엇을 의미하는지 명확히 정한다
- ** 전이(Transition)**: dp[i]를 이전 상태들로 어떻게 표현하는지 수식을 세운다
- ** 기저 조건(Base Case)**: 가장 작은 문제의 답을 초기화한다
이 세 단계만 잘 정하면 구현은 자연스럽게 따라옵니다.
패턴 1: 0/1 배낭 (Knapsack)
물건을 넣거나 안 넣거나 (0 또는 1). 각 물건은 한 번만 사용.
상태 정의
dp[i][w] = i번째 물건까지 고려했을 때, 용량 w 이내의 최대 가치
점화식
dp[i][w] = max(
dp[i-1][w], // i번째 물건을 안 넣는 경우
dp[i-1][w - weight[i]] + value[i] // i번째 물건을 넣는 경우
)
구현
public static int knapsack(int[] weight, int[] value, int capacity) {
int n = weight.length;
int[][] dp = new int[n + 1][capacity + 1];
for (int i = 1; i <= n; i++) {
for (int w = 0; w <= capacity; w++) {
dp[i][w] = dp[i-1][w]; // 안 넣는 경우
if (w >= weight[i-1]) {
dp[i][w] = Math.max(dp[i][w],
dp[i-1][w - weight[i-1]] + value[i-1]);
}
}
}
return dp[n][capacity];
}
1차원 배열로 공간 최적화
public static int knapsack1D(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int w = capacity; w >= weight[i]; w--) { // 역순!
dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
}
}
return dp[capacity];
}
역순으로 순회하는 이유: 같은 물건을 두 번 사용하는 것을 방지합니다. 정순이면 완전 배낭(Unbounded Knapsack)이 됩니다.
패턴 2: LIS (Longest Increasing Subsequence)
가장 긴 증가하는 부분 수열의 길이를 구합니다.
O(n²) DP
// dp[i] = arr[i]를 마지막으로 하는 LIS의 길이
public static int lisDP(int[] arr) {
int n = arr.length;
int[] dp = new int[n];
Arrays.fill(dp, 1);
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (arr[j] < arr[i]) {
dp[i] = Math.max(dp[i], dp[j] + 1);
}
}
}
return Arrays.stream(dp).max().getAsInt();
}
O(n log n) 이진 탐색
public static int lisBinarySearch(int[] arr) {
// tails[i] = 길이 (i+1)인 증가 수열의 가장 작은 끝값
List<Integer> tails = new ArrayList<>();
for (int num : arr) {
int pos = Collections.binarySearch(tails, num);
if (pos < 0) pos = -(pos + 1); // 삽입 위치
if (pos == tails.size()) {
tails.add(num); // 새로운 길이의 수열
} else {
tails.set(pos, num); // 끝값을 더 작은 값으로 갱신
}
}
return tails.size();
}
tails 배열은 항상 정렬되어 있으므로 이진 탐색이 가능합니다. 이 기법은 인내 정렬(Patience Sorting)이라고도 합니다.
패턴 3: LCS (Longest Common Subsequence)
두 문자열의 가장 긴 공통 부분 수열을 구합니다.
점화식
dp[i][j] = 두 문자열의 처음 i, j 글자까지 고려한 LCS 길이
if s1[i-1] == s2[j-1]:
dp[i][j] = dp[i-1][j-1] + 1 (같으면 LCS에 추가)
else:
dp[i][j] = max(dp[i-1][j], dp[i][j-1]) (하나를 건너뜀)
구현
public static int lcs(String s1, String s2) {
int m = s1.length(), n = s2.length();
int[][] dp = new int[m + 1][n + 1];
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
dp[i][j] = dp[i-1][j-1] + 1;
} else {
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
}
}
}
return dp[m][n];
}
LCS 문자열 복원
public static String lcsString(String s1, String s2) {
// dp 테이블 구성 (위와 동일)
// ...
// 역추적
StringBuilder sb = new StringBuilder();
int i = m, j = n;
while (i > 0 && j > 0) {
if (s1.charAt(i-1) == s2.charAt(j-1)) {
sb.append(s1.charAt(i-1));
i--; j--;
} else if (dp[i-1][j] > dp[i][j-1]) {
i--;
} else {
j--;
}
}
return sb.reverse().toString();
}
패턴 4: 구간 DP (Interval DP)
구간 [i, j]에 대한 최적값을 구하는 패턴입니다. 행렬 체인 곱셈, 최적 BST 등에 사용됩니다.
행렬 체인 곱셈
n개의 행렬을 곱할 때 곱셈 횟수를 최소화하는 괄호 위치를 찾습니다.
// dp[i][j] = 행렬 i부터 j까지 곱하는 최소 비용
// dim[i] = i번째 행렬의 행 수, dim[n] = 마지막 행렬의 열 수
public static int matrixChainMultiplication(int[] dim) {
int n = dim.length - 1; // 행렬 수
int[][] dp = new int[n][n];
// 구간 길이를 늘려가며 계산
for (int len = 2; len <= n; len++) {
for (int i = 0; i <= n - len; i++) {
int j = i + len - 1;
dp[i][j] = Integer.MAX_VALUE;
// 분할점 k
for (int k = i; k < j; k++) {
int cost = dp[i][k] + dp[k+1][j]
+ dim[i] * dim[k+1] * dim[j+1];
dp[i][j] = Math.min(dp[i][j], cost);
}
}
}
return dp[0][n-1];
}
구간 DP의 일반적 구조
// 구간 길이를 1부터 n까지
for (int len = 1; len <= n; len++) {
for (int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
// dp[i][j]를 계산
for (int k = i; k < j; k++) {
// 분할점 k에서의 최적값 비교
dp[i][j] = optimize(dp[i][k], dp[k+1][j], ...);
}
}
}
패턴 5: 완전 배낭 (Unbounded Knapsack)
각 물건을 무제한 사용할 수 있는 배낭 문제입니다.
public static int unboundedKnapsack(int[] weight, int[] value, int capacity) {
int[] dp = new int[capacity + 1];
for (int i = 0; i < weight.length; i++) {
for (int w = weight[i]; w <= capacity; w++) { // 정순! (0/1과 반대)
dp[w] = Math.max(dp[w], dp[w - weight[i]] + value[i]);
}
}
return dp[capacity];
}
동전 교환 문제(최소 동전 수)도 완전 배낭의 변형입니다.
// 최소 동전 수
public static int coinChange(int[] coins, int amount) {
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
dp[0] = 0;
for (int coin : coins) {
for (int a = coin; a <= amount; a++) {
dp[a] = Math.min(dp[a], dp[a - coin] + 1);
}
}
return dp[amount] > amount ? -1 : dp[amount];
}
패턴 요약
| 패턴 | 상태 | 전이 | 시간 |
|---|---|---|---|
| 0/1 배낭 | dp[i][w]: i개 물건, 용량 w | 넣기/안넣기 | O(nW) |
| 완전 배낭 | dp[w]: 용량 w | 모든 물건 시도 | O(nW) |
| LIS | dp[i]: i번째로 끝나는 LIS | 이전 원소 비교 | O(n²) / O(n log n) |
| LCS | dp[i][j]: s1[:i], s2[:j] | 같으면 +1, 다르면 max | O(mn) |
| 구간 DP | dp[i][j]: 구간 [i,j] | 분할점 k 탐색 | O(n³) |
백엔드/실무에서의 연결
diff 알고리즘
Git의 diff는 LCS의 응용입니다. 두 파일의 LCS를 구하면, 변경되지 않은 줄을 파악하고 변경/추가/삭제를 표시합니다.
문자열 유사도
편집 거리(Edit Distance)는 LCS의 변형으로, 자동 완성, 맞춤법 검사, DNA 서열 비교에 사용됩니다.
리소스 할당
서버 리소스(CPU, 메모리)를 여러 서비스에 할당하는 문제는 배낭 문제의 변형입니다.
쿼리 최적화
데이터베이스의 조인 순서 최적화는 구간 DP와 유사한 구조입니다.
주의할 점
LIS에서 O(n^2)과 O(n log n)의 적용 기준을 모르는 실수
n이 10,000 이하이면 O(n^2) DP로 충분하지만, n이 100,000 이상이면 이진 탐색 기반 O(n log n) 풀이가 필요합니다. 입력 범위를 보고 판단해야 합니다.
구간 DP에서 구간 크기 순서로 채우지 않는 실수
구간 DP는 작은 구간부터 큰 구간으로 채워야 합니다. 즉, 길이 1 → 길이 2 → ... → 길이 n 순서로 계산해야 이전 결과를 참조할 수 있습니다.
정리
기억할 포인트:
- DP의 핵심은 상태 정의 → 전이 → 기저 조건 세 단계입니다.
- 0/1 배낭은 ** 역순 순회 **, 완전 배낭은 ** 정순 순회 **입니다.
- LIS는 이진 탐색으로 O(n log n)에 구할 수 있습니다.
- LCS는 Git diff의 기반이 됩니다.
- 문제를 보고 "이건 배낭이다", "이건 LCS다"라고 패턴을 인식하는 것이 DP의 핵심 역량입니다.
댓글 로딩 중...