동적 계획법은 loop를 두 번 쓰는 알고리즘이 아니다. 원래 문제의 답이 더 작은 문제의 답으로 구성되고, 같은 작은 문제가 반복될 때 상태별 답을 한 번 계산해 저장하는 전략이다. 가장 어려운 부분은 table을 채우는 문법이 아니라 상태가 미래 결정에 충분한지 증명하는 일이다.
1. 문제 계약
양의 정수 동전 종류를 제한 없이 사용해 amount를 만드는 최소 개수를 구한다. 결과는 최소 개수와 실제 동전 목록이다. 만들 수 없으면 count -1과 빈 목록, amount 0은 0개다. 음수 amount, null coins, 0 이하 coin은 계약 위반이다.
동전 순서는 결과 의미에 없으므로 복원 후 오름차순 정렬해 결정적인 출력을 만든다. 같은 최소 개수 해가 여러 개일 때 어느 조합을 고르는지는 coin iteration 순서에 의존하며 별도 tie-breaker가 필요할 수 있다.
2. 상태와 점화식
best[x]를 금액 x를 만드는 최소 동전 수로 정의한다. 미래에는 남은 금액만 알면 되고 이전 선택 순서는 필요 없다는 것이 state sufficiency다.
단, x-c가 불가능한 state면 후보에서 제외한다. 예제는 amount+1을 unreachable sentinel로 쓴다. 양의 동전만 있으므로 실제 필요한 동전 수는 1원 동전이 있어도 최대 amount라 sentinel이 충돌하지 않는다.
3. [1,3,4], amount 6 추적
| x | 유효 후보 | best[x] | 고른 coin |
|---|---|---|---|
| 0 | base | 0 | - |
| 1 | best[0]+1 | 1 | 1 |
| 2 | best[1]+1 | 2 | 1 |
| 3 | best[2]+1, best[0]+1 | 1 | 3 |
| 4 | 1·3·4 후보 | 1 | 4 |
| 5 | 4+1 또는 1+4 | 2 | 1 |
| 6 | best[3]+1이 최소 | 2 | 3 |
previousCoin[x]는 최솟값을 만들 때 마지막으로 붙인 동전을 기록한다. amount에서 그 값을 반복해서 빼면 0까지 가며 해를 복원한다.
4. 불변식과 정당성
불변식: 바깥 loop에서 x를 계산할 때 best[0..x)는 각 금액의 정확한 최소 개수다. 모든 coin이 양수라 x-c < x이므로 필요한 state가 이미 확정돼 있다.
금액 x의 어떤 최적해도 마지막 동전 c 하나를 가진다. 그 앞부분이 x-c의 최적해가 아니라면 더 짧은 해로 바꿔 x의 해도 줄일 수 있어 모순이다. algorithm은 가능한 모든 마지막 c를 비교하므로 최적해를 포함하고, 각 후보가 유효한 구성에 동전 하나를 붙인 것이므로 불가능한 값을 만들지 않는다.
실행 재현
아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
public final class DynamicProgrammingDemo {
record Result(int count, List<Integer> coins) {}
static Result minimumCoins(int[] coins, int amount) {
if (coins == null || amount < 0) throw new IllegalArgumentException("invalid input");
for (int coin : coins) if (coin <= 0) throw new IllegalArgumentException("coins must be positive");
int unreachable = amount + 1;
int[] best = new int[amount + 1];
int[] previousCoin = new int[amount + 1];
Arrays.fill(best, unreachable);
Arrays.fill(previousCoin, -1);
best[0] = 0;
for (int current = 1; current <= amount; current++) {
for (int coin : coins) {
if (coin <= current && best[current - coin] != unreachable && best[current - coin] + 1 < best[current]) {
best[current] = best[current - coin] + 1;
previousCoin[current] = coin;
}
}
}
if (best[amount] == unreachable) return new Result(-1, List.of());
List<Integer> used = new ArrayList<>();
for (int current = amount; current > 0; current -= previousCoin[current]) used.add(previousCoin[current]);
Collections.sort(used);
return new Result(best[amount], List.copyOf(used));
}
static void check(boolean condition, String message) {
if (!condition) throw new AssertionError(message);
}
public static void main(String[] args) {
Result result = minimumCoins(new int[] {1, 3, 4}, 6);
check(result.count() == 2 && result.coins().equals(List.of(3, 3)), "minimum");
check(minimumCoins(new int[] {2}, 3).count() == -1, "impossible");
check(minimumCoins(new int[] {2}, 0).count() == 0, "zero");
try {
minimumCoins(new int[] {0, 1}, 3);
throw new AssertionError("invalid coin expected");
} catch (IllegalArgumentException expected) {
check(expected.getMessage().equals("coins must be positive"), "invalid reason");
}
System.out.println("minimum(6)=" + result + ", impossible=-1, zero=0");
}
}
javac --release 21 DynamicProgrammingDemo.java
java DynamicProgrammingDemo
직접 실행한 출력은 다음과 같다.
minimum(6)=Result[count=2, coins=[3, 3]], impossible=-1, zero=0
컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.
5. Greedy가 실패하는 이유
동전 [4,3,1], amount 6에서 큰 동전 우선은 4+1+1 세 개, 최적은 3+3 두 개다. DP는 “마지막 동전 4/3/1” 후보를 모두 비교해 지역 선택에 갇히지 않는다. canonical coin system에서는 greedy가 맞을 수 있지만 임의 입력 계약에는 증명이 없다.
6. 시간·공간 복잡도
amount를 , 동전 종류 수를 라 하면 각 x에서 C개를 보므로 시간은 다. best와 previousCoin 두 int[A+1]로 보조 공간, 복원 output은 최소 개수 k만큼 다.
개수만 필요하면 previousCoin을 제거해 공간 상수를 줄일 수 있지만 실제 조합을 복원할 수 없다. memory optimization은 무료가 아니라 output 계약을 바꾼다. A가 수십억이면 pseudo-polynomial DP table 자체가 불가능하므로 amount 수치 크기까지 input size 모델에 넣는다.
7. top-down memoization과 bottom-up
top-down은 필요한 state만 방문하고 recurrence와 가까우나 호출 깊이와 memo lookup이 있다. bottom-up은 계산 순서가 명시적이고 recursion frame이 없으며 primitive array locality가 좋다. reachable state가 희소하면 top-down map이 메모리를 아낄 수 있지만 boxing/node 비용이 생긴다.
둘 다 같은 state graph를 평가한다. memoization이 없으면 겹치는 subproblem을 반복해 지수적으로 커질 수 있다.
8. JVM 메모리와 overflow
두 primitive array와 결과 list/boxed Integer는 heap에 있다. loop locals는 frame 관점이다. sentinel을 Integer.MAX_VALUE로 두고 무조건 +1하면 overflow할 수 있다. 예제는 amount+1 bound와 unreachable 확인 후에만 더한다. 다만 amount 자체가 Integer.MAX_VALUE면 배열을 만들 수 없고 amount+1도 overflow하므로 production API는 현실적인 upper bound를 먼저 검증해야 한다.
복원 list의 boxing/allocation이 hot path라면 caller-provided int[]나 packed result를 검토한다. 먼저 JFR로 allocation이 실제 병목인지 확인한다.
9. 실제 도메인 적용
resource budget allocation, batch partition, sequence alignment, cache replacement의 제한된 상태 모델로 확장할 수 있다. 그러나 state dimension이 늘면 table 크기가 곱으로 증가하는 차원의 저주가 온다. 관측 지표는 reachable states, transition count, table bytes, cache hit(top-down), solve latency, optimality gap(근사 사용 시)이다.
AI의 Viterbi/sequence decoding도 DP 구조를 가지지만 state와 transition score, numerical stability가 별도 계약이다. “DP를 쓴다”만으로 도메인 정당성이 생기지 않는다.
10. 이건 피한다
- 상태 정의 없이 2차원 배열부터 만든다. 미래 결정에 부족하거나 중복 차원이 생긴다. state가 무엇을 요약하고 왜 충분한지 먼저 증명한다.
- 불가능 sentinel에 1을 더한다. overflow로 최솟값처럼 보일 수 있다. 도달 가능 여부를 먼저 확인한다.
- 0/음수 coin을 허용한다. state가 줄지 않아 recurrence 순서와 복원이 깨진다. 입력에서 거절한다.
- amount 값 크기를 무시하고 polynomial이라 부른다. 는 수치 A에 대한 pseudo-polynomial이다. upper bound와 memory budget을 계산한다.
- 해 복원이 필요한데 value table만 남긴다. 최솟값은 알아도 선택을 재현할 수 없다. predecessor/choice를 저장한다.
Reference
- Richard Bellman, Dynamic Programming, Princeton University Press, 1957
- MIT OpenCourseWare, 6.046J Design and Analysis of Algorithms — Dynamic Programming lecture notes
- Oracle, Arrays — Java SE 21 API
- Oracle, The Java Language Specification, Java SE 21 — Integer Operations
- Oracle, The Java Virtual Machine Specification, Java SE 21 — Heap and Frames
댓글