[백준/C,C++] 1003번: 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

백준 단계별로 풀어보기 동적 계획법 1 첫 번째 문제입니다. 흔히 DP라고 부르는 동적 계획법(Dynamic Programming)은 문제를 작은 문제로 나누어 해답을 기억해뒀다가 중복되는 문제에 재활용하는 기법을 의미합니다. 피보나치 함수의 경우 fibonacci(3) = fibonacci(2) + fibonacci(1)인데 fibonacci(2)는 다시 fibonacci(1)을 호출합니다. 이렇게 중복된 부분이 생기고 입력값이 커질수록 중복되는 부분은 기하급수적으로 늘어납니다.

그림을 보시면 중복된 일을 처리하는 함수가 여러 번 실행되는 것을 보실 수 있습니다. f(2)가 2번 f(1)은 3번 f(0)는 2번 실행되죠. 배열을 만들어 매번 결괏값을 저장해두고, 해당 인덱스에 값이 있다면 이전에 해를 구한 적이 있다는 뜻이므로 함수를 호출하지 않고 값을 그대로 가져다 쓸 수 있습니다.

#include<iostream>

using namespace std;

int DP[100];

int fibonacci(int n)
{
    if (n == 0) return 0;
    if (n == 1) return 1;
    if (DP[n] != 0) return DP[n];
    return DP[n] = fibonacci(n - 1) + fibonacci(n - 2);
}

int main(void)
{
    int n; cin >> n;

    cout << fibonacci(n);

    return 0;
}

이렇게 간단하게 DP를 이용해 피보나치 수열의 값을 구하는 코드를 짤 수 있습니다. n이 0이거나 1인 경우 더 이상 분해되지 않는 가장 작은 문제이므로 값을 바로 리턴해주고, DP[n] 값이 있다면 함수를 호출하지 않고 배열의 값을 그대로 리턴해줍니다. 여기서 중복되는 문제들을 앞서 이용한 해를 이용하게 되죠. 이전에 구한 해가 존재하지 않는다면 n - 1과 n -2를 재귀 호출한 값을 DP[n]에 입력해 다음 중복되는 문제에서 이용할 수 있게 해줍니다. 수열의 값이 아니라 0과 1이 재귀로 인해 몇 번 호출되는지도 같은 로직을 이용해 코딩할 수 있습니다.

#include<iostream>

using namespace std;

#define MAX 41

pair<int, int> memory[MAX];

pair<int, int> plusPair(pair<int, int> a, pair<int, int> b)
{
    return pair(a.first + b.first, a.second + b.second);
}

pair<int, int> fibonacci(int n)
{
    if (n == 0) return pair(1, 0);
    if (n == 1) return pair(0, 1);
    else {
        if (memory[n].first != 0 && memory[n].second != 0) return memory[n];
        else {
            memory[n] = plusPair(fibonacci(n - 1), fibonacci(n - 2));
            return memory[n];
        }
    }
}

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

    int T; cin >> T;

    for (int i = 0; i < T; i++) {
        int temp; cin >> temp;
        pair<int, int> tempPair = fibonacci(temp);
        cout << tempPair.first << " " << tempPair.second << "\n";
    }

    return 0;
}