차례 Memoization Tabluation 공간 최적화 1. Memoization > 특징 재귀함수를 사용한다. 필요한 만큼만, 불필요한 경우는 제외하여 구한다. 필요한 계산을 요구, 필요하지 않은 경우는 요구하지 않응. 단, 최대 재귀호출 깊이에 제한을 받을 수 있음. Code def fib_memo(n, cache):
if n < 3:
return 1
# 이미 n번째 피보나치를 계산했으면 저장된 값을 바로 리턴한다.
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)) 2.
Continue reading
