메모이제이션 문서 원본 보기

[include(틀:프로젝트 문서,프로젝트=나무위키 컴퓨터 프로젝트)]

 * 상위 항목 : [[동적 계획법]]

Memoization

'''Memory'''zation이 아니다. 메모리를 사용하긴 하지만, [[메모]]에 초점이 맞춰진 단어이기 때문.

[목차]

== 개요 ==
[[컴퓨터]] [[프로그래밍]] 용어로, 같은 계산을 여러 번 해야 할 때, 한 번 계산한 결과를 메모리에 저장해 이후 동일한 계산 과정을 생략할 수 있게 하는 기법이다.
[[동적 계획법]]의 핵심이 되는 기술이다.

== 예시 ==
가장 흔하게 사용되는 예시는 [[피보나치 수열]]이다.
n번째 피보나치 수열을 구하는 [[재귀함수]]를 f(n)이라 하자. 그러면 4번째 피보나치 수열은 f(4), 즉 f(4) = f(3) + f(2) 이다. 
f(3)과 f(2)는 전과 같은 방법으로 구하고, f(1), f(0)까지 간다면 그 그림은 다음과 같다.
[[파일:Memoization.jpg|width=60%]]

위와 같이 4번째 피보나치 수열을 구하는 데 f() [[함수#s-2]]를 호출하는 횟수는 총 9번이다. 위의 예시에서 중복되어 계산되는 값만 따져봐도 f(2)가 2번(+1번), f(1)이 3번(+2번), f(0)이 2번(+1번) 계산된다. 9번의 계산 중에 무려 '''4번'''이 중복되어 계산된 셈이다. 비록 이 예시는 비교적 작은 값을 제시했지만, 피보나치 수열을 일반적으로 구하는 데 걸리는 [[시간복잡도]]는 [[피보나치 수열]]의 값에 비례한다. 즉 O(<math>1.6^N</math>)라는 것이다.[* Intel i5-4200m 쿼드코어 기준 f(45)를 구하는데 8~9초 정도 소요된다.] 일반적인 방법을 [[C(프로그래밍 언어)|C언어]]로 구현해 보면 다음과 같다.[* [[재귀함수]] 문서를 참고하면 전체적인 방법을 이해하는데 훨씬 수월할 것이다.]

{{{#!syntax cpp
#include <stdio.h>
int f(int num){
    if(num<2) return num;
    return f(num-1)+f(num-2);
}
int main(void){
    int N;
    scanf("%d", &N);
    printf("%d", f(N));
    return 0;
}
}}}
이 방법은 위의 사진과 완전히 동일한 방법인데, f(num)을 f(num-1)과 f(num-2)로 나눠 각각의 f()를 계속 구하는 과정을 거듭한다. 
여기서 미리 구한 f(1), f(2), ... , f(n-1)을 다음에 사용할 때 하위 계산 과정 없이 사용하기 위해 메모리에 집어넣게 되면, [[시간복잡도]]는 무려 O(N)으로 줄어든다!

다음은 f()값을 저장하는 [[배열]]을 Memo[]로 선언하여 작성한 [[C(프로그래밍 언어)|C언어]] 코드이다.

{{{#!syntax cpp
#include <stdio.h>
#define Size 1000
int Memo[Size]={0, 1, 1, };
int f(int num){
    if(!num || Memo[num]) return Memo[num];
    Memo[num]=f(num-1)+f(num-2);
    return Memo[num];
}
int main(void){
    int N;
    scanf("%d", &N);
    printf("%d", f(N));
    return 0;
}
}}}
쪼개서 구할 수 없는 Memo[1]과 Memo[2]는 1로 미리 초기화시켜놓고, 그 이후의 값들은 처음으로 구할 때 Memo[num]에 저장하는 방식이다.
이 값이 저장되어 있으면 다음에 구하려 할 때 가져다 사용할 수 있다. 다시 말하여, 계산하는 시간과 메모리 공간을 맞바꾸는 셈이다.--등가교환--

[[분류:프로그래밍 이론]] [[분류:전산학/컴퓨팅 방법론]]