메모이제이션


Memoization

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

1 개요

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

2 예시

가장 흔하게 사용되는 예시는 피보나치 수열이다.
n번째 피보나치 수열을 구하는 재귀함수를 f(n)이라 하자. 그러면 4번째 피보나치 수열은 f(4), 즉 f(4) = f(3) + f(2) 이다.
f(3)과 f(2)는 전과 같은 방법으로 구하고, f(1), f(0)까지 간다면 그 그림은 다음과 같다.
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])라는 것이다.[1] 일반적인 방법을 C언어로 구현해 보면 다음과 같다.[2]


<syntaxhighlight lang="cpp" line="1">

  1. 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;
}
</syntaxhighlight>
이 방법은 위의 사진과 완전히 동일한 방법인데, f(num)을 f(num-1)과 f(num-2)로 나눠 각각의 f()를 계속 구하는 과정을 거듭한다.
여기서 미리 구한 f(1), f(2), ... , f(n-1)을 다음에 사용할 때 하위 계산 과정 없이 사용하기 위해 메모리에 집어넣게 되면, 시간복잡도는 무려 O(N)으로 줄어든다!

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


<syntaxhighlight lang="cpp" line="1">

  1. include <stdio.h>
  2. 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;
}
</syntaxhighlight>
쪼개서 구할 수 없는 Memo[1]과 Memo[2]는 1로 미리 초기화시켜놓고, 그 이후의 값들은 처음으로 구할 때 Memo[num]에 저장하는 방식이다.

이 값이 저장되어 있으면 다음에 구하려 할 때 가져다 사용할 수 있다. 다시 말하여, 계산하는 시간과 메모리 공간을 맞바꾸는 셈이다.등가교환
  1. Intel i5-4200m 쿼드코어 기준 f(45)를 구하는데 8~9초 정도 소요된다.
  2. 재귀함수 문서를 참고하면 전체적인 방법을 이해하는데 훨씬 수월할 것이다.