7. Dynamic Programming

한번 (1,1)에서 (4,4)까지 갈 수 있는 path를 계산해봅시다.

갈 수 있는 모든 경우의 수를 다 고려한다면, 정답을 구할 수 있을 것입니다. 하지만 이는 꾀나 비효율적인 방법입니다. 아래의 그림은 가능한 모든 경우의 수를 그래프로 나타낸 것입니다.

가능한 모든 경우의 수

그래프를 보시면, 반복되는 구간이 많은 것을 알 수 있습니다. Recursion 개념을 사용해 (i,j)에서 (4,4)로 갈 수 있는 path를 생각해보면 어떨까요? 반복되는 구간을 중복해서 계산하지 않고 처리할 수 있을 것입니다. 이 방법을 Memoization이라고 합니다.

Function

Memoization을 사용할 경우, 위의 문제에 대한 Time complexity는 $O(2^{2n-1})$이 됩니다.

 

Dynamic Programming

문제의 solution을 subproblem의 solution에 기반해서 해결하는 방법입니다. Divide-and-conquer에서 했던 것처럼 문제를 subproblem으로 나누고, subproblem의 solution을 저장해서 사용하는 것이 특징입니다. Divide-and-conquer와 다른 점은 Divide-and-conquer와는 다르게 subproblem이 subsubproblem을 공유하는 경우에만 Dynamic Programming을 사용할 수 있습니다. (Divide-and-conquer는 공유하지 않아도 됨)

 

• 문제를 가장 작은 수준까지 나누기
• 작은 문제 해결하기
• Solution들을 저장해서 사용하기

 

Example: Fibonacci number

Function

Top-down approach

계속해서 해왔던 방법입니다.

Top-down approach

$T(n) = O(2^n)$을 보여줍니다.

 

Bottom-up approach

계산 결과를 저장해서 사용하게 됩니다.

Bottom-up approach

중복되는 계산이 사라져서, $T(n) = O(n)$이 됩니다.

 

Example: Logest common subsequence

두 string 사이에 공통된 subsequence 중 제일 긴 것을 찾는 문제입니다.

Example

Function

Algorithm

$T(n) = O(mn)$을 보여줍니다.