상위 질문
타임라인
채팅
관점
메모이제이션
동적 계획법의 핵심이 되는 기술 위키백과, 무료 백과사전
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
적용
같이 보기
각주
외부 링크
Wikiwand - on
Seamless Wikipedia browsing. On steroids.
Remove ads