[Dynamic Programing] 피보나치 수열 Memoization

실습 설명

n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성해 보세요.
 
fib_memo는 꼭 memoization 방식으로 구현하셔야 합니다!
- memoization(중복되는 계산은 한번만 계산 후 메모(재귀 함수 사용), 중복되는 부분 문제에 대한 비효율성 해결)
 

def fib_memo(n, cache):
    # 여기에 코드를 작성하세요
    # base case
    if n < 3: # 피보나치 수열의 첫 번째 수와 두번째 수는 1로 정해져있다.
        return 1
    
    # recursive case
    if n in cache: # 이미 n번째 피보나치를 계산했으면
        return cache[n] # 저장된 값 바로 리턴
    
    # 아직 n번째 피보나치 수를 계산하지 않았다면
    # 계산한 후 cache에 저장
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    
    # 계산한 값 return
    return cache[n]


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

    return fib_memo(n, fib_cache)


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

해결과정
base case: n이 1이거나 2일때 그냥 1로 정해져있음.
recursive case: 
fib_memo(n, cache)를 호출했다고 가정했을 때…

• 이미 n번째 피보나치 수를 계산한 경우, 즉 cache[n]이 존재하는 경우
• 아직 n번째 피보나치 수를 계산하지 않은 경우, 즉 cache[n]이 존재하지 않는 경우