피보나치 수Fibonacci numbers와 메모이제이션memoization

Q. 메모이제이션이란?

글자 그대로 해석하면 ‘메모리에 넣기’라는 의미. 출처. 위키백과

 

피보나치 구현 예

def fib(n):
    if n == 1 or n == 2:
        return 1
    return fib(n-1) + fib(n-2)
fib(10)

실행결과는 55이다.

 

메모이제이션을 활용해서 피보나치 구현 예

memo = {}
memo[1] = 1
memo[2] = 1
def fib(n):
    if n not in memo:
        memo[n] = fib(n-1) + fib(n-2)
    return memo[n]
fib(10)

똑같이 실행결과는 55이다.

 

속도차이를 비교해보자.

그냥 구현한 경우 50을 구하는데 얼마나 걸릴까. 끝나지를 않는다. 계속 돌고 있다.

 

메모이제이션을 활용한 경우 금방 끝난다. 이미 구한 경우는 재활용하니까.

메모이제이션