재귀와 메모이제이션

1351번: 무한 수열
https://www.acmicpc.net/problem/1351

재귀 깊이가 늘어날수록 프로그램은 중복된 계산을 많이 하게 되고, 시간이 오래 걸릴 수 밖에 없다.

#include <iostream>
using namespace std;

long long infinite(long long N, long long P, long long Q) {
    if(N==0) return 1;
    return infinite(N/P, P, Q) + infinite(N/Q, P, Q);
}

int main() {
    long long N, P, Q;
    cin >> N >> P >> Q;
    cout << infinite(N,P,Q);
}

어떠한 무한 수열을 구하는 코드이다.

주어진 코드에서는 메모이제이션을 사용하지 않고 재귀 함수만을 이용하여 값을 계산하고 있기 때문에, 입력 값이 큰 경우에는 중복 계산이 많아져서 시간 초과가 발생할 수 있다.

#include <iostream>
#include <map>
using namespace std;

map<long long, long long> m;

long long infinite(long long N, long long P, long long Q) {

	// 이미 결과가 저장되어 있다면 이전에 계산한 값을 반환
    if(m[N] != 0) return m[N];
    
    // 이전에 저장한 결과가 없다면 해당 N에 대한 값을 계산 후, map에 저장
    return m[N] = infinite(N/P, P, Q) + infinite(N/Q, P, Q);
}

int main() {  
    long long N, P, Q;
    cin >> N >> P >> Q;
    m[0] = 1;
    cout << infinite(N,P,Q);
}

위와 같이 map을 사용하여 메모이제이션을 구현하였다.

이렇게 하면 이미 계산한 값들을 map에 저장해두고, 이후에 동일한 값이 필요할 때에는 저장된 값을 사용하게 된다.

중복 계산을 피함으로써 성능을 크게 향상시킬 수 있다.