📒 활용 개념

1.Dynamic Programming(DP)을 활용한 풀이
2. 재귀함수를 활용한 풀이

Dynamci Programming과 Memoization의 개념 설명
Dynamic Programming & Memoization

📌 문제 설명

피보나치 수를 이용해 n(n>2)에 대하여 1234567로 나눈 나머지를 리턴하는 함수를 만든다.
여기서 주의할 점은 f(n)만을 1234567로 나눈 나머지가 아니라 모든 f(i)를 1234567로 나눈 값이 피보나치의 값이 되는 것이다.

📌 구현

1. Dynamic Programming(DP)을 활용한 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    vector<int> fb;						//크기가 작기 때문에 vector가 아닌 배열을 사용할 수 있다.
    
    fb.push_back(0);
    fb.push_back(1);
    
    for(int i=2; i<=n; i++){
        fb.push_back((fb[i-1]+fb[i-2] )% 1234567);	//각각의 결과를 1234567로 나눠 나머지를 구한다.
    }
    answer=fb[n];
    
    return answer;
}

2.재귀함수를 활용한 풀이

#include <string>
#include <vector>

using namespace std;

int solution(int n) {
    int answer = 0;
    if(n==0){
    	answer=0;
    }
    else if(n==1){
    	answer=1;
    }
    else{
    	answer=(solution(n-2) + solution(n-1)) % 1234567;
	}
    
    return answer;
}

📌주의점

• 두 번째 방법인 재귀함수를 사용하면 이 문제를 풀 수 없을 것이다. 그 이유는 프로그램이 실행되는 시간이다
  -재귀함수는 중복이 일어날 수 있다.
  ex) f(5) = f(4) + f(3)
  f(4) = f(3) + f(2)
  이러한 중복이 반복되어 누적되면 결국 프로그램의 실행 시간이 길어지게 되고 좋지 못한 프로그램이 된다.
• 문제의 이해를 잘 해야한다. 처음에는 결과값만 1234567로 나눈 나머지라고 생각하여 문제를 풀지 못했다.