[알고리즘문제] 프로그래머스 - 피보나치 수

 

그냥 일반적인 재귀방법을 사용하면 시간초과가 뜬다.

 

fibo(5)값을 구하기 위해서는 fibo(4) + fibo(3). fibo(4)는 fibo(3) + fibo(2).fibo(3)은 fibo(2) + fibo(1). 여기서 fibo(3)은 fibo(5)와 fibo(4)를 구할 때 3번 사용하게 된다. 다시 계산을 해야 한다는 말이다. 

 

근데 fibo(3)을 매번 계산해야 할까? 처음 1번은 계산을 해야 하지만, 그 뒤 부터는 fibo(3)계산 결과값을 기억하고 있으면 안될까 ? 그러면 바로 fibo(3)값을 재귀호출 없이 바로 구할 수 있을 것이다 -> 메모제이션

#include <string>
#include <vector>
#include <iostream>

using namespace std;
int store[100001] = {0};
int result;

int fibo(int n){
    if(store[n] > 0){
        return store[n];
    }
    if(n==1){
        result = 1;
    }else if(n==0){
        result=0;
    }else{
        result = fibo(n-1)+fibo(n-2);
        store[n] = result % 1234567;
    }
    return result % 1234567;

}
int solution(int n) {

    return fibo(n);
}

먼저 fibo(n)함수가 호출되면 n값을 이미 구했는지 검사하고 값이 있다면 그 값을 바로 return하고 아닌 경우 다시 재귀를 돈다.

그리고 재귀의 결과값을 배열에 저장해둔다.

 

dp에서 사용하는 방법인데, 이렇게 피보나치 수를 구하는데 사용할 수도 있다.