동적 프로그래밍 (Dynamic Programming)
1. 오늘의 학습 흐름
- DP 개념 (메모이제이션 vs 타뷸레이션)
- 피보나치로 DP 필요성 체감
- BOJ 1149 RGB 거리
- BOJ 2293 동전 1
- 0/1 Knapsack 알고리즘
2. DP란
중복되는 부분 문제(Overlapping Subproblems)의 결과를 저장해서 재사용하는 기법이다.
DP가 적합한 문제의 두 가지 조건:
- 중복 부분 문제: 같은 계산이 반복해서 나타남
- 최적 부분 구조: 부분 문제의 최적해로 전체 최적해를 구성할 수 있음
두 가지 방식:
- 메모이제이션(Memoization): 재귀 + 결과 저장. Top-Down 방식
- 타뷸레이션(Tabulation): 반복문으로 테이블 채우기. Bottom-Up 방식
3. 피보나치로 DP 필요성 체감
피보나치를 단순 재귀로 구하면 같은 값을 엄청나게 많이 계산한다.
public static long fibo1(int n) {
if (n < 2) return 1;
return fibo1(n-1) + fibo1(n-2);
}
// fibo1(40) → 재귀 수행 횟수: 331,160,281번
// fibo(5)만 해도 중간에 fibo(2)가 3번, fibo(3)이 2번 호출됨메모이제이션을 적용하면:
static long[] memo;
public static long fibo2(int n) {
// 이미 계산된 값이면 바로 반환
if (n >= 2 && memo[n] == 0) {
memo[n] = fibo2(n-1) + fibo2(n-2);
}
return memo[n];
}
// fibo2(40) → 재귀 수행 횟수: 79번같은 결과를 memo[]에 저장해두면 이미 계산한 값은 배열에서 O(1)로 꺼낸다. 시간복잡도가 O(2^N)에서 O(N)으로 줄어든다.
4. BOJ 1149 - RGB 거리
N개의 집을 RGB로 칠하는데 인접한 집은 같은 색일 수 없고, 비용 합이 최소가 되도록 하는 문제다.
dp[i][색] = i번째 집을 해당 색으로 칠했을 때 1~i번까지의 최소 비용점화식:
dp[i][R] = min(dp[i-1][G], dp[i-1][B]) + cost[i][R]
dp[i][G] = min(dp[i-1][R], dp[i-1][B]) + cost[i][G]
dp[i][B] = min(dp[i-1][R], dp[i-1][G]) + cost[i][B]int[][] dp = new int[N][3]; // [집 번호][R=0, G=1, B=2]
dp[0][0] = cost[0][0];
dp[0][1] = cost[0][1];
dp[0][2] = cost[0][2];
for (int i = 1; i < N; i++) {
dp[i][0] = Math.min(dp[i-1][1], dp[i-1][2]) + cost[i][0];
dp[i][1] = Math.min(dp[i-1][0], dp[i-1][2]) + cost[i][1];
dp[i][2] = Math.min(dp[i-1][0], dp[i-1][1]) + cost[i][2];
}
System.out.println(Math.min(dp[N-1][0], Math.min(dp[N-1][1], dp[N-1][2])));풀이에서 dp 배열을 [2][3]으로 압축해서 공간복잡도를 줄였다. 직전 값만 필요하기 때문에 i%2로 현재/이전 인덱스를 번갈아 쓰는 방식이다.
5. BOJ 2293 - 동전 1
N가지 동전으로 가치 합이 K가 되는 경우의 수를 구하는 문제다.
dp[j] = 가치 j를 만드는 경우의 수각 동전에 대해 반복하면서 dp를 갱신한다.
int[] dp = new int[K + 1];
for (int i = 0; i < N; i++) {
int c = Integer.parseInt(in.readLine()); // 동전 가치
if (c > K) continue;
dp[c] += 1; // 이 동전만 단독으로 쓰는 경우
for (int j = c + 1; j <= K; j++) {
dp[j] += dp[j - c]; // j-c를 만드는 방법에 c를 얹기
}
}
System.out.println(dp[K]);핵심 아이디어: dp[j] = dp[j] + dp[j - c]
"이미 j-c를 만드는 방법이 dp[j-c]가지 있고, 거기에 동전 c를 하나 얹으면 j가 된다"는 논리다.
1차원 배열로 처리할 수 있는 이유: 동전을 무한히 사용할 수 있는 문제(Unbounded Knapsack)라서 이전 동전의 결과를 그대로 덮어써도 된다.
6. 0/1 Knapsack
배낭 무게 W를 초과하지 않으면서 가치 합이 최대가 되도록 물건을 선택하는 문제다. 각 물건은 하나씩만 있다.
K[i][j] = i번째 물건까지 고려했을 때, 배낭 무게 j에서의 최대 가치점화식:
j < w[i] (배낭이 물건보다 가벼울 때):
K[i][j] = K[i-1][j] // i번 물건 못 담음
j >= w[i] (담을 수 있을 때):
K[i][j] = max(K[i-1][j], // i번 물건 안 담는 경우
K[i-1][j - w[i]] + v[i]) // i번 물건 담는 경우int W = 10;
int[] w = {0, 5, 4, 6, 3}; // 무게 (0번은 dummy)
int[] v = {0, 10, 40, 30, 50}; // 가치
int[][] K = new int[w.length][W + 1];
for (int i = 1; i < w.length; i++) {
for (int j = 0; j < w[i]; j++) {
K[i][j] = K[i-1][j]; // 못 담는 경우
}
for (int j = w[i]; j <= W; j++) {
int now = K[i-1][j - w[i]] + v[i]; // 담는 경우
int pre = K[i-1][j]; // 안 담는 경우
K[i][j] = now >= pre ? now : pre;
}
}2차원 배열을 쓰는 이유: 물건이 1개씩이라서 같은 물건이 두 번 선택되는 걸 방지해야 한다. K[i-1]을 참조함으로써 이전 물건들의 결과에만 의존하고, 현재 물건 i가 다시 선택되는 것을 막는다.
1차원으로 쓰면 j를 역순으로 순회해서 해결할 수도 있다. j를 내림차순으로 순회하면 같은 물건이 두 번 쓰이는 걸 방지한다.
분할 가능 Knapsack vs 0/1 Knapsack
| 분할 가능 Knapsack | 0/1 Knapsack | |
|---|---|---|
| 물건 | 쪼개서 담을 수 있음 | 통째로 담거나 안 담거나 |
| 알고리즘 | Greedy (가치/무게 기준 정렬) | DP |
| 이유 | 남는 공간에 일부분만 담으면 됨 | 쪼갤 수 없어서 최적 부분 구조 필요 |
7. 오늘 리뷰
오늘 피보나치 예제에서 재귀 수행 횟수를 직접 찍어봤다. fibo1(40)이 3억 3천만 번, fibo2(40)이 79번. 같은 결과를 내는데 약 400만 배 차이가 난다.
DP가 어려운 이유는 코드 자체보다 "점화식을 세우는 것"이다. dp[i][j]가 무엇을 의미하는지를 명확하게 정의해야 한다. RGB 거리에서 dp[i][색] = i번 집을 해당 색으로 칠했을 때까지의 최소 비용이라는 정의가 잡히면 코드는 자연스럽게 나온다.
정의를 잡기 전에 코드부터 짜면 항상 헷갈린다. dp 문제는 정의 먼저, 점화식 다음, 코드 마지막 순서다.
8. 키워드 정리
Dynamic Programming
9. 내일의 목표
- 연휴동안 좀 쉬기..
