[C][순환][반복] 피보나치 수열 계산

피보나치 수열(Fibonacci Sequence)을 계산하는 프로그램을 순환 알고리즘과 반복 알고리즘을 통해 만들어보겠다.

피보나치 수열의 정의는 다음과 같다.

${\displaystyle F_{n}:={\begin{cases}0&{\mbox{if }}n=0;\\1&{\mbox{if }}n=1;\\F_{n-1}+F_{n-2}&{\mbox{if }}n>1.\\\end{cases}}}$

위 정의를 보면 피보나치 수열 정의 자체가 피보나치 수열을 포함하는 순환적인 구조로 이루어져 있다는 것을 알 수 있다.
이에 순환 알고리즘을 사용하여 코드를 작성해보았다.

#include <stdio.h>
 
int fibonacci(int n) {
    if(n == 0) return 0;
    else if(n == 1) return 1;
    else return (fibonacci(n-1) + fibonacci(n-2));
}
 
int main(void) {
    int num = 7;
    int result;
 
    result = fibonacci(num);
    printf("%d번째 fibonacci 수열 값: %d", num, result);
    return 0;
}
 

위의 코드에서 fibonacci 함수는 보기에 이해하기 쉽고 간편해보인다.

하지만 실제로 이 함수는 매우 비효율적이다.

n의 값이 커질 수록 호출 되는 횟수가 매우 많이지기 때문이다.

여기서는 fibonacci(7)을 계산하였는데,

fibonacci(7)을 구하기 위해서는 fibonacci(6)와 fibonacci(5)의 값이 필요하고,

fibonacci(6)을 구하기 위해서는 fibonacci(5)와 fibonacci(4)가,

fibonacci(5)를 구하기 위해서는 fibonacci(4)와 fibonacci(3)이 필요하다.

즉 한 번 fibonacci 함수를 호출을 하면 두 번의 fibonacci 함수를 호출하게 된다.

따라서 피보나치 수열을 계산하는 순환 알고리즘의 시간 복잡도는 O(2^n)이다.

추가로 메모이제이션(Memoization)을 사용해 위 프로그램을 수정해보겠다.

메모이제이션이란 한 번 그 값을 계산하였다면 값을 저장해두어, 다시 계산해야 할 때 계산하는 대신 값을 바로 가져오는 방법이다.

이 방법을 동일한 피보니치 수를 다시 계산하는 것을 방지할 수 있다.

#include <stdio.h>
#define MAX_SIZE 100
 
int fibonacci(int n) {
    static int arr[MAX_SIZE];
    if(n < 2) return n;
    if(arr[n] > 0) return arr[n];
    else return arr[n] = fibonacci(n-1) + fibonacci(n-2);
}
 
int main(void) {
    int num = 10;
    int result;
 
    result = fibonacci(num);
    printf("%d번째 fibonacci 수열 값: %d", num, result);
    return 0;
}

다음으로는 반복 알고리즘을 사용하여 코드를 작성해보았다.

#include <stdio.h>
 
int fibonacci1(int n) {
    if(n < 2) return n;
    else {
        int i, tmp, cur = 1, last = 0;
        for (i = 2; i <= n; i++) {
            tmp = cur;
            cur += last;
            last = tmp;
        }
        return cur;
    }
}
 
int fibonacci2(int n) {
    if(n < 2) return n;
    else {
        int i, tmp, cur = 1, last = 0;
        for (i = 2; i <= n; i++) {
            tmp = last;
            last = cur;
            cur += tmp;
        }
        return cur;
    }
}
 
int main(void) {
    int num = 7;
    int result1, result2;
    
    result1 = fibonacci1(num);
    result2 = fibonacci2(num);
    printf("%d번째 fibonacci1 수열 값: %d\n", num, result1);
    printf("%d번째 fibonacci2 수열 값: %d", num, result2);
    return 0;
}
 

위의 코드에서 fibonacci1과 fibonacci2 모두, 반복 알고리즘을 사용해서 피보나치 수열을 계산하는 함수이다.

다만 구현 과정에서 어떠한 방법을 선택하여도 상관 없다는 것을 보여주기 위해 두 개다 만들어보았다.

for문을 사용하였기 때문에, 피보나치 수열을 계산하는 반복 알고리즘의 시간 복잡도는 O(n)이다.

이번 예제를 통해 문제의 정의가 순환적으로 되어있는 경우에도 순환 알고리즘보다 반복 알고리즘의 효율성이 뛰어날 수 있다는 것을 알아보았다.

• 거듭제곱의 값 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기
• 순환 알고리즘을 통해 하노이탑 문제 해결해보기
• 이항 계수의 계산을 통해 순환 알고리즘과 반복 알고리즘 비교해보기