[백준 2748번/C언어] 피보나치 수, 두 가지 접근법으로 풀기

백준 2748번 문제를 Dynamic Programming (DP, 동적 계획법)의 두 가지 접근 방법인 Top Down 방식과 Bottom Up 방식으로풀어보았습니다. 백준에 제출 시에는 실행 횟수를 절감할 수 있는 Bottom Up 방식만 제출했으니 참고해주시기 바랍니다. 

 

백준 2748번: https://www.acmicpc.net/problem/2748

2748번: 피보나치 수 2

 

 

문제 내용은 아래와 같습니다. 

 

우선 피보나치 수열은 첫번째, 두번째 수가 1이고, 그 이후로는 앞 두 개의 숫자를 더한 수가 되는 수열을 말합니다. 자세한 내용은 아래 링크를 참고해주세요.

https://ko.wikipedia.org/wiki/%ED%94%BC%EB%B3%B4%EB%82%98%EC%B9%98_%EC%88%98

피보나치 수 - 위키백과, 우리 모두의 백과사전

 

이 피보나치 수열이 DP의 가장 기본적이고 또 기초적인 예제라고 할 수 있다고 합니다. 사실 저도 다른 동적계획법 문제를 풀다가 막혀, 기초부터 동적계획법을 익히자는 생각으로 해당 문제를 먼저 풀어보게 되었습니다. 동적계획법은 아래 블로그에서 잘 소개하고 있어 참고하시면 좋을 것 같습니다. 

https://didu-story.tistory.com/220

[알고리즘] Dynamic Programming (동적 계획법, DP) (feat. Swift 스위프트)

 

 

피보나치 수열에서 동적 계획법이 필요한 이유는, 동적 계획법을 적용하지 않으면 재귀함수로 인해 반복 횟수가 급격하게 증가할 수 있기 때문입니다. 비교를 위해 먼저 동적 계획법을 사용하지 않은 코드를 준비했습니다. 

언뜻 보기에는 코드가 매우 간단하고 깔끔해보이지만, 함수 내에 f(n-1)과 f(n-2), 즉 두 개의 재귀 함수를 가지고 있어 숫자가 커질 수록 반복횟수가 기하급수적으로 증가하게 됩니다. 또한, f(n-1)와 f(n-2)가 같은 작업을 수행하며 f(n-2)가 하나 덜 수행하는 것 뿐이지만, 결국 각각을 위해 같은 과정을 두 번 수행해야 한다는 것도 문제입니다. 이러한 문제를 해결하여 프로그램을 더 빠르게 만들기 위해 동적계획법을 사용하게 됩니다. 

#include <stdio.h>

int f(int n) {
    if ((n == 1) || (n == 2)) return 1;
    else return f(n-1) + f (n-2);
}

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

    printf("%d", f(n));
}

 

 

그럼 두 가지 접근법으로 구성해본 코드를 살펴보겠습니다. 첫번째는 Bottom Up 방식입니다. Bottom Up 방식은 문제를 작게 쪼개어서 작은 문제의 답으로 더 큰 문제를 풀어나가는 방식입니다. 피보나치 수열에서는 첫번째부터 차근히 풀어 마지막 n번째 수를 얻어내는 것이 목표입니다. fibonacci 수열을 담을 fibonacci 배열을 만들고, 여기에 0부터 n까지의 피보나치 수열을 채워나갑니다. 백준에서 문제를 풀 때 주의해야 할 점은, 변수나 수열을 저장할 때 long long 타입으로 지정해야 한다는 점입니다. 문제에 제시된 가장 큰 n값인 90번째 수가 2,880,067,194,370,816,120이기 때문입니다. 

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

int main() {
    int n;
    scanf("%d", &n);
    
    long long int *fibonacci = (long long int *)malloc(sizeof(long long int) * (n+1));
    fibonacci[0] = 0;
    fibonacci[1] = 1;
    for (int i = 2; i <= n; i++) {
        fibonacci[i] = fibonacci[i-1] + fibonacci[i-2];
    }
    
    printf("%lld", fibonacci[n]);
    free(fibonacci);
}

 

이렇게 Bottom Up 방식으로 문제를 풀어 백준에 제출하면, 아래와 같이 정답처리가 됩니다. 

 

 

 

정답은 이미 맞추었지만, 처음부터 동적계획법을 이해하고자 시작한 문제였기 때문에, Top Down 방식으로도 풀어보았습니다. 제출할 것이 아니기 때문에 long long 타입이 아닌 int 타입으로 통일한 점 유의해서 봐주시기 바랍니다. 

여기서는 fibo 함수를 만들어 재귀를 이용했습니다. 가장 큰 단위인 n부터 시작하여 가장 작은 단위인 0이나 1에 닿으면 전역변수인 res 배열을 채워 기록하는 방식으로 동적 계획법을 이용합니다.

저는 여기서 의문을 품은 것이, 그렇다면 어차피 재귀함수를 이용하는데, 동적 계획법을 사용하여 코드를 더 복잡하게 만드는 이유가 뭐지? 라고 생각했습니다. 하지만 코드를 찬찬히 뜯어보자, fibo(n-1)과 fibo(n-2)에서 중복으로 계산해야 하는 값이 이미 res 배열에 저장되어 있어, 다시 계산하지 않아도 된다는 이점이 있다는 것을 깨달았습니다. 

#include <stdio.h>

int res[90];

int fibo(int n) {
    if (n <= 1) return n;
    else {
        if (res[n] > 0) return res[n];
        else {
            res[n] = fibo(n-1) + fibo(n-2);
            return res[n];
        }
    }
}

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

    printf("%d", fibo(n));
}