728x90
피보나치 수열(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
'📊 Algorithm > Algorithm PS' 카테고리의 다른 글
[알고리즘 일기] 19. 피보나치 수열(최적화) (0) | 2021.05.19 |
---|---|
[알고리즘 일기] 18. 피보나치 수열(Tabulation) (0) | 2021.05.18 |
[알고리즘 일기] 16. 퀵 정렬(3) (0) | 2021.05.16 |
[알고리즘 일기] 15. 퀵 정렬(2) (0) | 2021.05.15 |
[알고리즘 일기] 14. 퀵 정렬(1) (0) | 2021.05.15 |