[프로그래밍] 메모이제이션 이해하기

재귀 호출은 문제를 풀기 위해 자기 자신을 호출하는 방식입니다. 가장 유명한 예제로 factorial을 들 수 있습니다. n!는 n*(n-1)!로 나타낼 수 있으며 이는 n!을 구하기 위해서 (n-1)!을 구하는 문제부터 해결 해야함을 의미합니다.

n!의 코드는 아래와 같습니다 (n이 음수인 경우 처리는 제외.)

int factorial(int n) {
	
    if (n == 1) return 1;
    else return n * factorial(n-1);
    
}

factorial(n)은 factorial(n-1)을 호출하는 것을 볼 수 있습니다. 코드를 보면 알 수 있듯이 재귀호출을 이용하여 문제를 푸는 것은 어려운 일이 아니지만, 시간이 오래 걸린다는 단점이 있습니다. 해당 부분은 아래 피보나치 수열 계산에서 명확하게 알 수 있습니다.

int fibonacci(int n) {
	
    if(n == 1 !! n == 2) return 1;
    else return fibonacci(n-1) + fibonacci(n-2);
    
}

피보나치 수열의 n번 쨰 값을 구한다고 하면, (n-1)번 째 값과 (n-2)번 째 값을 구해야합니다. 하지만 (n-1)번 째 값을 구하기 위해서 (n-2)번째값을 또 구해야합니다. 즉 하나의 값을 위하여 최소 두 번 이상 호출해야함을 의미합니다. 메모이제이션을 이용하면 이런 단점을 해결할 수 있습니다. 필요한 값을 첨으로 구한 이후, 값을 메모리에 저장하여 필요한 경우에 함수 호출이 아닌 메모리 접근으로 원하는 값을 가져올 수 있습니다. 아래가 위의 fibonacci 함수를 메모이제이션을 이용하여 구현한 코드입니다. 

int memo[N] = {0};

int fibonacci(int n) {
	
    if(memo[n] != 0} return memo[n];
    
    if (n == 1 || n == 2) return 1; 
    else memo[n] = fibonacci(n-1) + fibonacci(n-2);
    
    return memo[n];
    
}

코드에서 확인할 수 있듯이, memo라는 메모리 공간을 할당하고 값을 0으로 초기화해줍니다. 메모이제이션을 사용하지 않은 방식과 동일하게 fibonacci(n-1) 와 fibonacci(n-2)를 호출하지만 해당 값들이 이미 계산되었었다면 새로 계산하는 것이 아니라 저장된 값을 읽어오는 형식입니다. 

메모이제이션 방식을 이용하더라도 해당 코드는 재귀 용법에 속하니다. 다만 저장을 통하여 반복 작업을 방지함으로써 속도 측면의 성능 향상에 도움을 줍니다. 하지만, 값을 저장하는만큼 메모리 측면의 성능은 감소합니다.