[재귀]05. 메모이제이션(memoization)

이번 포스트에서는 재귀의 동작 과정에서 발생할 수 있는 엄청난 중복 호출과 이를 극복하기 위한 메모이제이션에 대해서 살펴보자.

 

피보나치!

 

피보나치 수열 구하기

 

피보나치 수는 첫째항과 둘째 항이 1이고 그 뒤의 항은 바로 앞 두 항의 합인 수열이다. 1, 1, 2, 3, 5, 8, ... 이렇게 전개된다. 알고리즘 계에서는 달나라 토끼에서부터 건물 페인트 칠하기, 계단 오르기 등 정말 다양한 가면을 쓰면서 등장하는 녀석이다.(신기하게도 가면을 바꿔 쓸 때마다 못알아본다. 니가 피보나치였다니...)

 

재귀를 통한 피보나치 수열 구하기

피보나치 수의 정의에 의해 f(1) = f(2) = 1이다. 이 두개의 값은 기저조건이 된다.

피보나치 수의 점화식은 f(n) = f(n-1) + f(n-2)이다.

따라서 결정요인을 n으로 했을 때 피보나치 수는 다음과 같이 재귀를 통해서 구할 수 있다.

static int fiboCnt;

static long fibo(int n) { // n >=1
    fiboCnt++;
    if (n <= 2) {
        return 1;
    }
    return fibo(n - 1) + fibo(n - 2);
}

 

 

상태공간 트리와 문제

위 재귀 함수의 상태공간 트리를 그려보면 다음과 같을 것이다.

 

잘 동작하는 이 구현에서는 무엇이 문제일까?

 

바로 엄청난 중복 호출이다. fibonacci를 구하는 함수는 철저히 n에만 영향을 받는다. 따라서 fibo(4)는 언제나 3일 수밖에 없다. 하지만 함수 호출의 관계에서 필요할 때마다 fibo(4)가 매번 계산되고 있고 한번 계산될 때마다 그 하위 호출들 역시 무수히 반복된다. 지금은 n이 겨우 6인 상태이지만 n이 커지면 커질수록 이런 중복은 어마어마하게 나타날 것이다. 이 중복을 없앨 수 있다면?

 

 

 

memoization

 

memoization의 필요성

재귀 함수를 아무생각 없이 사용하면 어마어마한 중복이 발생하는데 이 값은 결정 요인에 의해서만 좌우되며 언제나 같은 값을 갖는다. 이런 경우 실행 결과를 배열 같은 메모리에 저장해두고 같은 계산 결과가 필요할 때 또다시 계산하지 않고 메모리에 저장된 값을 재사용하는 기법을 memoization이라고 한다. 약간의 메모리를 투자해서 함수 호출을 획기적으로 줄임으로써 속도를 향상시키는 것이다.

static int fiboMemoCnt;

static long fiboMemo(int n, long[] memo) {
    fiboMemoCnt++;
    if (n <= 1) {
        return n;
    } else if (memo[n] > 0) {
        return memo[n];
    }
    return memo[n] = fiboMemo(n - 1, memo) + fiboMemo(n - 2, memo);
}

 

아주 간단한 변화이지만 n=30일 경우 일반 버전은 무려 1,664,079번의 메서드 호출이 발생하는 반면 메모 버전은 경우 59번의 호출만으로 계산이 종료된다!!

832040, 호출 회수: 1664079
832040, 호출 회수: 59

 

 

memoization은 만병 통치약?

내친김에 factorial을 구할 때 memoization을 수행하면 얼마나 함수 호출 회수가 줄어드는지 살펴보자.

static int factCnt;
static long fact(int n) {
    factCnt++;
    if (n == 1) {
        return 1;
    }
    return fact(n - 1) * n;
}

static int factMemoCnt;
static long factMemo(int n, long[] memo) {
    factMemoCnt++;
    if (n == 1) {
        return 1;
    } else if (memo[n] > 0) {
        return memo[n];
    }
    return memo[n] = factMemo(n - 1, memo) * n;
}

 

하지만 신기하게도 이번에는 호출 회수에 변화가 없다. 왜일까?

3628800, 일반 호출 회수: 10
3628800, 메모 호출 회수: 10

 

 

이유는 factorial을 호출할 때는 함수호츨 트리에 중복되는 내용이 없기 때문이다. 괜히 쓸데없이 메모리만 낭비한 경우이다. 즉 재귀를 사용한다고해서 언제나 memoization을 통해서 코드를 효율화 시킬 수 있는 것은 아니다. 중복호출이 발생할 때에만 효과가 있다는 점을 명심하자.