[C] 백준 1003 (피보나치 함수)

*문제에 대한 내 생각

재귀에 대한 좋은 문제라고 생각한다. 

그러나 종종 런타임오류가 나와 사람들을 당황하게 만드는 것 같다.

 

 

*문제 풀이

-아이디어

내 경우 두 코드를 작성했다. 하나는 재귀, 하나는 배열을 이용한 방법이다.

사실상 서로 코드의 진행방향이 반대라고 생각하면 된다.

즉, 뿌리에서 각 가지로 나아갈지, 가지들을 모아 뿌리로 갈지의 차이다.

 

-코드1(재귀)

문제를 읽어보면, 결국 출력해야 하는 숫자는 0과 1의 개수다.

나무로 따지자면, 제일 끝에 있는 잎새에 해당하는 것.

이 경우 문제에 나와있는 fibonacci함수를 변형시켰다.(코드에서는 fibo라는 함수)

구체적으로 말하자면 원래 0또는 1을 출력하는 부분을, 배열을 이용해 개수를 더하는 것으로 수정했다.

 

#include <stdio.h>
 
 
void fibo(int num, int z_o[]) {
    if (num == 0) { //fibonacci(0)에 해당
        (*z_o)++; //포인터를 쓰는게 좀 더 재귀에 편하다는 판단이었다
        return;
    }
    else if (num == 1) { //fibonacci(1)에 해당
        (*(z_o + 1))++;
        return;
    }
    else { //인수가 1과 0이 될때까지 재귀를 사용
       fibo(num-1, z_o);
       fibo(num-2, z_o);
    }
}
 
 
int main(void) {
    int t;
    int num;
    scanf("%d", &t);
 
    for(int i=0;i<t;i++) {
        scanf("%d", &num);
 
        if (num == 0)
            printf("%d %d \n", 1, 0);
        else if(num == 1)
            printf("%d %d \n", 0, 1);
        else { //num이 2이상인경우(0과 1은 재귀가 필요없다)
            int z_o[2] = {0, 0}; //왼쪽이 0의 개수, 오른쪽이 1의 개수
           fibo(num, z_o);
            printf("%d %d \n", z_o[0], z_o[1]);
        }
    }
    return 0;
} 

 

*결과

런타임에러;;

재귀가 너무 많이 사용되어서 오류가 나온 듯 하다. 사실 다른 사람들의 코드를 보면

왜 그건 런타임에러가 안나올까하는 의문.

결국 이 에러를 해결하지 못해서 다른 코드를 작성했다.

 

 

-코드2(배열)

언뜻보면 무식한 방법같지만, 가장 간단한 방법이 아닌가 싶다.

요는 간단하다. 문제속 fibonacci(n)을 호출했을때, 각 n을 인덱스값으로 삼아 0과1이 몇 번 출력되는지 배열에 저장했다.

즉 맨 처음에 n이 10이라면, 0부터 10까지 각각 호출했을때 0과1이 출력되는 수가 배열에 저장된다.

이후 새로 받는 숫자가 10보다 작으면, 기존 배열에서 찾아 바로 출력할 수 있다.

만일 10보다 크면, 10부터 새로 받은 숫자까지 추가로 원소를 추가하면 된다.

 

q(n)을 fibonacci(n)을 호출했을 때 0과 1이 각각 출력되는 개수로 정의한다면, q(n)=q(n-1)+q(n-2)이다.

우리는 n이 0과 1일때의 q(n)의 값을 알기 때문에 앞으로의 개수를 구하는 건 매우 쉽다.

세세한 부분은 코드를 보면서 이해해 보길 바란다.

#include <stdio.h>
 
 
int main(void) {
    int t;
    int num;
    scanf("%d", &t);
    int dic[1000][2] = {{1,0},{0,1}}; //이차원 배열 설정. 먼저 인덱스 0과 1을 초기화했다.
    int max = 2; //현재 배열에 들어간 원소의 개수(인덱스 0과 1)
 
    for(int i=0;i<t;i++) { //t만큼의 반복
        scanf("%d", &num);
        int i;
 
/*
 새로받은 숫자가 기존의 배열에 있는 숫자보다 크면 원소추가를 한다.
이때, 인덱스 값은 num과 같은 값을 가지게 되므로,
num이 10이면 채워지는 인덱스값도 10까지다.
 
한편 인덱스값은 0부터 시작하므로, 배열에 채워져있는 칸들의 개수(max)보다 항상 1작다.
따라서 새로운 num도 max보다 1작으므로, max보다 크거나 같아야만 기존의 num보다
크다는 것을 알 수 있다.
그래서 if의 조건문이 num>=max다
*/
        if(num>=max)
            for(i=2;i<=num;i++) {
                dic[i][0] = dic[i-1][0] + dic[i-2][0];
                dic[i][1] = dic[i-1][1] + dic[i-2][1];
            }
        printf("%d %d \n", dic[num][0], dic[num][1]);
        }
} 

 

*결과

1116KB에 396B가 나왔다.

C언어 내에서의 1등도 메모리가 1116KB인 것을 보면, 그리 나쁘지 않은 결과로 보인다.

다만 BYTE가 좀 크긴 하다.