1003. 피보나치 함수

1. 시간초과된 풀이

#include <iostream>
#include <vector>

#define endl "\n"

using namespace std;

int T, N;
vector<int> testCase;
int cnt_zero = 0, cnt_one = 0;

void Input()
{
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        cin >> N;
        testCase.push_back(N);
    }
}

int fibonacci(int n)
{
    if(n == 0)
    {
        cnt_zero += 1;
        return 0;
    }
    else if(n == 1)
    {
        cnt_one += 1;
        return 0;
    }
    else{
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

void Solution()
{
    for(int i = 0; i < T; i++)
    {
        int result = fibonacci(testCase[i]);
        cout << cnt_zero << " " << cnt_one << endl;
        
        cnt_zero = 0;
        cnt_one = 0;
    }
}

int main()
{
    Input();
    Solution();
    return 0;
}

 

2. 해결방법

• 피보나치 수열은 대표적인 "Dynamic Programming" 기법의 예시이다.
• 피보나치 수열은 (1) 재귀함수 (2) Dynamic Programming 으로 구현할 수 있다. (1) 재귀함수로 구현하면 숫자가 커질 수록 시간복잡도가 커진다. (f(n) = f(n-1) + f(n-2) 에서 같은 값을 계속 재귀함수로 계산하기 때문이다.) 따라서 (2) Dynamic Programming 을 사용하여 메모이제이션(Memoization) 즉, 캐싱(Caching) 기법을 사용하자
• 메모이제이션은 한 번 구한 결과를 메모리 공간에 메모해 두고 같은 식을 다시 호출하면 메모한 결과를 그대로 가져오는 기법을 의미한다. 캐싱이라고도 불린다.
• Dynamic Programming 은 다음 조건을 만족할 때 사용할 수 있다.(1) 큰 문제를 작은 문제로 나눌 수 있다. (2) 작은 문제에서 구한 정답은 그것을 포함하는 큰 문제에서도 동일하다.

3. Solution

// 동적 프로그래밍
#include <iostream>
#include <cstring>
#define endl "\n"
#define MAX 41
using namespace std;

int T, N;
int DP[MAX][2];

void Calculate()
{
    DP[0][1] = DP[1][0] = 0;
    DP[0][0] = DP[1][1] = 1;

    for(int i = 2; i <= N; i++)
    {
        DP[i][0] = DP[i-1][0] + DP[i-2][0];
        DP[i][1] = DP[i-1][1] + DP[i-2][1];
    }
}

void Solution()
{
    cin >> T;
    for(int i = 0; i < T; i++)
    {
        memset(DP, 0, sizeof(DP));

        cin >> N;
        Calculate();

        cout << DP[N][0] << " " << DP[N][1] << endl;
    }
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    Solution();

    return 0;
}