메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 동일한 계산을 반복해야 할 때, 이전에 계산한 값을 메모리에 저장함으로써 동일한 계산의 반복 수행을 제거하여 프로그램 실행 속도를 빠르게 하는 기술이다. 동적 계획법의 핵심이 되는 기술이다.

어원 및 역사

메모이제이션은 글자 그대로 해석하면 ‘메모리에 넣기’라는 의미이며 ‘기억되어야 할 것’이라는 뜻의 라틴어 memorandum에서 파생되었다. 흔히 메모라이제이션(memorization)과 비슷하지만 구분되는 용어이다.

메모이제이션이라는 용어를 처음 만든 사람은 도널드 미치(Donald Michie)이다. 1968년 네이처에 실린 논문 〈Memo functions and machine learning〉에서 처음으로 메모이제이션이라는 말이 나왔다.

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

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 zero:
       memo[n] = fib(n-1) + fib(n-2);
   return memo[n];
}