다이나믹 프로그래밍 1편

종만북, JM북이라고 알려진 구종만님의 알고리즘 문제 해결 전략 이라는 책을 통해 공부한 부분을 블로그에 정리하고자 합니다. 잘못되거나 부족한 부분이 있으면 언제든 댓글로 가르침 부탁드립니다.

1. 다이나믹 프로그래밍이란?

주어진 문제를 더 작은 문제로 나눈 뒤 각 작은 문제의 답을 구하고, 이를 큰 문제의 답을 구하는데 사용하는 알고리즘 풀이 방법이다. 이는 문제의 답을 여러 번 계산하는 대신 한 번만 계산하고 계산 결과를 재활용함으로써 속도의 향상을 꾀한다. 그러기 위해서는 각 문제의 답을 메모리에 저장해두는데 이를 캐시 라고 부르며, 두 번 이상 계산되는 부분 문제를 중복되는 부분 문제(overlapping subproblems) 라고 부른다.

2. 메모이제이션

함수의 결과를 저장하는 장소를 마련해 두고, 한 번 계산한 값을 저장해 뒀다 재활용하는 최적화 기법을 메모이제이션(momoization) 이라고 부른다. 메모이제이션을 적용하기 위해서는 참조적 투명성 이 성립해야 한다.

참조적 투명성 이란 입력이 같으면 출력도 항상 같은 함수를 의미한다.

3. 풀이 방법

풀이는 크게 2단계이다.

1. 주어진 무제를 완전 탐색을 이용해 해결한다.
2. 중복된 부분 문제를 한 번만 계산하도록 메모이제이션을 적용한다.

코드는 다음과 같이 5단계로 나눠진다.
단, 기저사례의 경우 recursive 함수 호출 직전에 조건문으로 제한해도 상관없다.

dfs(int param){

  // 1. 기저사례
  if(param < 0 || N < param) return false;

  // 2. 종료조건
  if(param == N) ...

  // 3. 메모이제이션
  if(cache[param] != -1) return cache[param];

  // 4. 풀이(recursive 활용)
  answer = ...;

  // 5. 메모이제이션 저장
  return cache[param] = answer;

}