동적 계획법

동적 계획법

현재 문제를 작은 문제로 나눈 뒤 작은 문제의 답을 구하고,

작은 문제로부터 현재 문제의 답을 구하는 알고리즘

분할정복 vs 동적 계획법

동적 계획법은 현재 문제를 부분문제로 나눈 뒤 현재 문제의 답을 구한다는 점에서 분할정복과 비슷하지만

분할 정복은 부분문제를 한번만 계산하게 되는 반면,

동적 계획법은 같은 부분문제를 여러 차례 계산한다.

따라서 중복적인 계산을 피하기 위해 메모이제이션 기법이 반드시 필요하며, 

두번 이상 계산되는 부분문제를 중복되는 부분문제 (overlapping subproblems) 라고 부른다.

(a)는 분할 정복 (b)는 동적 계획법

메모이제이션

동적 계획법의 반복적인 부분 문제 계산 예

bino(2, 1)은 

• bino(3, 1) 을 계산할 때 필요
• bino(2, 1) 을 계산할 때도 필요

입력 n과 r 이 정해져 있을 떄 bino(n, r) 의 반환값이 일정

∴ 한번 계산한 값을 저장해 뒀다가 재활용하는 최적화 기법을 사용해야 함

이와 같이 

두번이상 반복 계산되는 부분 문제들의 답을 미리 저장함으로써, 속도의 향상을 꾀하는 알고리즘 설계 기법을 동적 계획법이라고 한다.

메모이제이션 주의 할 점

메모하려는 값이 참,거짓 이어도 불리언 타입으로 메모이제이션을 하면 안됨.

불리언 배열을 캐시로 사용해서는 아직 계산되지 않은 상태인지 아닌지 알 수 없기 때문.

따라서 캐싱을 정수형으로 1, 0 값을 가진다고 설계하고 -1 로 초기화 하여 사용.

최적화 동적 계획법 레시피

1. 모든 답을 만들어 보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.
2. 전체의 값을 반환하는 것이 아니라, 앞으로 남은 선택들에 해당하는 값 만을 반환하도록 부분 문제 정의를 바꾼다.
3. 재귀 호출의 입력에 이전 선택에 관련된 정보가 있다면 꼭 필요한 것만 남기고 줄인다.
   문제가 최적 부분 구조에 성립할 경우에는 이전 선택에 관련된 정보를 완전히 없앨 수도 있다.
   입력의 정보가 줄어들면 줄어들수록 더 많은 부분 문제가 중복되고, 따라서 메모이제이션을 최대한 활용할 수 있다.
4. 입력이 배열이거나 문자열인경우 가능하다면 적절한 변환을 통해 메모이제이션을 이용할 수 있도록 한다.
5. 메모이제이션을 적용한다.