알고리즘 동적 계획법
분할정복과 동적 계획법
각 부문제의 해답을 단 한번만 풀어서 저장하고 나주에 같은 부문제의 답이 필요한 경우 간단하게 저장된 해답을 찾아서 해결한다. 주어진 문제가 여러 차례 재사용 가능한 중복된 부문제들로 쪼개지는 경우 중첩된 부문제(overlapping subproblems) 특성을 갖는다고 하며 동적 계획법은 중첩된 부문제 특성이 있는 문제에 적합하다. 쪼개진 부문제들이 중첩되지 않는다면 동적 계획법이 가진 장점을 제대로 발휘할 수 없으며 최종 해단에 사용되지 않을 답들을 계산하느라 많은 시간을 낭비할 우려가 있다.
- 분할 정복은 큰 문제를 작은 문제로 쪼갠 후 부문제를 해결하려는 전략이므로 크기가 큰 문제에서 작은 문제로 줄여나가는 하향식 기법이다.
- 동적 계획법은 부문제를 풀고 이를 이용하여 더 큰 문제를 해결하는 전략을 사용하기 때문에 작은 문제에서 큰 문제로 향하는 상향식 기법 이다.
욕심쟁이 방법과 동적 계획법
부문제들의 최적해로부터 주어진 문제의 최적해를 효율적으로 생성할 수 있다면 욕심쟁이 방법 또는 동적 계획법을 사용할 수 있다. 욕심쟁이 방법은 최적해를 보장하지는 않지만 빠르다는 장점이있고, 동적 계획법은 최적부분구조를 갖는 최적화 문제에 대하여 최적해를 반드시 찾아준다.
- 욕심쟁이 방법은 최적해의 일부를 먼저 선택한 후 남은 부문제를 해결하려는 전략이므로 크기가 큰 문제에서 작은 문제로 줄여나가는 하향식 기법 이다.
- 동적 계획법은 이와 반대인 상향식 기법 이다.
동적 계획법의 적용
- 최적화 문제의 경우 최적 부분구조를 갖는지 검증한다.
- 문제를 순환적으로 정의한다.
- 중첩된 부문제 특성을 갖는지 조사한다.
- 부문제의 해답을 저장하고 이로부터 최적해를 구성하는 알고리즘을 구축한다.
메모이제이션
하향식 분할정복 알고리즘에서, 이미 해결한 문제의 답을 저장한 후 동일한 문제를 풀 필요가 있을 때 재사용할 수 있다면 어떨까? 이미 풀어놓은 문제가 다시 사용되는 알고리즘의 경우 부문제의 해답을 저장하여 재사용한다. 부분적인 결과들을 기록한 후 나중에 필요할 때 다시 계산할 필요 없이 재사용하는 기법 을 메모이제이션이라고 한다.