1) Memoiztion 방식의 피보나치 함수 (Dynamic Programming)

1) Memoiztion 방식

:  동일한 계산을 반복해야 할 경우 한 번 계산한 결과를 메모리에 저장해 두었다가 꺼내 씀으로써 중복 계산을 방지할 수 있게 하는 기법

 

피보나치 수열은 예를 들어 f(4) = f(3) + f(2) 이다.  f(3)는 f(2) + f(1)이므로

f(4) = f(2) + f(1) + f(2) 이런 과정을 반복해서

표현한 최종적인 f(4)는 f(1) + f(0) + f(1) + f(1) + f(0)와 같다.

 

 

2) Memoiztion 방식의 피보나치 함수

def fib_memo(n, cache):
    if n < 3:
        return 1
    if n in cache:
        return cache[n]

    cache[n] = fib_memo(n - 1,cache) + fib_memo(n - 2,cache)
    return cache[n]


def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}

    return fib_memo(n, fib_cache)

# 테스트
print(fib(10))
print(fib(50))
print(fib(100))

# 결과
 55
 12586269025
 354224848179261915075

 

 

풀이