동적 계획법(Dynamic Programming)

복잡한 문제를 간단한 여러 개의 문제로 나누어 푸는 방법

 

흔히 말하는 DP가 바로 '동적 계획법'

한 가지 문제에 대해서, 단 한 번만 풀도록 만들어주는 알고리즘이다.

즉, 똑같은 연산을 반복하지 않도록 만들어준다. 실행 시간을 줄이기 위해 많이 이용되는 수학적 접근 방식의 알고리즘이라고 할 수 있다.

 

동적 계획법은 Optimal Substructure에서 효과를 발휘한다.

Optimal Substructure : 답을 구하기 위해 이미 했던 똑같은 계산을 계속 반복하는 문제 구조

 

접근 방식

커다란 문제를 쉽게 해결하기 위해 작게 쪼개서 해결하는 방법인 분할 정복과 매우 유사하다. 하지만 간단한 문제로 만드는 과정에서 중복 여부에 대한 차이점이 존재한다.

모든 답을 만들어보고 그 중 최적해의 점수를 반환하는 완전 탐색 알고리즘을 설계한다.

즉, 동적 계획법은 간단한 작은 문제들 속에서 '계속 반복되는 연산'을 활용하여 빠르게 풀 수 있는 것이 핵심이다.

 

조건

• 작은 문제에서 반복이 일어남
• 같은 문제는 항상 정답이 같음

이 두 가지 조건이 충족한다면, 동적 계획법을 이용하여 문제를 풀 수 있다.

같은 문제가 항상 정답이 같고, 반복적으로 일어난다는 점을 활용해 메모이제이션(Memoization)으로 큰 문제를 해결해나가는 것이다.

 

메모이제이션(Memoization) : 한 번 계산한 문제는 다시 계산하지 않도록 저장해두고 활용하는 방식

 

피보나치 수열에서 재귀를 활용하여 풀 경우, 같은 연산을 계속 반복함을 알 수 있다.
이때, 메모이제이션을 통해 같은 작업을 되풀이 하지 않도록 구현하면 효율적이다.

 

fibonacci(5) = fibonacci(4) + fibonacci(3)
fibonacci(4) = fibonacci(3) + fibonacci(2)
fibonacci(3) = fibonacci(2) + fibonacci(1)

이처럼 같은 연산이 계속 반복적으로 이용될 때, 메모이제이션을 활용하여 값을 미리 저장해두면 효율적

피보나치 구현에 재귀를 활용했다면 시간복잡도는 O(2^n)이지만, 동적 계획법을 활용하면 O(N)으로 해결할 수 있다.

 

구현 방식

1. Bottom-up : 작은 문제부터 차근차근 구하는 방법
2. Top-down : 큰 문제를 풀다가 풀리지 않은 작은 문제가 있다면 그때 해결하는 방법 (재귀 방식)

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]
}

Bottom-up은 해결이 용이하지만, 가독성이 떨어짐

Top-down은 가독성이 좋지만, 코드 작성이 힘듬

 

동적 계획법으로 문제를 풀 때는, 우선 작은 문제부터 해결해나가보는 것이 좋다.

작은 문제들을 풀어나가다보면 이전에 구해둔 더 작은 문제들이 활용되는 것을 확인하게 된다. 이에 대한 규칙을 찾았을 때 점화식을 도출해내어 동적 계획법을 적용시키자