https://www.acmicpc.net/problem/1003

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);
    }
}

위 문제에서 주어지는 재귀를 이용한 피보나치 알고리즘이다.
막연히 생각한다면 0과 1의 카운트를 저장하는 변수를 만들고 재귀함수에 넣을것이다.

하지만,

위 코드는 시간복잡도가 2^n 이 걸려버리는 아주 나쁜성능의 프로그램이라고 할 수 있다.
그래서 제출을 하게되면 2의 40승이 되어버려서 시간초과가 발생한다.

그래서

Dynamic Programing

을 사용할거다.

다이나믹 프로그래밍 즉 동적프로그래밍은
작은 문제들이 반복적으로 일어나는경우 이 작은 문제들이한번씩 만 작동이 되도록 하기위한 방법이다.

DP의 조건

-작은문제가 반복해서 일어나는경우.
-같은문제를 구할때마다 정답이 동일한경우.
위 두 조건이 만족할때 DP를 사용할 수 있다.

해결방법

간단하게 작은 문제의 값을 저장할 수 있는 공간을 만들어서 저장한 다음, 큰 문제의 해결에 작은문제의 값이 필요하다면, 불러오면 된다.

#include <stdio.h>

typedef struct cn
{
    int cnt_0;
    int cnt_1;
} cnt;

cnt fibo(int n)
{
    cnt fibo_cnt[40];

    for (int i = 0; i <= n; i++)
    {
        if (i == 0)
        {
            fibo_cnt[i].cnt_0 = 1;
            fibo_cnt[i].cnt_1 = 0;
        }
        else if (i == 1)
        {
            fibo_cnt[i].cnt_0 = 0;
            fibo_cnt[i].cnt_1 = 1;
        }
        else
        {
            fibo_cnt[i].cnt_0 = fibo_cnt[i - 1].cnt_0 + fibo_cnt[i - 2].cnt_0;
            fibo_cnt[i].cnt_1 = fibo_cnt[i - 1].cnt_1 + fibo_cnt[i - 2].cnt_1;
        }
    }
    return fibo_cnt[n];
}

int main()
{
    int TestCase, n;
    scanf("%d", &TestCase);
    cnt result;
    for (int i = 0; i < TestCase; i++)
    {
        scanf("%d", &n);
        result = fibo(n);
        printf("%d %d\n", result.cnt_0, result.cnt_1);
    }
    return 0;
}

코드를 분석해보면 알겠지만 DP를 사용해서 코딩을 했을때
시간복잡도는 n이 된다는 것을 알 수있다.

참고 :https://galid1.tistory.com/507