수학에는 Fibonacci(피보나치 수)라는 수가 있습니다. 아직 이것이 어디에 사용되는지 확인할 방법은 없지만… 그래도 프로그래밍 쪽에서는 꽤나 많은 예제로 등장하는 문제입니다. Recursive나 Iterative을 보여주는 예제로도 많이 사용되고, 특히나 이번에 소개해 드릴 Dynamic programming 측면에서 자주 예제로 등장하는 개념입니다. 간단하게 정의하면, \[F_n=\begin{cases} &0 &\text{if }n=0 \newline &1 &\text{if }n=1 \newline &F_{n-1}+F_{n-2} &\text{if }n>1\end{cases}\] 이런 형태의 수입니다. 그러면 우리가 가장 쉽게 구현할 수 있는 Recursive 방법으로 구현해 보겠습니다.

def fibonacci_recursive(n):
    if n==0:
    	return 0
    if n==1:
        return 1
    return fibonacci_recursive(n-1) + fibonacci_recursive(n-2)

>>> for i in range(1, 11): #첫번째부터 10번째까지 Fibonacci 수를 출력해 봅시다.
>>>     print fibonacci_recursive(i)
1
1
2
3
5
8
13
21
34
55

결과가 잘 출력되네요 :) 그런데 문제가 무엇일까요? img

바로 \[\begin{aligned} T(n) &= T(n-1)+T(n-2) + 1 \newline &< 2T(n-1)+1\newline &= 4T(n-2)+2+1\newline &=…\newline &\approx O(2^n)\end{aligned}\] 어마무시한 complexity를 갖게 된다는 점입니다…ㅠ 조금만 큰 수를 넣어도 컴퓨터가 버거워서 견디지를 못하네요 ㅠ 그럼 이제 Dynamic programming이라는 개념을 이해하면서 얼마나 효율적인지 알아보도록 합시다. 먼저 어떻게 동작을 하는지 그림으로 쉽게 이해해 봅시다.

img2

Dynamic programming의 핵심은 메모리를 조금 더 쓰는 대신에 complexity에서 크게 이득을 보는 것입니다. 만약 우리가 위의 그림의 오른쪽처럼 한번 쭉 $F_1$까지 구한 다음에 그 결과 값을 메모리로 저장하고 있다고 가정해 봅시다. 그렇게 되면 그림과 같이 이미 구했던 값들은 더 이상 아래로 가지를 쳐가면서 또 구하고 있을 필요가 없게되는 것입니다!! 획기적이지 않습니까!?ㅎㅎ 이렇게 되면 complexity도 \[T(n)\approx O(n)\] 으로써 무려 linear complexity로 감소하게 됩니다!! 와우… 그럼 이제 구현을 해보도록 합시다.

def fibonacci_dynamic(n, cache=dict()):
    if n==1 or n==2:
        return 1

    ### 이 부분이 포인트입니다! cache라는 메모리 변수를 이용하는 것이죠!
    if n in cache:
        return cache[n]
    ### 리턴하기 전에 반드시 메모리에 기록하고 리턴해야합니다!
    cache[n] = fibonacci_dynamic(n-1, cache) + fibonacci_dynamic(n-2, cache)
    return cache[n]

>>> for i in range(1, 11): #첫번째부터 10번째까지 Fibonacci 수를 출력해 봅시다.
>>>     print fibonacci_recursive(i)
1
1
2
3
5
8
13
21
34
55

결과는 맞게 나오니 이제 시간을 비교해 보죠 :)

>>> from time import time
>>> n = 30
>>> t0 = time()
>>> print fibonacci_recursive(n)
832040
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 3.23e-01

>>> t0 = time()
>>> print fibonacci_dynamic(n)
832040
>>> print "걸린시간 : %.2e" % (time()-t0)
걸린시간 : 1.55e-04

으악.. 거의 2000배 가까이 차이가 나는게 보이시나요?? 그것도 $n=30$밖에 안됐는데 말이죠.. 보시는바와 같이 Dynamic programming의 힘은 상상을 초월한답니다! 메모리 기술의 발달로 큰 메모리도 얼마든지 사용할 수가 있기 때문에 더욱더 파워풀해지겠죠?