메모이제이션

메모이제이션(memoization)은 컴퓨터 프로그램이 복잡한 함수 호출의 결과값을 함수에 저장해놓고, 같은 입력이 반복될 때 저장한 값을 반환하도록 하여 속도를 높이는 최적화 기술이다. 동적 계획법의 핵심이 되는 기술이다.

어원

메모이제이션이라는 용어는 1968년 영국의 인공지능학자인 도널드 미키가 사용하였다. 영어 메모(memo)로 흔히 축약되는 라틴어 단어 메모랜덤(memorandum, '기억되어야 할 것')에서 유래하였다. 같은 유래를 지닌 메모라이제이션(memorization, 기억화)과 비슷하지만 구분되는 용어이다.

예제

피보나치 수열을 계산하는 간단한 방법은 다음과 같습니다.

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];
}

적용

• 검색
• HTML등과 같은소스 코드 생성
• 암호화, 데이터 압축 영상변환과 같은 반복 계산
• 음성 인식과 같은 패턴 인식
• Game tree evaluation

같이 보기

• 계산 복잡도 이론
• 플라이웨이트 패턴
• 느긋한 계산법
• 구체화 뷰

외부 링크

• Memoize.pm - memoize 서브루틴을 구현한 펄 모듈
• Java memoization - memoization 패턴을 만들기 위해 자바에서 dynamic proxy class를 이용한 예제.
• memoize - memoize 패턴을 구현한 루비 모듈
• Python memoization - memoization의 파이썬 구현 예제.