메모이제이션

위키백과 ― 우리 모두의 백과사전.

메모이제이션(영어: memoization)은 컴퓨터 프로그램을 실행할 때 이전에 계산한 값을 메모리에 저장해서 매번 다시 계산하지 않도록 하여 전체적인 실행속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

[편집] 어원 및 역사

‘memoization’은 글자 그대로 해석하면 ‘메모리에 넣기(to put in memory)’라는 의미이며 ‘기억되어야 할 것’이라는 뜻의 라틴어 memorandum에서 파생되었다. 흔히 ‘기억하기’, ‘암기하기’라는 뜻의 memorization과 혼동하지만, 정확한 단어는 memoization이다. 동사형은 memoize이다.

memoization이라는 용어를 처음 만든 사람은 Donald Michie이다. 1968년 네이처에 실린 그의 논문 〈Memo functions and machine learning〉 에서 처음으로 memoization이라는 말이 나왔다.

[편집] 예제

피보나치 수열을 구하는 가장 단순한 방법은 다음과 같다.

fib(n) {
   if n is 1 or 2, return 1;
   return fib(n-1) + fib(n-2);
}

이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6ⁿ)이다. 그러나 fib(n)의 값을 계산하자마자 저장하면(memoize), 실행시간을 Θ(n)으로 줄일 수 있다.

allocate array for memo, setting all entries to zero;
initialize memo[1] and memo[2] to 1;

fib(n) {
   if memo[n] is not zero, return memo[n];
   memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}