DP 심화 - 1차원 Knapsack, 이항 계수, 색상환
1. 오늘의 학습 흐름
- 0/1 Knapsack 1차원으로 압축 (Knapsack2)
- 이항 계수 - 파스칼의 삼각형 DP (BinomialCoefficient)
- BOJ 2482 색상환
2. 0/1 Knapsack - 1차원으로 줄이기
어제 2차원 배열로 풀었던 0/1 Knapsack을 1차원 배열로 압축할 수 있다. 핵심은 j를 역순(내림차순)으로 순회하는 것이다.
int[] K = new int[W + 1];
for (int i = 1; i < w.length; i++) {
// j를 W부터 w[i]까지 역순 순회
for (int j = W; j >= w[i]; j--) {
int now = K[j - w[i]] + v[i]; // 현재 물건 담는 경우
int pre = K[j]; // 담지 않는 경우
K[j] = now >= pre ? now : pre;
}
}왜 역순으로 순회하는가: j를 오름차순으로 순회하면 K[j - w[i]]가 이미 현재 물건 i로 갱신된 값을 참조하게 된다. 같은 물건을 두 번 쓰는 효과가 생겨서 0/1 조건이 깨진다. 역순으로 순회하면 K[j - w[i]]는 아직 갱신되기 전 값이라 같은 물건이 두 번 선택되는 걸 막을 수 있다.
역방향(내림차순) → 같은 물건 1번만 사용 (0/1 Knapsack)
순방향(오름차순) → 같은 물건 중복 사용 허용 (Unbounded Knapsack, 어제 동전 문제)3. 이항 계수 - 파스칼의 삼각형
nCk를 DP로 구하는 방법이다.
점화식:
nCk = (n-1)C(k-1) + (n-1)Ck"n개 중 k개 선택"을 특정 원소 A 기준으로 나눈다.
- A를 선택한 경우: 나머지 n-1개 중 k-1개 선택 →
(n-1)C(k-1) - A를 선택하지 않은 경우: 나머지 n-1개 중 k개 선택 →
(n-1)Ck
int[][] memo = new int[N+1][K+1];
for (int i = 0; i <= N; i++) {
for (int j = 0; j <= i; j++) {
if (j == 0 || j == i) {
memo[i][j] = 1; // nC0 = nCn = 1
} else {
memo[i][j] = memo[i-1][j-1] + memo[i-1][j]; // 파스칼의 삼각형
}
}
}파스칼의 삼각형이 이 점화식의 시각적 표현이다. 각 원소가 위쪽 두 원소의 합이다.
1
1 1
1 2 1
1 3 3 1
1 4 6 4 1
1 5 10 10 5 1재귀로 nCk를 구하면 중복 계산이 엄청나게 발생한다. DP로 memo 배열에 저장해두면 이미 계산한 값을 O(1)로 꺼내서 O(N*K)로 끝낼 수 있다.
4. BOJ 2482 - 색상환
N가지 색상이 원형으로 배치된 색상환에서, 인접하지 않게 K가지 색상을 선택하는 경우의 수를 구하는 문제다.
dp[i][j] = i개의 색상(선형) 중 인접하지 않게 j개를 선택하는 경우의 수
점화식:
i번째 선택하지 않는 경우: dp[i-1][j]
i번째 선택하는 경우: dp[i-2][j-1] (i-1번은 인접해서 못 씀)
→ dp[i][j] = dp[i-1][j] + dp[i-2][j-1]for (int i = 1; i <= n; i++) {
dp[i][1] = i; // i개 중 1개 선택은 i가지
dp[i][0] = 1; // 점화식 계산을 위해 0개 선택은 1로 초기화
}
for (int i = 3; i <= n; i++) {
for (int j = 2; j <= (i+1)/2; j++) { // n/2개 초과 선택은 불가
dp[i][j] = (dp[i-1][j] + dp[i-2][j-1]) % MOD;
}
}원형이라서 답이 dp[n][k]가 아니다. dp[n][k]에는 1번과 N번을 동시에 선택하는 경우가 포함되어 있기 때문이다.
dp[n][k] = dp[n-2][k-1] + dp[n-1][k]
↑ N번 선택한 경우 ↑ N번 미선택한 경우
N번을 선택한 경우(dp[n-2][k-1])에는
1번과 N번이 동시에 선택되는 경우가 포함되어 있다.
→ 1번을 제외한 N-3개 중에서 k-1개 선택한 경우를 빼야 함 = dp[n-3][k-1]
최종 답: dp[n-3][k-1] + dp[n-1][k]System.out.println((dp[n-3][k-1] + dp[n-1][k]) % MOD);5. 오늘 리뷰
오늘 색상환 문제에서 "왜 dp[n][k]가 답이 아닌가"를 이해하는 게 제일 어려웠다. 선형 문제라면 dp[n][k]로 끝나는데, 원형이 되면 1번과 N번의 인접 관계가 추가로 생겨서 별도 처리가 필요하다.
원형 DP의 일반적인 처리 방법: 1번을 고정하거나 제외하는 두 케이스로 나눠서 선형 DP를 적용한다.
6. 키워드 정리
DP
7. 내일의 목표
- 백준 문제 풀이
