13. 피보나치 수열 (Fibonacci Numbers) Codility Lesson 한국어 정리본 (JavaScript ver.)

피보나치 수열(Fibonacci Numbers)이란?

피보나치 수열은 다음과 같이 정의된다.

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n ≥ 2)

예제:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89 ...

---

1. O(2ⁿ) 시간 복잡도의 재귀 방식 (비효율적)

JavaScript 코드:

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

이 방식은 너무 느려서 n이 커질수록 사용할 수 없다.

---

2. O(n) 시간 복잡도의 동적 프로그래밍 방식

JavaScript 코드:

function fibonacciDP(n) {
    let fib = new Array(n + 1).fill(0);
    fib[1] = 1;
    
    for (let i = 2; i <= n; i++) {
        fib[i] = fib[i - 1] + fib[i - 2];
    }
    return fib[n];
}

이 방식은 O(n) 시간 복잡도로 피보나치 수열을 계산할 수 있다.

---

3. O(log n) 시간 복잡도의 행렬 거듭제곱 방식

피보나치 수열을 더 빠르게 계산하는 방법으로 행렬 거듭제곱 방식 을 사용할 수 있다.

function fibonacciMatrix(n) {
    if (n === 0) return 0;
    let F = [[1, 1], [1, 0]];
    power(F, n - 1);
    return F[0][0];
}

function power(F, n) {
    if (n === 0 || n === 1) return;
    let M = [[1, 1], [1, 0]];
    
    power(F, Math.floor(n / 2));
    multiply(F, F);
    
    if (n % 2 !== 0) multiply(F, M);
}

function multiply(F, M) {
    let x = F[0][0] * M[0][0] + F[0][1] * M[1][0];
    let y = F[0][0] * M[0][1] + F[0][1] * M[1][1];
    let z = F[1][0] * M[0][0] + F[1][1] * M[1][0];
    let w = F[1][0] * M[0][1] + F[1][1] * M[1][1];
    
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

이 방법은 O(log n) 시간 복잡도로 매우 효율적이다.