[파이썬] 피보나치 수열 (1) memoization로 구현 - 다이나믹 프로그래밍 ★

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요.

fib_memo는 꼭 memoization 방식으로 구현하셔야 합니다!

실습 결과

# 캐시에 담긴 n번째 피보나치 수를 반환
def fib_memo(n, cache):
    #base case
    if n <= 2:
        return 1
    
    # 캐시에 저장된 피보나치 수가 있으면?
    if n in cache:
        return cache[n]
    # 캐시에 없으면, 캐시에 저장
    else:
        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