[백준] 24416(피보나치 수 1) - C언어

안녕하세요 오늘은 백준 24416번 피보나치 수 1 문제에 대해 해설하겠습니다. 기말시험과 방학 여행때문에 이제서야 왔네요...

(귀찮았던건 안비밀...)

군대 가기 전까지 다시 열심히 달리겠습니다!

이 문제는 피보나치 수를 활용한 가장 기본적인 동적 프로그래밍 문제이다. 각 의사코드에 맞게 피보나치 수를 재귀호출,동적프로그래밍으로 작성후 각 코드의 실행 횟수를 출력해 빠르기를 비교하는 문제다.

 

우선 간단하게 피보나치의 수가 뭐냐면,

 

피보나치

 

피보나치 설명

1 1 2 3 5 8 13 21... 이런식으로 앞의 두 숫자의 합이 그 다음 숫자로 이어지는 수열을 피보나치 수 라고 한다.

 

 

이제 재귀호출로 푼 코드부터 살펴보자.

 

재귀호출

 

재귀호출은 의사코드와 똑같이 써도 된다. 이렇게 말이다.

아래는 의사코드이다.

fib(n) {
    if (n = 1 or n = 2)
    then return 1;  # 코드1
    else return (fib(n - 1) + fib(n - 2));
}

아래는 의사코드를 바탕으로 작성한 재귀호출 함수이다.

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

어떤가 둘이 거의 같은 코드라 봐도 무방할 정도로 생각한 대로 작성만 하면 될 정도로 쉬운 정답이지 않는가?

재귀호출이 어떻게 이루어지는지 간단하게 설명하자면 

재귀호출 설명

이런식으로 위의 코드에서 만약 n이 5라면, 5는 4와 3으로, 4와 3은 또 3,2와 2,1로..이렇게 계속해서 top-down 방식으로 나뉘어지는것이다. 

fib(fib(fib(...) + fib(...)) + fib(fib(...) + fib(...)))

프로그램 안에서 일어나는 작업으로 생각하면 대략 이렇게 함수안에서 계속해서 함수가 호출되는것으로 생각할 수 있다.

 

위의 그림에서 알수있듯 이런식으로 하면 계산했던 내용을 똑같이 또 계산하게 되어 계산량이 늘어나 비효율적이된다.

(물론 메모이제이션을 활용하면 이런 수고를 덜 수 있으나 이것은 다음에 기회가 될 때 따로 정리하겠다. )

 

따라서 우리가 할 수 있는방법은 반복문을 이용한 bottom-up 방식인 동적 프로그래밍이다.

 

 

동적 프로그래밍

 

우선 동적 프로그래밍의 의사코드부터 확인해 보자.

fibonacci(n) {
    f[1] <- f[2] <- 1;
    for i <- 3 to n
        f[i] <- f[i - 1] + f[i - 2];  # 코드2
    return f[n];
}

동적프로그래밍은 위의 재귀호출보다 효율적인 반면에 구현하기 약간 까다로운 방면이 있다. 

 

아래는 의사코드를 바탕으로 작성한 동적 프로그래밍 코드이다. 

int fibonacci(int n) {
    int f[n];
    int t = 0;  // 실행횟수를 세어줄 변수 생성
    f[0] = 1;
    f[1] = 1;  // 첫번째 자리와 두번째 자리에 1의 값을 저장
    if(n == 1 || n==2){
        return 1;
    }
    else{
        for(int i = 2; i < n; i++){
            f[i] = f[i-1] + f[i-2];  // 이전 값들을 활용해 다음 수열을 계산 후 저장
            t++;
        }
        return t;
    }
}

나는 이렇게 함수를 구현했다.

 

이 함수는 배열을 사용하여 피보나치 수열의 값을 계산했다. 피보나치의 수를 계산할 때에 초기 첫번째와 두번째의 값은 1이므로 배열의 첫번째와 두번째는 1로 저장해 놓았다. 

 

그 다음부터는 n이 1이나 2일때를 제외했을때 반복문을 사용하여 저장한 다음 인덱스부터 피보나치 수를 계산해 배열에 저장했다. 

이렇게 초기값 부터 계산하여 1 1 2 3... 올라가는것을 bottom-up 방식이라고 한다. 

 

이런식으로 피보나치 수의 값을 구하고 실행 횟수를 알 수 있었다. 

 

 

아래는 완성본 코드다!!

#include<stdio.h>

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

int fibonacci(int n) {
    int f[n];
    int t = 0;
    f[0] = 1;
    f[1] = 1;
    if(n == 1 || n==2){
        return 1;
    }
    else{
        for(int i = 2; i < n; i++){
            f[i] = f[i-1] + f[i-2];
            t++;
        }
        return t;
    }
}

int main(void){
    int n;
    scanf("%d", &n);
    printf("%d %d", fib(n), fibonacci(n));
    return 0;
}

 

입력 조건이 "첫째 줄에 n(5 ≤ n ≤ 40)이 주어진다." 이기때문에 동적 프로그래밍의 실행 횟수는 처음 2번의 횟수를 뺀 n-2로도 나타낼 수 있어서 

#include<stdio.h>

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

int main(void){
    int n;
    scanf("%d", &n);
    printf("%d %d", fib(n), n-2);
    return 0;
}

이런식으로 재귀 호출 함수만 제작하고 간결화 할 수도 있다. 

 

성공 !!

성공 !!

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

 

24416번: 알고리즘 수업 - 피보나치 수 1