[DP] 피보나치 수열 메모이제이션

문제

n번째 피보나치 수를 찾아주는 함수 fib_memo을 작성하기.

fib_memo는  memoization 방식으로 구현한다.

내 코드(통과)

• 엄밀히 얘기하면, 재귀가 아니라 for문을 사용한 것.
• 예를 들어 n 이 8이면 그 전까지의 수들을 계산해서 하나하나 딕셔너리에 넣어준 것이다.
• 이를 재귀함수로 구현할 수 있다.

수정하면 좋을 부분

• def fib(n) 을 수정하는 것이 아니라, fib_memo 함수만 수정해야 한다.
• 사전에 n 이 있으면 그대로 출력하고, 없다면 만들어내는 형식으로 작성한다.

def fib_memo(n, cache):
    # 코드를 작성하세요.
    if n == 1 or n == 2:
        return cache[1]
    else:
        return cache[n-2] + cache[n-1]
    
def fib(n):
    # n번째 피보나치 수를 담는 사전
    fib_cache = {}
    fib_cache[1] = 1
    fib_cache[2] = 1
    if n >= 3:
        for i in range(3, n):
            fib_cache[i] = fib_cache[i-1] + fib_cache[i-2]
    return fib_memo(n, fib_cache)

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

 

접근법

• base case의 경우 딕셔너리 들를 필요 없이 바로 1을 리턴
• recursive case의 경우 딕셔너리를 호출하는데, 이때 n 번째 피보나치 수가 계산된 경우와 계산되지 않은 경우로 분리
  • cache[n] 이 존재하는 경우: 저장된 값을 바로 리턴한다.
  • cache[n] 이 존재하지 않는 경우: 계산을 한 후 chache에 저장하고, 이후 계산한 값을 리턴한다.

수정코드

def fib_memo(n, cache):
    # base case
    if n < 3:
        return 1

    # recursive case
    # 이미 n번째 피보나치를 계산했다면
    # 저장된 값을 바로 리턴한다.
    if n in cache:
        return cache[n]

    # 아직 n번쨰 피보나치수를 계산하지 않았다면
    # 계산을 한 후 cache에 저장하고 리턴한다.
    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))