[백준/C언어] 1003번 - 피보나치 함수

백준 웹사이트 "1003번 - 피보나치 함수" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

1003번: 피보나치 함수

---

소스 코드

#include <stdio.h>

void fibonacci(int N);

int main(void){
    int T;
    scanf("%d", &T);

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

        fibonacci(N);
    }
}

void fibonacci(int N){
    if(N==0)
        printf("%d %d\n", 1, 0);
    else{   //N>0
        int fibo[N+1][2];
        fibo[0][0] = 1;
        fibo[0][1] = 0;
        fibo[1][0] = 0;
        fibo[1][1] = 1;
     
        for(int i=2; i<N+1; i++){
            fibo[i][0] = fibo[i-1][0] + fibo[i-2][0];
            fibo[i][1] = fibo[i-1][1] + fibo[i-2][1];
        }
        printf("%d %d\n", fibo[N][0], fibo[N][1]);
    }
}

---

문제 풀이

  재귀함수는 공간(메모리)을 비교적 적게 쓰는 대신, 같은 계산을 반복해야 하는 관계로 시간이 오래 걸립니다. 같은 계산을 여러 번씩 반복하지 않도록 한 번 한 계산을 저장해두는 것을 '다이나믹 프로그래밍' 또는 '동적 계획법'이라고 합니다. 대표적인 재귀 문제인 피보나치 함수 문제를, 이번에는 동적 계획법으로 풀어봅니다.

  함수 'fibonacci'는 N번째 피보나치 숫자를 계산하기 위해 재귀 함수를 쓸 때 0이 출력되는 횟수와 1이 출력되는 횟수를 계산합니다. 이때 이차원 배열 'fibo'를 선언하는데, fibo[n][0]은 n번째 숫자에서 0이 출력되는 횟수, fibo[n][1]은 n번째 숫자에서 1이 출력되는 횟수입니다. 각 횟수 역시 피보나치 규칙을 따르기 때문에, 아래와 같은 점화식이 성립합니다.

$$ fibo[i][0] = fibo[i-1][0] + fibo[i-2][0] $$

$$ fibo[i][1] = fibo[i-1][0] + fibo[i-2][1] $$

이전에 계산한 값들은 모두 배열 'fibo'에 저장되므로 정확히 한 번의 for문만으로 N번째 경우까지 계산이 가능합니다. 22를 입력했을 때의 출력값이 10946 17711인데, 만약 재귀함수 fibonacci로 22번째 피보나치 수를 구하고자 했다면 fibonacci(0)을 10946번, fibonacci(1)을 17711번 실행했을 것이란 의미가 됩니다. 재귀함수에 비해 동적 계획법이 얼마나 빠른지 체감이 되시죠?