동적 계획법: 어떤 정보를 상태로 남겨야 할까
동적 계획법은 반복되는 부분문제의 답을 저장하고 작은 답들로 큰 답을 구성하는 방법이다. 표를 만든다는 외형보다 상태가 무엇을 뜻하며 어떤 정보만 남겨도 이후 결정을 할 수 있는지가 중요하다. 상태 정의가 틀리면 전이식을 정교하게 써도 문제를 풀지 못한다.
작은 상태의 최적해를 이용해 더 큰 상태의 최적해를 계산한다.
배낭의 상태와 선택
각 물건을 한 번만 선택할 수 있는 0/1 배낭에서 dp[i][c]를 “앞의 i개 물건으로 용량 c 이내에서 얻는 최대 가치”라고 정의하자. i번째 물건을 안 넣으면 이전 행의 같은 용량, 넣으면 그 무게를 뺀 이전 상태의 가치에 현재 가치를 더한다.
물건 무게 w가 용량 c를 넘으면 넣는 선택이 없다. 초기 상태는 물건이 없을 때 가치 0이다. 음수 가치나 반드시 일정 개수를 선택해야 하는 변형이라면 초기값과 불가능 상태 처리를 바꿔야 한다.
한 행으로 줄일 때 순서가 중요하다
def knapsack(weights, values, capacity):
best = [0] * (capacity + 1)
for weight, value in zip(weights, values):
for remaining in range(capacity, weight - 1, -1):
best[remaining] = max(
best[remaining],
best[remaining - weight] + value,
)
return best[capacity]
이 코드는 용량을 큰 쪽부터 갱신한다. 작은 쪽부터 갱신하면 같은 물건으로 이미 개선한 상태를 다시 읽어 물건을 여러 번 넣는 효과가 생긴다. 공간 최적화가 원래 상태의 의미를 바꾸지 않도록 읽기와 쓰기 순서를 지켜야 한다.
무게 2·가치 3과 무게 3·가치 4, 용량 5라면 둘을 골라 가치 7을 얻는다. dp에서 “최대 용량만큼 꼭 채우는가”와 “그 이내를 쓰는가”는 다른 의미다. 위 코드는 후자이므로 비어 있는 공간을 허용한다.
필요한 상태만 정확하게 보존하기
최적 부분 구조는 전체 최적 선택을 구성하는 부분 선택도 해당 조건에서 최적이어야 한다는 성질이다. 겹치는 부분문제는 같은 상태가 여러 경로에서 반복된다는 뜻이다. 전자는 전이의 의미, 후자는 저장의 효율을 설명한다.
물건 수 n과 정수 용량 W에 대한 시간은 O(nW), 공간은 O(W)다. W의 숫자 크기에 비례하므로 입력 비트 수에 대한 일반적인 다항 시간과 같지 않아 의사다항 시간이라고 한다. 용량이 아주 크면 이 방법이 부담스러울 수 있다.
해 선택까지 복원하려면 결정 기록이나 별도 상태를 저장해야 한다. 최댓값만 남기는 공간 최적화는 어떤 물건을 골랐는지 바로 제공하지 않는다. 상태, 초기값, 전이, 평가 순서, 출력 의미를 각각 설명할 수 있을 때 동적 계획법을 제대로 설계한 것이다.
정수 무게가 0인 물건이나 음수 무게를 허용할지 입력 계약에 명시해야 한다. 전이가 정의한 상태 범위를 벗어나면 같은 코드의 보장이 사라진다.