[JS] 백준 1003번 피보나치 함수

 

출처

백준 온라인 저지

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

1003번: 피보나치 함수

 

문제

다음 소스는 N번째 피보나치 수를 구하는 C++ 함수이다.

int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}

fibonacci(3)을 호출하면 다음과 같은 일이 일어난다.

• fibonacci(3)은 fibonacci(2)와 fibonacci(1) (첫 번째 호출)을 호출한다.
• fibonacci(2)는 fibonacci(1) (두 번째 호출)과 fibonacci(0)을 호출한다.
• 두 번째 호출한 fibonacci(1)은 1을 출력하고 1을 리턴한다.
• fibonacci(0)은 0을 출력하고, 0을 리턴한다.
• fibonacci(2)는 fibonacci(1)과 fibonacci(0)의 결과를 얻고, 1을 리턴한다.
• 첫 번째 호출한 fibonacci(1)은 1을 출력하고, 1을 리턴한다.
• fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 결과를 얻고, 2를 리턴한다.

1은 2번 출력되고, 0은 1번 출력된다. N이 주어졌을 때, fibonacci(N)을 호출했을 때, 0과 1이 각각 몇 번 출력되는지 구하는 프로그램을 작성하시오.

반응형

풀이

피보나치 함수가 돌아가는 방식을 이해하면 문제 해결이 쉬워지는 문제입니다.

fibonacci(n) = fibonacci(n‐1) + fibonacci(n‐2);

fibonacci(3) = fibonacci(2) + fibonacci(1);

피보나치 함수에 대한 자세한 내용은 '더보기' 버튼을 클릭해 확인할 수 있습니다.

위 코드에서 보듯이 피보나치의 함수는 fibonacci(3)은 fibonacci(2)와 fibonacci(1)의 합으로 이뤄집니다;

 

하지만 해당 위 방식을 사용하게 될 시 fibonacci(5)의 상황에서 fibonacci(4)와 fibonacci(3)의 결과가 나오지만 다시 fibonacci(4)의 상황에서 fibonacci(3)과 fibonacci(2) 즉 fibonacci(3)의 결과를 다시 구해야 하는 상황이 생깁니다.

 

이러한 중복적인 함수가 돌아가는 현상을 막기 위해 fibonacci(3)의 결괏값을 저장시켜줍니다.

 

이러한 방법이 가능한 이유는 fibonacci(3)의 값은 fibonacci(2)와 fibonacci(1)의 합이며 각 함수의 값을 구했으니 fibonacci(3), fibonacci(2), fibonacci(1)의 값은 저장시켜줍니다.

 

fibonacci(4)의 값은 fibonacci(3)과 fibonacci(2)의 합입니다.

 

하지만 이미 fibonacci(3), fibonacci(2)의 값을 저장시켜놨기에 저장시킨 값을 더하기만 하면 fibonacci(4)의 값을 구할 수 있습니다.

 

이해를 위한 이미지

 

이를 이용하여 fibonacci(0) 일 때는 0이 바로 반환되니 이를 [1, 0]로 배열을 만들어주고 fibonacci(1) 일 때도 1이 바로 반환되니 [0, 1]로 배열을 만들어줍니다.

 

이제 fibonacci(2)의 수는 fibonacci(1), fibonacci(0)의 각 0과 1의 합이 fibonacci(2)의 값이 됩니다.

 

---

 

 

fibonacci(0), fibonacci(1) 일 때 각각 바로 0과 1로 반환되니 [1, 0], [0, 1] 배열을 만들어줍니다.

이제 차례대로 fibonacci(2)의 값은 fibonacci(1)과 fibonacci(0)의 각 0과 1의 합으로 구해줄 수 있습니다.

 

이를 n번까지 계속 배열에 저장시켜주며 값을 구해주면 됩니다.

 

코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");

const len = input.shift();

for (let i = 0; i < len; i++) {
    const n = input[i];

    const fibonacci = [[1, 0], [0, 1]];
    
    for (let j = 2; j <= n; j++) {
        fibonacci[j] = [
            fibonacci[j-1][0] + fibonacci[j-2][0], 
            fibonacci[j-1][1] + fibonacci[j-2][1]
        ];
    }

    console.log(fibonacci[n].join(" "));
}

 

다른 코드

위와 같은 이전에 구한 값을 저장시키는 방식입니다.

 

결국 fibonacci(n)의 결괏값을 구하기 위해서는 순차적으로 구해온 fibonacci(n-1), fibonacci(n-2)의 값만 있으면 됩니다.

 

즉 fibonacci(n-1), fibonacci(n-2)의 값만을 변수에 저장시켜 값을 구할 수 있습니다.

 

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split("\n");

const len = input.shift();

for (let i = 0; i < len; i++) {
    let oneCount = 0, zeroCount = 1;
    
    for (let j = 1; j <= input[i]; j++) {
        const tmpCount = zeroCount;
       
        zeroCount = oneCount;
        oneCount = tmpCount + oneCount;
    }

    console.log(zeroCount + " " + oneCount);   
}