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