Dynamic Programming (DP, 동적 계획법, 동적 프로그래밍)

Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고, 하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.

길이 막힐 때 돌아가는 길로 가는 것이 더 빠르게 도착한다는 사실을 알고 있다면 같은 상황에서 돌아가는 길을 계속 선택한다. 그럼 결국 최적의 경로를 찾게 된다.

다시 말하면 최종 문제를 해결하는 많은 방법들을 모두 탐색하게 된다. 하위 문제들 각각의 해결 방법들을 모두 탐색하기 때문이다. 하지만, 반복되는 하위 문제를 찾아 간단히 해결하도록 만드는 것으로 계산 횟수를 줄일 수 있다.

DP 에는 두 가지 구현 방식이 존재한다.

• top-down : 여러 개의 하위 문제(sub-problem) 나눴을시에 하위 문제를 결합하여 최종적으로 최적해를 구한다.
  • 메모이제이션 (memoization) : 같은 하위 문제를 가지고 있는 경우가 존재한다. 그 최적해를 저장해서 사용하는 경우 하위 문제수가 기하급수적으로 증가할 때 유용하다.
• bottom-up : top-down 방식과는 하위 문제들로 상위 문제의 최적해를 구한다.
  • 상향식 동적 프로그래밍 : fibonacci(1)과 fibonacci(0)을 계산한다. 이 후, 그 둘을 사용해 2,3,4,...을 계산해나간다.

접근 방법

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

예시

Fibonacci 수열을 예로 들어보면,

top-down
f (int n) {
  if n == 0 : return 0
  elif n == 1: return 1
  if dp[n] has value : return dp[n]
  else : dp[n] = f(n-2) + f(n-1)
         return dp[n]
}

bottom-up
f (int n){
  f[0] = 0
  f[1] = 1
  for (i = 2; i <= n; i++) {
   f[i] = f[i-2] + f[i-1]
  }
  return f[n]
}

Greedy (탐욕법)