728x90

문제 17. (2021-05-17)

 

피보나치 수열(Memoization)

n번째 피보나치 수를 찾아주는 함수 fib_memo를 memoization 방식으로 구현해 보세요.

 

 

❧ 테스트 셋

def fib_memo(n, cache):
    # Code


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

    return fib_memo(n, fib_cache)


# Test
print(fib(10))
print(fib(50))
print(fib(100))

 

❧ 출력 예시

55
12586269025
354224848179261915075

 


❧ 정답

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)

# Test
print(fib(10))
print(fib(50))
print(fib(100))

 

 

728x90

 

728x90