[Algorithm] 다이나믹 프로그래밍 (Dynamic Programming)

다이나믹 프로그래밍 (Dynamic Programming) 이란 재귀 (recursion)와 메모이제이션 (memoization) 을 사용하여 문제를 해결하는 기법입니다.

 

memoization 은 recursive function 의 중간 결과를 저장하는 기법인데 말로 하면 와닿지 않으니 피보나치 수를 구하는 문제를 해결하며 다이나믹 프로그래밍과 메모이제이션에 대해 이해해보도록 하겠습니다.

 

Fibonacci Number.

0을 포함한 자연수 n에 대해서 n-th Fibonacci Number Fn 은 다음과 같이 정의합니다.

 

F0 = 0, F1 = 1

Fn = Fn-1 + Fn-2 (for n > 1)

 

얘를 들면 F5는 다음과 같습니다.

F0=0, F1=1 일 때 F5

이제 재귀(Recursion)을 이용하여 Fibonnaci Number 의 일반항 Fn을 계산하는 알고리즘을 짜보겠습니다. (Python)

      

      

      

    
    

      <python />
    
def fibo(n):
    if n == 0:
        return 0
    
    if n == 1:
        return 1

    return fibo(n-1) + fibo(n-2)

이 알고리즘의 시간복잡도는 어떻게 계산할 수 있을까요?

 

T(n) 을 Fibo(n) 의 답을 얻을 때 까지 필요한 총 addtion 의 횟수라고 정의하면, 다음과 같은 Recurrence Relation 을 얻을 수 있습니다.

 

재귀함수를 이용한 fibonacci number 를 구하는 데 소요되는 time complexity

이 Recurrence Realtion 을 해결하면 T(n) 은 약 (1.618) ^ n 이 나옵니다. 모든 exponential 의 극한이 polynomial 을 dominant 한다는 것을 생각해보면 exponential 형태의 시간복잡도는 소요시간이 굉장히 긴 것을 의미합니다.

 

이렇게 느린 이유는 무엇일까요? fibo(7)을 호출할 때의 recursion tree를 살펴보며 그 이유를 알아봅시다.

 

fibo(7) 호출 시의 recursion tree

빨간색 동그라미 친 부분을 보면 F7을 구하기 위해서 F3을 5번이나 계산해야 합니다. 즉 같은 값을 여러번 계산해야 한다는 점이 문제가 되는 것입니다.

 

그렇다면, 같은 값을 여러번 쓸 것 같다면 한 번 계산하고 저장해뒀다가 필요할 때 꺼내쓰면 이런 문제를 해결할 수 있습니다. 이와 같이 중간 결과를 저장하는 방법을 memoization 이라고 합니다.

 

      

      

      

    
    

      <python />
    
global F

F = [0] * 100000
F[0] = 0
F[1] = 1

def fibo(n):
    if n == 0:
        return 0
    
    if n == 1:
        return 1

    F[n] = F[n-1] + F[n-2]

    return F[n]

위 코드는 메모이제이션을 적용하여 fibonacci number 를 구하는 코드입니다. 이 알고리즘의 time complexity 는 O(n)입니다.

 

이렇게 memoization 을 이용해서 recursion 을 smart 하게 수행하는 방법이 바로 다이나믹 프로그래밍(Dynamic Programming) 입니다.

 

Dynamic Programming 으로 문제를 해결하는 절차는 다음과 같습니다.

 

1. 문제를 정확하게 정의하기. (구하고자 하는 것이 무엇인지 정확하게 파악해야 합니다.)

2. 정의된 문제에 대한 subproblem 을 정의한 뒤 subproblem 을 이용한 recurrence relation 을 세우기. (subproblem 이란 본래 문제보다 size가  작은 문제를 의미합니다. fibonacci 문제에서는 fn' (n' < n) 이 subproblem입니다.)

3. Memoization 을 이용하여 recurrence relation 을 계산

• 중간 결과물들을 저장할 자료구조 (Data Structure) 를 골라야합니다. 보통은 n차원 array 를 사용합니다.
• Subproblem 들 간의 dependency 를 확인합니다. ( fibonacci 문제의 Fn을 구하려면 어떤 subproblem 들을 계산해두어야 할까요? 바로 Fn-1과 Fn-2 입니다.)
• Dependency 에 기반하여 subproblem 들의 답을 구하는 순서를 정해야합니다. ( fibonacci 문제는 1차원 array 이므로 그냥 순차적으로 구하면 됐습니다.)

4. Time Complexity 분석 및 알고리즘을 작성하기.