[C code] 피보나치 수열 (동적계획법 ; DP)

Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고,

하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.

 

---

 

피보나치 수열을 구현할 때,

 

#include <stdio.h>
#include <stdlib.h>

int fibonacci(int n, int* z, int* o)	//num & zero & one
{
    if (n == 0)
    {
        (*z)++;
        return 0;
    }
    else if (n == 1)
    {
        (*o)++;
        return 1;
    }
    else
    {
        return fibonacci(n-1, z, o) + fibonacci(n-2, z, o);
    }
}

int main()
{
    int cnt, zero, one;
    int num;

    scanf("%d", &cnt);

    for(int i=0 ; i<cnt ; i++)
    {
        zero = 0;
        one = 0;

        scanf("%d", &num);

        fibonacci(num, &zero, &one);
        printf("%d %d", zero, one);
    }

    return 0;
}

 

위와 같이 풀었더니, 시간초과로 실패

 

---

 

★☆★☆★ 문제에 쓰인 코드 그대로 구현하면 시간 초과가 나는 게 당연합니다. ★☆★☆★

문제에서 요구하는 건 그렇게 했을 때 나오는 값이 무엇인지 구하라는 것이지,

그 코드 그대로를 복붙해서 돌리라는 뜻이 아닙니다.

더 효율적으로 답을 구하는 방법을 찾아야 합니다.

 

---

 

그래서 찾게 된 동적계획법 (DP)

 

#include <stdio.h>
#include <stdlib.h>

int zero[41];   // 전역변수로 배열 선언하여 (메모이제이션)
int one[41];    // 모두 0으로 초기화

void fibonacci(int n)
{
    if(n == 0)
    {
        zero[n] = 1;
        one[n] = 0;
    }
    else if(n == 1)
    {
        zero[n] = 0;
        one[n] = 1;
    }
    else if(zero[n] == 0 && one[n] == 0)    //메모이제이션이 안 된 n
    {
        fibonacci(n-1);
        fibonacci(n-2);
        zero[n] = zero[n-1] + zero[n-2];	//zero 배열 메모이제이션
        one[n] = one[n-1] + one[n-2];		//one 배열 메모이제이션
    }
}

int main()
{
    int cnt;
    int num;

    scanf("%d", &cnt);

    for(int i=0 ; i<cnt ; i++)
    {
        scanf("%d", &num);

        fibonacci(num);
        printf("%d %d\n", zero[num], one[num]);
    }

    return 0;
}

 

Dynamic Programming은 전체 문제를 여러 개의 하위 문제로 나누어 풀고,

하위 문제들의 해결 방법들을 결합하여 최종 문제를 해결하는 문제 해결 방식이다.

 

진행된 계산들을 "메모이제이션(Memoization)"에 저장함으로써 나중에 동일한 계산을 피한다

->

 

if (DP[n] == 0)
{
 ...
 DP[n] = DP[n-1] + DP[n-2];
 ...
}

 

재귀 함수를 이용하여 풀게 되면, 했던 계산들을 재귀하며 다시 하는 이유때문에

시간이 지수적으로 증가하게 된다

​

큰 문제를 작은 문제로 나눌 수 있고,

작은 문제에서 구한 정답이 그것을 포함하는 큰 문제에서도 동일하다면,

DP 방법을 이용할 수 있다