[ 프로그래머스 피보나치 수(Lv2) ] (C++)

프로그래머스의 피보나치 수(Lv2) 문제이다.

[ 문제 풀이 ]

피보나치 수는 1, 1, 2, 3, 5, 8... 과 같이 진행되는 수열이다.

문제에서 나와있듯이 피보나치 수열의 규칙은 F[x] = F[x - 1] + F[x - 2] 가 된다.

이를 구현하기 위해서 생각해볼 수 있는 방법은 재귀를 이용한 구현이거나 메모이제이션을 이용한 방법이 존재한다.

첫 번째로 재귀를 이용하는 방법은 굉장히 시간이 오래걸리고 비효율적인 방법이 될 수 있다.

F[n] 값을 구하는 과정을 통해서 왜 비효율적인지 알아보자.

F[n]의 값을 구하기 위해서 재귀가 호출되는 과정을 정말 간단하게 그림으로 표현한 것이다.

보게 되면, 중복된 값에 대한 호출이 반복해서 일어나게 된다. 해당 위의 그림이 끝이 아닌 값이 1이 될 때 까지 계속해서 자식을

만들면서 호출될 것이다.

그런데 ! 위의 그림만 보더라도 F[n - 2], F[n - 3]이 2번씩 호출되고 있다. 아마 그 아래에 있는 더 작은 값들은 더 많이 호출될

것이다. 즉 ! 중복된 값이 반복적으로 호출되기 때문에 시간이 오래걸리고 비효율적일수 있다 라고 이야기한 것이다.

그래서 본인은 메모이제이션 방법을 이용해서 구현하였다.

반복문을 이용해서 작은 값부터 순차적으로 값을 구해서 가는 bottom-up 방식인 Dynamic Programming 방법으로 계산을

해주었다.

[ 소스코드 ]

#include<string>
#include<vector>
using namespace std;
 
int F[100010];
 
int solution(int n)
{
    F[0] = 0;
    F[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        F[i] = F[i - 1] + F[i - 2];
        F[i] = F[i] % 1234567;
    }
    return F[n];
}