그리디와 동적 계획법

되돌아보는지가 다릅니다. 그리디는 매 단계 최선을 골라 확정하고, 동적 계획법은 부분 문제의 답을 저장해 두고 다시 씁니다.

갈림길은 하나입니다. 지금의 선택이 뒤를 망칠 수 있으면 그리디를 쓸 수 없습니다.

흔한 실수: 그리디가 더 빠르니 먼저 시도한다고 답하는 것. 빠른 것은 맞지만 틀린 답을 빠르게 낼 수 있다는 것이 요점입니다. 성립 근거를 말하지 못하면 고른 이유가 없는 것입니다.

동전으로 금액을 만드는 문제가 대표적입니다.

동전이 500, 100, 50, 10원이면 큰 것부터 집는 그리디가 맞습니다. 큰 단위가 작은 단위의 배수라서, 큰 것을 집는 선택이 뒤를 막지 않습니다.

그런데 동전이 1원, 3원, 4원이고 6원을 만든다면 결과가 달라집니다.

그리디는 4원을 먼저 집고, 남은 2원을 1원 두 개로 채운다. 동전 3개
실제 최선은 3원 두 개로 만드는 것이다. 동전 2개

큰 것부터 집는다는 판단이 뒤를 망쳤습니다. 이럴 때 모든 금액에 대해 최소 개수를 채워 올라가는 동적 계획법으로 넘어갑니다.

판단 기준은 큰 단위가 작은 단위의 배수인지입니다. 배수 관계가 깨지면 그리디의 근거가 사라집니다.

흔한 실수: 동전 문제는 그리디로 푼다고 외우는 것. 실제 화폐 단위에서 성립하는 것이고 문제에서 주는 단위에 따라 달라집니다. 조건을 보지 않고 방법을 고르면 틀립니다.

같은 부분 문제를 여러 번 계산하는 구조여야 합니다. 이것을 중복 부분 문제라고 합니다.

피보나치를 그대로 재귀로 풀면 같은 값을 지수적으로 다시 계산합니다.

fib(5) 를 구하려면 fib(4) 와 fib(3) 이 필요하다
fib(4) 를 구할 때 fib(3) 을 또 계산한다
아래로 내려갈수록 같은 계산이 기하급수로 늘어난다

한 번 구한 값을 저장해 두면 각 항을 한 번씩만 계산하므로 항의 수에 비례하게 줄어듭니다.

반대로 부분 문제가 겹치지 않으면 저장할 이유가 없습니다. 합병 정렬은 왼쪽과 오른쪽을 각각 한 번만 풀기 때문에 저장해도 다시 쓸 일이 없고, 이런 구조를 분할 정복이라고 합니다.

흔한 실수: 재귀를 쓰면 동적 계획법이라고 답하는 것. 재귀는 구현 방식이고, 핵심은 중복되는 계산을 저장해 다시 쓴다는 점입니다. 반복문으로 아래에서 위로 채워도 동적 계획법입니다.

현재 계산에 실제로 필요한 만큼만 남깁니다. 표 전체를 들고 있을 필요가 없는 경우가 많습니다.

배낭 문제처럼 표를 채우는 문제에서 다음 줄을 계산할 때 필요한 것이 이전 줄뿐이라면, 줄 두 개만 번갈아 쓰면 됩니다. 항목 수와 무관하게 메모리가 고정됩니다.

대가가 있습니다. 최적값은 구할 수 있지만 어떤 선택으로 그 값이 나왔는지 되짚을 수 없습니다. 경로를 알아야 하면 표를 남기거나 별도로 기록해야 합니다.

흔한 실수: 메모리를 줄이는 것을 항상 좋은 최적화로 답하는 것. 최적값만 필요한지 선택 경로까지 필요한지에 따라 갈립니다. 경로가 필요한데 줄여 버리면 다시 풀어야 합니다.