[메모이제이션 - Memoization] 메모이제이션이란?

메모이제이션이란?

메모이제이션이란 입력값에 대한 결괏값을 저장해둠으로써 같은 입력값에 따른 함수의 실행이 중복해서 일어나지 않도록 해주는 기법이다. DP로 문제를 풀 때 자주 등장하며, 함수의 중복 호출을 방지해 효율을 높여준다. 

왜 쓰는가?

피보나치

첫 번째와 두 번째가 1인 피보나치 수를 예로 들어보자. 피보나치 수를 재귀적으로 구한다면 위에서 볼 수 있듯이 fib(3), fib(4)등 앞선 피보나치 수가 여러 번 호출된다.
이때 fib(3), fib(4)이 각각 2, 3인 것을 저장해 두지 않는다면, fib(5), fib(6)이 무엇인지 구하기 위해 fib(3), fib(4)를 다시 구해야 한다.
이때 배열을 하나 만들어 이미 구해진 피보나치 수를 저장해둔다면 이 수고를 덜을 수 있다. 구하려는 수가 작다면 메모이제이션을 하지 않아도 큰 문제가 생기지 않지만, 100번째 피보나치 수를 구해야 한다면 거듭제곱 꼴로 연산량이 늘어난다. 

어떻게 쓰는가?

메모이제이션은 쓰고자 하는 함수가 입력값에 따른 결과가 항상 같은 값이 나올 때만 이용 가치가 있다. 
어차피 똑같은 결과가 나올 함숫값을 구하기 위해 함수를 다시 호출하는 것은 비효율적이기 때문에 쓰는 것인데, 상황에 따라 다른 결과가 나오는 함수라면 메모이제이션을 쓰는 의미가 없다. 
따라서 함수가 입력에 따른 결과가 항상 같을 때 쓸 수 있다. 

그렇다면 어떻게 쓸 수 있을까?

함수의 매개변수, 또는 입력값을 기준으로 특정할 수 있는 배열을 만든다. 

#include <stdio.h>

int memo[1010][1010];

int f(a, b){
	//...
}

int main(){
	//...
}

예를 들어 DP를 위한 int형 함수 f(a, b)가 있다고 하자. 그리고 입력값은 1000 이하, 출력 값은 양의 정수이다. 
그렇다면 int형 배열 memo[1010][1010]를 만들어 메모이제이션을 할 수 있다. 
함수가 호출되면 memo[a][b]가 0인지, 0이 아닌지 확인한 후 0이라면 함수를 진행하고 memo[a][b]값 갱신 후 return, 0이 아니라면 이미 그 값이 함수의 return값이기 때문에 memo[a][b]의 값을 return하면 된다. 

다음 수도 코드(pseudo code, 의사 코드)를 보면 이해가 갈 것이다.

#include <stdio.h>

int memo[1010][1010];

int f(a, b){
	if(memo[a][b]==0){
    	memo[a][b] = something; //실제 코드에서 함수가 리턴하는 것 & memo[a][b]값 갱신
        return memo[a][b];
    }
    else return memo[a][b]; //memo[a][b]가 0이 아니라는 것은 함수의 리턴값이 저장되어 있다는 것이므로 그대로 리턴
}

int main(){
	//...
}

 

여기서 전제 조건은 함수의 리턴값이 양의 정수로 보장한다는 것이었다.
따라서 항상 0으로 초기화되는 전역 변수로 메모이제이션용 배열을 선언한 것이 문제가 되지 않았다.
그러나 만약 리턴값이 0까지 포함된다면 어떻게 해야 할까?

메모이제이션이 아직 안 된 입력값이라는 것을 알 수 있도록만 하면 된다. 예를 들어 함수를 호출하기 전에 main함수에서 

#include <stdio.h>

int memo[1010][1010];

int f(a, b){
	//...
}

int main(){
	memset(memo, -1, sizeof(memo));
	//...
}

-1로 초기화해준 뒤 f함수에서는 -1인지 아닌지로 판별하면 된다. 
만약 0 이상이 아니라 결괏값의 범위가 보장되지 않는다면 메모이제이션이 된 입력값 자체를 따로 다른 배열에 저장해두는 것도 하나의 방법이다. 

메모리제이션? 타뷸레이션?

흔히 메모이제이션이라는 용어를 처음 접하는 사람들은 메모리제이션의 오타로 보기도 한다.
하지만 오타가 아니라 철자 자체가 Memoization이다. 둘 다 기억한다는 것으로 뜻도 비슷하다. 
코딩과 컴퓨터 과학이 아직 생소한 분들에겐 memorization이 더 익숙한 단어겠지만, memoization이라는 컴퓨터 용어가 따로 있음을 메모해두면 좋을 것 같다. 

메모이제이션과 비슷한 것으로 타뷸레이션(Tabulation)이 있다. 타뷸레이션은 DP의 최하단 [추가] 부분에 소개되어 있는 DP의 Bottom-Up 방식의 메모이제이션이다. 
메모이제이션과 타뷸레이션의 차이점은 그저 방식의 차이에 불과하다. 굳이 따지자면, 메모이제이션은 값이 필요해질 때마다 값을 만들어서 가져오는 Lazy-Evaluation, 즉 DP의 Top-Down 방식에서 쓰는 방법이고, 타뷸레이션은 값을 다 만들어두는, 테이블을 채워두는 DP의 Bottom-Up방식에서 쓰는 방법이다.