[Silver III] 피보나치 함수 - 1003

문제 링크

성능 요약

메모리: 2024 KB, 시간: 4 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 6월 14일 23:59:44

문제 설명

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
fibonacci(0)은 0을 출력하고, 0을 리턴한다.
fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다.

각 테스트 케이스는 한 줄로 이루어져 있고, N이 주어진다. N은 40보다 작거나 같은 자연수 또는 0이다.

출력

각 테스트 케이스마다 0이 출력되는 횟수와 1이 출력되는 횟수를 공백으로 구분해서 출력한다.

첫번째로 실패한 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>

using namespace std;

int N;
int countOne = 0;
int countZero = 0;
vector<int> arrN;

int fibonacci(int n) {
    if (n == 0) {
        // printf("0");
        countZero++;
        return 0;
    } else if (n == 1) {
        // printf("1");
        countOne++;
        return 1;
    } else {
        return fibonacci(n-1) + fibonacci(n-2);
    }
}

int main() {
	//freopen("input.txt", "r", stdin);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        /* code */
        int n;
        cin >> n;
        arrN.push_back(n);
    }

    for (int i = 0; i < N; i++)
    {
        // cout << arrN[i] <<endl;
        fibonacci(arrN[i]);
        cout << countZero << " " << countOne << endl; 
        countZero = countOne = 0; //초기화
    }    
    
    return 0;
}

처음에 구현한 코드이다. 전역 변수로 카운트를 만들고 마지막 분기점에서 각각 0,1을 카운트해주어 옳은 결과값을 받아올 수 있었지만, 시간 초과로 계속 실패하였다.

alt text

피보나치 수열의 시간 복잡도

무엇이 문제일까.. 피보나치 수열의 시간복잡도를 계산해보면 이유를 알 수 있다.

   			 F(4)
            /     \
         F(3)     F(2)
        /   \     /   \
     F(2)  F(1)  F(1)  F(0)
    /   \
  F(1)  F(0)

n=4라고 했을때, 트리의 왼쪽만 따라가봐도 알 수 있는데, 전체 층의 개수는 n개를 넘을수 없다. 그리고 한 층씩 내려갈때마다 두배로 늘어나니 O(2^n)의 복잡도를 가지게 될 것이다.

또한 메인 함수에서 입력받은 배열리스트의 그 수만큼 함수를 n번 호출하기 때문에 전체적인 프로그램의 속도는 더욱 느려질 것이다.

해결 - 다이나믹 프로그래밍 사용

또 일반적인 피보나치 수열을 DP로 해결할때는 값을 찾기만 하면 되지만, 해당 문제는 특이하게 0이 리턴되었을때의 카운트를 원하는게 포인트였다. 따라서 튜플을 사용해 메모리 제이션 기법을 사용할때 해당 튜플에 저장하고, 피보나치 함수의 리턴값도 튜플로 지정해주었다.

그리고 튜플을 add 하기위한 addValues 함수를 구현하여 해결하였다.

메모리 제이션 기법

다이나믹 프로그래밍 중 메모리 제이션 기법이란, 피보나치 수열의 예제 처럼 F(4)를 구할때 F(2)처럼 이미 계산되었지만, 다른 분기점에서 또 계산된다는 게 추가적인 연산을 소모함에 따라 이를 생략하고자 한번 계산된 F(2)의 값을 따로 저장해놓고, 다시 F(2)가 호출될 때 저장된 값을 사용하여 불필요한 추가 연산을 막는 것에 의의가 있어 높은 시간 복잡도를 해소할 매우 효과적인 방법이다.

해결 코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <unordered_map>
#include <tuple>
using namespace std;

int N;
vector<int> arrN;
unordered_map<int, tuple<int, int>> dp;

tuple<int, int> addValues(const tuple<int, int>& t1, const tuple<int, int>& t2) {
    return make_tuple(get<0>(t1) + get<0>(t2), get<1>(t1) + get<1>(t2));
}

tuple<int, int> fibonacci(int n) {
    if (n == 0) {
        return make_tuple(1, 0);
    }
    else if (n == 1) {
        return make_tuple(0, 1);
    }
    else if (dp.find(n) != dp.end()) {
        return dp[n];
    }
    else {
        dp[n] = addValues(fibonacci(n - 1), fibonacci(n - 2));
    }
    return dp[n];
}

int main() {
    freopen("input.txt", "r", stdin);

    cin >> N;
    for (int i = 0; i < N; i++)
    {
        /* code */
        int n;
        cin >> n;
        arrN.push_back(n);
    }

    for (int i = 0; i < N; i++)
    {
        // cout << arrN[i] <<endl;
        tuple<int, int> answer = fibonacci(arrN[i]);
        cout << get<0>(answer) << " " << get<1>(answer) << endl;
    }

    return 0;
}