상위 질문
타임라인
채팅
관점

메모이제이션

동적 계획법의 핵심이 되는 기술 위키백과, 무료 백과사전

Remove ads

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

어원

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

예제

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

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

이때 fib 함수가 재귀적으로 실행되면서 같은 인자값에 대해서 계속해서 반복되므로, 전체 실행시간은 Ω(1.6n)이다. 그러나 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];
}
Remove ads

적용

같이 보기

각주

외부 링크

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads