더북(TheBook)

호출 그래프는 함수 프레임들을 보여주고 있으며, 각 프레임은 프레임이 호출하는 함수의 프레임을 선으로 연결하고 있다. 호출 그래프의 최상층에서 n=4fibonacci에서 n=3n=3 fibonacci를 호출한다. 차례대로 n=3 fibonaccin=2n=1fibonacci를 호출한다. 이런 식으로 호출이 이어진다.

fibonacci(0)fibonacci(1)이 호출되는 횟수를 세어보라. 이는 문제에 대한 해법이 비효율적인 데다가 인수가 커질수록 더 비효율적으로 된다.

한 가지 해법은 이미 계산한 값을 사전에 저장하면서 관리하는 것이다. 앞서 계산한 값을 나중에 사용하기 위해 저장하는 것을 메모(memo)라고 부른다. 다음은 fibonacci메모화(memoized) 버전이다.

known = {0:0, 1:1}

def fibonacci(n):

if n in known:

return known[n]

res = fibonacci(n-1) + fibonacci(n-2)

known[n] = res

known은 이미 알고 있는 피보나치 수를 관리하기 위한 사전이다. 사전은 처음에는 두 항목을 갖는다. 즉, 00으로, 11로 연결된 항목을 갖는다.

fibonacci가 호출되면 known을 확인한다. 결과가 이미 있으면 즉시 결과를 반환한다. 그렇지 않으면 새로운 값을 계산해서 사전에 추가하고 반환한다.

메모화 버전의 fibonacci를 실행하고 원래 버전과 비교해보면 메모화 버전이 훨씬 더 빠르다.

신간 소식 구독하기
뉴스레터에 가입하시고 이메일로 신간 소식을 받아 보세요.