동적 계획법의 상태와 탐욕 반례

이 노트는 동적 계획법을 “재귀를 쓰는 기법”이 아니라 미래의 선택 가능성을 결정하는 최소 상태를 찾아, 이미 계산한 상태를 전이에서 재사용하는 방법으로 설명합니다. 상태를 잘못 합치면 정답이 사라지고, 갱신 방향을 잘못 고르면 같은 물건을 다시 쓰게 되므로 상태 의미와 실행 순서를 함께 추적해야 합니다.

탐욕적 첫 선택과 전체 최적해 손실

동전이 1·3·4이고 금액 6을 정확히 만들려 합니다. 큰 동전부터 고르면 4+1+1로 세 개지만, 3+3이면 두 개입니다. 이 작은 반례만으로 임의 동전 체계에 큰 동전 우선 탐욕법을 적용할 수 없음을 알 수 있습니다.

큰 동전을 먼저 고르는 방법은 지금 남은 금액만 보고 하나를 선택합니다. 이런 탐욕법이 맞는 문제도 있지만, 여기서는 첫 선택인 4 때문에 더 좋은 답을 놓쳤습니다. 그렇다면 마지막 동전이 1인 경우, 3인 경우, 4인 경우를 모두 비교하면 어떨까요?

마지막 동전이 1이라면 앞에서 금액 5를 만들어야 합니다. 3이라면 금액 3을, 4라면 금액 2를 만들어야 합니다. 이미 이 작은 금액들의 최소 동전 수를 알고 있다면, 각각에 한 개를 더해 가장 좋은 답을 고를 수 있습니다. 작은 문제의 답을 저장해 더 큰 문제에서 다시 쓰는 것이 이 예제에서 동적 계획법이 하는 일입니다.

여기서 중요한 것은 재귀 함수를 쓰느냐가 아닙니다. 어떤 작은 문제들을 같은 것으로 보고, 그 답을 다시 사용해도 되는지를 정하는 것이 먼저입니다. 탐욕법을 선택하려면 이와 달리, 지금 고른 선택 때문에 최적해를 놓치지 않는다는 근거가 필요합니다.

상태를 설계하기 전에 “같은 미래”라는 기준을 세우는 것이 선행 조건입니다. 마지막 선택을 기준으로 보면 금액 x의 최적값은 x-c라는 더 작은 금액의 최적값에만 의존하지만, 0-1 배낭처럼 남은 물건 집합이 달라지면 같은 용량도 같은 상태가 아닙니다. 이 차이를 먼저 확인하면 DP 적용 여부를 문제 유형이 아니라 정보 보존 조건으로 판단할 수 있습니다.

무제한 동전 문제의 금액 기반 상태

best[x]를 금액 x를 정확히 만드는 최소 동전 수로 정의합니다. 동전은 양수 정수이고 사용 개수 제한이 없습니다. 마지막에 동전 c를 하나 썼다면 그 앞은 x-c를 최적으로 만든 결과여야 합니다.

best[0] = 0
best[1..M] = UNREACHABLE
for x = 1 .. M:
    for c in positive_coin_values:
        if c <= x and best[x-c] != UNREACHABLE:
            candidate = best[x-c] + 1
            if best[x] == UNREACHABLE or candidate < best[x]:
                best[x] = candidate
                lastCoin[x] = c

금액 x	마지막 동전 후보에서 얻는 최소값	best[x]
0	빈 선택	0
1	1	1
2	1+1	2
3	3	1
4	4	1
5	4+1	2
6	3+3	2

x가 줄어드는 경로를 lastCoin으로 따라가면 실제 선택을 복원합니다. M=6에서 c=3을 선택하고 x=3으로, 다시 c=3을 선택해 x=0으로 갑니다. 동전 1이 없으면 불가능한 금액이 있으므로 큰 숫자 sentinel에 무조건 1을 더하지 않습니다.

그림을 글로 읽기

• best[6]: 최소 동전 개수
• 1을 마지막에 사용: best[5]+1 = 3
• 3을 마지막에 사용: best[3]+1 = 2
• 4를 마지막에 사용: best[2]+1 = 3

1. best[6] → 1을 마지막에 사용: 6-1
2. best[6] → 3을 마지막에 사용: 6-3
3. best[6] → 4를 마지막에 사용: 6-4

동일 금액 상태의 병합 조건

금액 4를 만든 과거가 4와 1+3이라면 무제한 동전에서는 이후 선택 가능한 동전 집합이 같습니다. 따라서 더 적은 개수의 과거만 남겨도 됩니다. 하지만 동전마다 한 개씩만 쓸 수 있다면 두 과거의 남은 동전이 다릅니다. 앞으로 금액 3을 더 만들려 할 때 4를 쓴 과거에는 3이 남지만, 1+3을 쓴 과거에는 없습니다.

이제 금액만 같다고 합치면 미래 가능한 선택을 잃습니다. 동전 종류를 순서대로 처리하는 인덱스, 남은 수량 등 충분한 정보를 상태에 넣어야 합니다. 모든 이력을 넣는 것은 정확할 수 있어도 상태 수가 폭발하므로, 미래의 가능성과 비용을 구분하는 최소 정보를 찾습니다.

실패를 재현하는 가장 작은 추적은 동전 종류가 1·3·4이고 각 동전을 한 번만 쓸 수 있는 경우입니다. 4를 만든 이력과 1+3을 만든 이력처럼 같은 금액에 도착해도 남은 동전 집합을 나란히 적어 보십시오. 이후 금액 3을 만들 때 가능한 후보가 달라지므로 best[amount]만으로 합치면 잘못된 최솟값을 재사용하게 됩니다. 반대로 무제한 문제에서는 이 추가 이력이 미래 선택에 영향을 주지 않으므로 금액 하나로 충분합니다.

0-1 배낭의 순회 방향과 상태 의미

용량 50에 (무게,가치)=(10,60),(20,100),(30,120)을 넣습니다. 물건을 나눌 수 있으면 가치/무게가 큰 순서로 10·20을 모두, 30짜리의 20만큼을 넣어 240을 얻습니다. 낮은 비율의 일부를 높은 비율로 바꿔도 무게는 같고 가치는 늘어난다는 교환 논증이 성립합니다.

통째로만 넣을 수 있는 0-1 배낭에서는 그 선택이 160으로 끝나지만 뒤 두 개는 220입니다. 용량별 DP에서 각 물건을 한 번만 쓰려면 다음처럼 용량을 내림차순으로 갱신합니다.

value[0..W] = 0                      # 용량 이하로 담는 문제
for (weight, gain) in items:
    require weight > 0 and integer weight
    for capacity = W down to weight:
        value[capacity] = max(value[capacity],
                              value[capacity-weight] + gain)

왜 큰 용량부터 계산할까요? 무게 2, 가치 3인 물건이 하나만 있고 배낭 용량은 4인 경우를 따라가 보겠습니다.

작은 용량부터 갱신하면 먼저 value[2]=3이 됩니다. 이어서 용량 4를 계산할 때 방금 바꾼 value[2]를 읽으므로 value[4]=3+3=6이 됩니다. 물건 하나를 두 번 넣은 셈입니다.

큰 용량부터 갱신하면 용량 4를 계산할 때 value[2]는 아직 이번 물건을 반영하기 전의 0입니다. 따라서 value[4]=3이고, 그다음 용량 2도 3으로 바뀝니다. 이번 물건을 반영하기 전의 값을 읽게 하는 것이 역순 갱신의 목적입니다.

배열을 두 줄로 나누어 이전 단계와 현재 단계를 따로 저장하면 이 관계가 더 눈에 잘 들어옵니다. 한 줄로 줄이는 최적화를 할 때 그 관계를 지키려고 순회 방향을 선택하는 것입니다.

또한 위 코드는 용량을 남겨도 되는 문제입니다. 정확히 용량을 채워야 한다면 0 이외의 초기 상태는 ‘아직 만들 수 없음’으로 두어야 합니다. 전부 0으로 시작하면 만들 수 없는 무게도 가능한 것처럼 다음 계산에 사용됩니다.

저장 방식과 계산량의 분리

방식	계산 순서	주의할 비용
Top-down 메모이제이션	필요한 상태에서 재귀 호출	호출 깊이·캐시 키·순환 의존
Bottom-up 표	의존 상태가 먼저 채워지는 순서	모든 상태 계산·메모리 배치
상태 압축	직전 층 등 필요한 표만 유지	잘못된 덮어쓰기·역추적 정보 손실

동전 종류가 C개이고 목표 금액이 M이면, 금액 0부터 M까지 각 상태에서 C개 동전을 확인하므로 위 DP는 O(MC) 시간과 O(M) 공간을 사용합니다. 예를 들어 M이 10억이면 입력에 M을 이진수로 적는 데 필요한 길이는 약 30비트이지만 표는 최대 10억 개 상태를 고려할 수 있어 의사 다항 시간입니다. 메모이제이션은 실제로 도달하는 상태만 줄일 뿐, 최악 상태 수와 비용 타입의 overflow를 자동으로 없애 주지는 않습니다.

분할 정복은 독립적인 작은 구간을 풀고 합치는 병합 정렬처럼 부분 문제의 분해에 초점이 있습니다. DP는 중복 상태의 답을 재사용합니다. 모든 재귀가 DP도 아니고, 모든 최적화 문제가 DP로 효율적으로 풀리는 것도 아닙니다.

실무 선택은 입력의 숫자 크기와 필요한 결과를 함께 봅니다. 목표 금액·용량이 작고 모든 상태의 답과 역추적이 필요하면 bottom-up 표가 설명과 검증에 유리하고, 상태 공간이 희소하면 top-down이 불필요한 계산을 줄일 수 있습니다. 값만 필요할 때 상태 압축을 쓰되 선택 복원이 요구되면 predecessor나 선택 비트를 별도로 보존하지 않는 순간 기능 요구를 잃습니다.

반례와 복원 결과의 동시 검사

작은 동전 집합과 금액을 완전 탐색해 DP의 개수뿐 아니라 복원한 동전 합과 사용 제한을 확인합니다. 배낭은 모든 부분집합을 열거해 용량·가치가 맞는지 비교하고, 한 물건 (2,3), 용량 4에서 0-1 해는 3이지 6이 아님을 검사합니다. 상태를 하나 줄이는 수정은 특히 같은 축약 상태에 도달한 두 과거가 서로 다른 미래를 갖는 반례를 찾아 검증해야 합니다.

검증에서는 best[M]만 비교하지 말고 lastCoin을 따라 얻은 합이 M인지, 사용 제한을 넘지 않는지, 각 전이가 실제로 도달 가능한 상태에서 왔는지를 함께 검사합니다. 작은 입력에서 완전 탐색과 DP를 대조했을 때 값은 맞지만 복원 배열만 틀리거나, unreachable sentinel에 1을 더해 가짜 해가 생기는 경우를 분리해 잡을 수 있습니다.