---
title: "동적 계획법: 상태·점화식·복원으로 동전 최소 개수를 증명하기"
slug: "java-dynamic-programming"
category: "CS"
topic: "cs"
subtopic: "algorithms"
tags: ["Java","Dynamic Programming","Coin Change","Memoization","JVM Memory"]
status: "published"
created: "2026-08-06"
updated: "2026-08-06"
summary: "동전 최소 개수 문제를 상태와 점화식으로 정의하고, bottom-up 계산·불가능 sentinel·해 복원·greedy 반례·메모리 최적화의 대가를 Java로 검증한다."
kind: "Deep Dive"
evidence: "Bellman의 optimality 원리·MIT 6.046J DP 강의 자료·Java SE 21 Arrays API를 대조하고 DynamicProgrammingDemo의 최소·불가능·0·잘못된 동전을 OpenJDK 21.0.11에서 실행"
series: "Java Essential Algorithms"
---

동적 계획법은 loop를 두 번 쓰는 알고리즘이 아니다. 원래 문제의 답이 더 작은 문제의 답으로 구성되고, 같은 작은 문제가 반복될 때 **상태별 답을 한 번 계산해 저장**하는 전략이다. 가장 어려운 부분은 table을 채우는 문법이 아니라 상태가 미래 결정에 충분한지 증명하는 일이다.

## 1. 문제 계약

양의 정수 동전 종류를 제한 없이 사용해 amount를 만드는 최소 개수를 구한다. 결과는 최소 개수와 실제 동전 목록이다. 만들 수 없으면 count `-1`과 빈 목록, amount 0은 0개다. 음수 amount, null coins, 0 이하 coin은 계약 위반이다.

동전 순서는 결과 의미에 없으므로 복원 후 오름차순 정렬해 결정적인 출력을 만든다. 같은 최소 개수 해가 여러 개일 때 어느 조합을 고르는지는 coin iteration 순서에 의존하며 별도 tie-breaker가 필요할 수 있다.

## 2. 상태와 점화식

`best[x]`를 금액 x를 만드는 최소 동전 수로 정의한다. 미래에는 남은 금액만 알면 되고 이전 선택 순서는 필요 없다는 것이 state sufficiency다.

$$
best[0]=0
$$

$$
best[x]=1+\min_{c\in coins, c\le x} best[x-c]
$$

단, `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 프로그램이다.

```java
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");
    }
}
```

```bash
javac --release 21 DynamicProgrammingDemo.java
java DynamicProgrammingDemo
```

직접 실행한 출력은 다음과 같다.

```text
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를 $A$, 동전 종류 수를 $C$라 하면 각 x에서 C개를 보므로 시간은 $O(AC)$다. `best`와 `previousCoin` 두 `int[A+1]`로 $O(A)$ 보조 공간, 복원 output은 최소 개수 k만큼 $O(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이라 부른다.** $O(AC)$는 수치 A에 대한 pseudo-polynomial이다. upper bound와 memory budget을 계산한다.
- **해 복원이 필요한데 value table만 남긴다.** 최솟값은 알아도 선택을 재현할 수 없다. predecessor/choice를 저장한다.

## Reference

- Richard Bellman, [Dynamic Programming, Princeton University Press, 1957](https://press.princeton.edu/books/paperback/9780691146683/dynamic-programming)
- MIT OpenCourseWare, [6.046J Design and Analysis of Algorithms — Dynamic Programming lecture notes](https://ocw.mit.edu/courses/6-046j-design-and-analysis-of-algorithms-spring-2015/pages/lecture-notes/)
- Oracle, [Arrays — Java SE 21 API](https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/Arrays.html)
- Oracle, [The Java Language Specification, Java SE 21 — Integer Operations](https://docs.oracle.com/javase/specs/jls/se21/html/jls-4.html#jls-4.2.2)
- Oracle, [The Java Virtual Machine Specification, Java SE 21 — Heap and Frames](https://docs.oracle.com/javase/specs/jvms/se21/html/jvms-2.html#jvms-2.5)