백준 1003 피보나치 함수

www.acmicpc.net/problem/1003

1003번: 피보나치 함수

이 문제는 피보나치 수열을 응용하여 만든 재미있는 문제이다. 피보나치 수열은 기본적으로 f(n)=f(n-1)+f(n-2)의 형태를 갖는다. 따라서 재귀함수의 형태로 공식을 구현할 수 있지만, 중간 과정에서 찾은 값들을 기록하지 않는다면 너무 많은 연산이 필요하게 된다.

이 문제에서는 f(0)에 다다랐을 경우, '0'을 출력하고 f(1)에 닿으면 '1'을 출력하도록 되어있다. 단순하게 생각하면 재귀로 계속 파고 들어 f(0)이나 f(1)에 닿아야 할 것 같지만, 그렇게 하면 당연히 너무 많은 시간이 필요하게 된다. 따라서, 과거의 히스토리를 기록해두어 중복된 계산을 피해야 한다. 

 

---

컴퓨터 공학 쪽에서는 '어떤 값을 기록하는 행위' 등에 대해 [메모이제이션]이라고 부른다. 정확한 정의는 직접 검색을 통해서 쉽게 파악할 수 있다. 이는 동적 계획법, 다이나믹 프로그래밍(DP)의 핵심이 되는 기술이다. 단순한 예시에 대해서는 아주 직관적으로 이해할 수 있다. 당연히 이전 기록을 남기면, 다음에 편하니까... 하지만 어려운 형태의 문제로 갈수록 무엇을 기록으로 남길지도 파악하기 힘들고, 어떤 기록들이 또는 어떤 정점들이 어떤 관계를 맺고 있는지도 파악하기 어려워서 점화식을 만들기가 어렵다. 다이나믹 프로그래밍도 추후 본 블로그 [알고리즘 자료구조] 카테고리에서 다루도록 하겠다. 

---

본 문제로 다시 돌아와서, 매번 f(0)에 닿은 횟수와 f(1)에 닿은 횟수를 기록하고 그걸 누적한다면 문제를 쉽고 빠르게 해결할 수 있다.

아래의 그림을 보자.

위와 같이, 바로 위의 두 함수에서 나온 값들을 그대로 누적하여 답을 구할 수 있게 되고, 결과값을 배열 등에 계속 담아주면 된다.

 

<주요 내용>

다이나믹 프로그래밍, 재귀함수, 피보나치

 

<코드>

아래 코드에서 zo[n]=ans를 하는 부분이 바로 '메모이제이션', 기록을 하는 부분이다. ans를 그대로 리턴해도 되지만 zo배열에 담아둠으로써, 이하의 연산은 더이상 하지 않게 된다. 재귀함수 fibo는 항상 if ... 를 통해 기록을 먼저 확인하기 때문이다.

#include <iostream>
#define endl '\n'
using namespace std;
const int sz=40+1;
int t,n;
pair<int,int> zo[sz];

pair<int,int> fibo(int n){
    if(zo[n]!=make_pair(0,0))return zo[n];
    auto a=fibo(n-1);
    auto b=fibo(n-2);
    auto ans=make_pair(a.first+b.first,a.second+b.second);
    zo[n]=ans;
    return ans;
}

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

    zo[0]=make_pair(1,0);
    zo[1]=make_pair(0,1);
    cin>>t;
    while(t--){
        cin>>n;
        auto ans=fibo(n);
        cout<<ans.first<<' '<<ans.second<<endl;
    }
    return 0;
}

 

loop=int(input())
result=[]
for i in range(loop):
    n=int(input())
    zero=[1,0]
    one=[0,1]
    if n>=2:
        for i in range(2,n+1):
            zero.append(zero[i-1]+zero[i-2])
            one.append(one[i-1]+one[i-2])
    result.append([zero[n],one[n]])
    
for i in result:
    print(i[0],i[1])