[바미] 피보나치 수 5

 

 

문제

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

코드

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim();
const n = parseInt(input, 10);

function fibonacci(n) {
    if (n === 0) {
        return 0;
    } else if (n === 1) {
        return 1;
    } else {
        return fibonacci(n - 1) + fibonacci(n - 2);
    }
}

const result = fibonacci(n);
console.log(result);

문제 해설

이번 문제는 출제자가 재귀 함수를 사용하여 계산하길 원하는 문제입니다.

피보나치 수열은 아래와 같이 정의할 수 있습니다.

• 𝐹(0) = 0
• 𝐹(1) = 1
• 𝐹(𝑛) = 𝐹(𝑛−1) + 𝐹(𝑛−2) for 𝑛  ≥  2

따라서 정수 𝑛에 대해𝑛번째 피보나치 수를 계산하는 재귀 함수를 작성하면 됩니다.

𝑛이 0이면 0을 반환하고, 𝑛 이 1이면 1을 반환, 둘 다 아니면 𝐹(𝑛) = 𝐹(𝑛−1) + 𝐹(𝑛−2)을 계산하여 반환 해줍니다.

시간 복잡도

시간 복잡도는 알고리즘이 입력의 크기에 따라 얼마나 빠르게 실행되는지를 나타냅니다

 

재귀적 피보나치 수 계산의 시간 복잡도는 O\left( 2^{n}\right)이 됩니다. 각 호출이 두 개의 하위 문제를 다시 호출하기 때문에 지수 시간이 소요되지만 주어진 n의 최대 값은 20이기 때문에 이 정도 복잡도는 문제가 되지 않습니다.

공간 복잡도

공간 복잡도는 알고리즘이 얼마나 많은 메모리 공간을 사용하는지 나타냅니다.

 

재귀 함수 호출 스택의 깊이는 𝑛이므로 공간 복잡도는 𝑂(𝑛)이 됩니다.