[알고리즘] - Dynamic Programming (DP)

오늘은 알고리즘 중에서 중요한 DP에 대해서 알아보도록 하자. 

정의 DP란 memory table를 활용한 재귀 연산이라고 할 수 있다. 

---

그렇다면 재귀 연산이란 무엇일까? Recursive Operation이라고도 하는데, 이 알고리즘은 반복하여 계산하는 것과 같다. 이전 포스팅의 Divide and Conquer를 생각해보면, 거기서도 재귀를 사용했었다. 그렇다면 재귀 연산의 간단한 예시를 보도록 하자. 

피보나치 수열은 다음과 같이 정의된다.

$A_{n+2} = A_{n+1} + A_{n}$
where $A_1 = 1, A_2 = 1$

그렇다면 $A(n)$을 구하는데 어떻게 알고리즘을 설계할까? 바로 재귀를 이용해 다음과 같이 설계한다. 

Fib(n) 
  if n == 1 or n == 2 :
   return 1
  else :
   return Fib(n-1) + Fib(n-2)

위에서 보는 것처럼 base case를 n이 1,2일때를 설정하고, 그 이후로 더 큰 숫자들이 들어올 경우에는 정의한 함수를 return할 때 호출하는 식으로 말이다. 사실 여기서 user가 음수를 입력할 것을 대비해 그것에 대한 방어 코딩을 하는 것도 맞겠지만, 쉬운 이해를 위해 간단히 적어봤다. 

그렇다면 이 함수의 복잡도($O$)는 얼마나 될까? 그 과정은 substitution method(수학적 귀납법)을 이용해서 계산할 수 있는데, 간단히 말해 $O(2^n)$이 나온다. 이 복잡도는 정말 큰 것이다. 그럼 이것을 능가할 수 있는 알고리즘이 있는가? 바로 DP를 이용하는 것이다!

---

DP는 재귀와 같지만 다른 것이 memory table(memoization)을 이용하는 것이다. 왜 이것을 하는지 생각해보자. 피보나치 수열의 경우 Fib(5)를 할 경우 Fib(4)와 Fib(3)을 호출하게 되는데 이미 Fib(4)에서 또다시 Fib(3)을 다시 호출하게 된다. 즉, 이미 계산한 것을 또 계산하는 중복이 굉장히 많이 생기기 때문에 복잡도가 증가하는 것이다. 이 문제를 해결하기 위해 memory table을 만들어서 중복 계산을 피하겠다는 것이다. 그렇다면 이것을 피보나치 수열을 구하는 알고리즘에 적용하면 어떨까?

Fib(n)
  if memo[n] is undefined :
    if n <= 2 :
      return 1
    else :
      f = Fib(n-1) + Fib(n-2)
      memo[n] = f
      return f
  else:
    f = memo[n]
    return f

보는 바와 같이 memo 테이블에 계산한 것들을 저장하게 된다. 그렇다면 이 알고리즘의 복잡도는 어떻게 될까?

간단히 말하면 DP 알고리즘의 복잡도 계산은 다음과 같이 한다.

# of subproblems(size of table) * time per subproblem 

여기서 size of table은 memory table의 크기라고 생각하면 된다. 그러니, 여기서는 n이다. 그리고 subproblem을 하는데 걸리는 시간인데, 여기서는 두 결과를 더하는데 걸리는 시간을 말한다. 그러므로 여기서는 1에 해당한다.

그러므로 이 알고리즘의 복잡도는 $O(n)$이 된다! 

재귀를 이용했을 때 $O(2^n)$에서 $O(n)$이 된다니 대단하지 않은가? 실제로 이 알고리즘을 파이썬이나 C로 구현해보면 차이가 나는 것을 확인할 수 있다. 이 알고리즘은 꼭 알아두면 좋은 방법이라고 할 수 있다.