14.7 요약¶

동적 계획법은 문제를 나누고 부분 문제의 해를 저장하여 중복 계산을 피함으로써 계산 효율을 높인다.
시간을 고려하지 않는다면 모든 동적 계획법 문제는 백트래킹(완전 탐색)으로 풀 수 있다. 하지만 재귀 트리에 중복 부분 문제가 매우 많아 비효율적이다. 메모이제이션 리스트에 계산한 해를 저장하면 중복 부분 문제를 한 번만 계산하도록 보장할 수 있다.
메모이제이션을 이용한 탐색은 위에서 아래로 진행하는 재귀 풀이이며, 이에 대응하는 동적 계획법은 '표를 채우듯' 아래에서 위로 진행하는 반복 풀이이다. 현재 상태는 일부 주변 상태에만 의존하므로 \(dp\) 테이블의 한 차원을 없애 공간 복잡도를 줄일 수 있다.
부분 문제로 나누는 것은 일반적인 알고리즘 아이디어이며, 분할 정복, 동적 계획법, 백트래킹에서 서로 다른 특성을 가진다.
동적 계획법 문제의 세 가지 주요 특성은 중복 부분 문제, 최적 부분 구조, 무후효성이다.
원래 문제의 최적해를 부분 문제의 최적해로 구성할 수 있다면 최적 부분 구조를 가진다.
무후효성이란 한 상태의 이후 전개가 현재 상태에만 의존하고 과거의 모든 상태와는 무관하다는 뜻이다. 많은 조합 최적화 문제는 무후효성을 갖지 않아 동적 계획법으로 빠르게 풀 수 없다.

배낭 문제

배낭 문제는 가장 대표적인 동적 계획법 문제 중 하나로, 0-1 배낭, 무한 배낭, 개수 제한 배낭 등의 변형이 있다.
0-1 배낭의 상태는 앞 \(i\) 개 물건을 용량 \(c\)인 배낭에 담을 때의 최대 가치로 정의한다. 넣지 않기와 넣기라는 두 결정으로 최적 부분 구조와 상태 전이 식을 얻는다. 공간 최적화에서는 바로 위와 왼쪽 위 상태에 의존하므로, 왼쪽 위 값이 덮어써지지 않도록 리스트를 역순으로 순회해야 한다.
무한 배낭은 각 물건의 선택 횟수에 제한이 없어 물건을 넣는 상태 전이가 0-1 배낭과 다르다. 바로 위와 바로 왼쪽 상태에 의존하므로 공간 최적화에서는 정방향 순회를 해야 한다.
동전 교환은 무한 배낭의 변형이다. '최대' 가치 대신 '최소' 동전 수를 구하므로 상태 전이 식의 \(\max()\)를 \(\min()\)으로 바꾼다. 용량을 '넘지 않는' 것이 아니라 목표 금액을 '정확히' 만들어야 하므로, 만들 수 없는 유효하지 않은 해를 \(amt + 1\)로 나타낸다.
동전 교환 II는 '최소 동전 수' 대신 '동전 조합 수'를 구하므로 상태 전이 식의 \(\min()\)을 합 연산으로 바꾼다.

편집 거리 문제

편집 거리(Levenshtein 거리)는 두 문자열의 유사도를 측정하며, 한 문자열을 다른 문자열로 바꾸는 최소 편집 횟수로 정의된다. 편집 연산에는 추가, 삭제, 교체가 있다.
편집 거리의 상태는 \(s\)의 앞 \(i\) 개 문자를 \(t\)의 앞 \(j\) 개 문자로 바꾸는 최소 편집 횟수로 정의한다. \(s[i-1] \ne t[j-1]\)이면 추가, 삭제, 교체의 세 결정이 있고 각각 남는 부분 문제가 있다. 이를 바탕으로 최적 부분 구조와 상태 전이 식을 구한다. \(s[i-1] = t[j-1]\)이면 현재 문자를 편집할 필요가 없다.
편집 거리의 상태는 바로 위, 바로 왼쪽, 왼쪽 위 상태에 의존하므로 공간 최적화 후에는 정방향이나 역방향 순회만으로 올바른 전이를 할 수 없다. 변수를 하나 두어 왼쪽 위 상태를 임시 저장하면 무한 배낭과 같은 상황이 되어 정방향 순회가 가능하다.