피보나치 수열(Finbonacci Sequence)

피보나치 수열(Fibonacci Sequence)란?

피보나치 수열(Fibonacci Sequence)은 각 숫자가 그 앞의 두 숫자의 합인 수열이다. 이 수열은 13세기 수학자 레오나르도 피보나치(Leonardo Fibonacci)의 이름을 따서 명명되었다. 피보나치 수열은 자연에서 자주 발견되는 패턴으로, 예를 들어 나뭇잎의 배열, 꽃잎의 수, 소라 껍질의 나선형 등에서 볼 수 있다.

수열의 시작은 일반적으로 0과 1로 설정되며, 그 다음 수들은 다음과 같이 계산된다.

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

피보나치 수열의 수식

피보나치 수열의 기본 수식을 정의하면 다음과 같다.

• F(0) = 0
• F(1) = 1
• F(n) = F(n-1) + F(n-2) (n >= 2)

이 수식에 따라 n번째 피보나치 수를 구할 수 있다.

자바스크립트로 피보나치 수열 구현하기

자바스크립트로 피보나치 수열을 계산하는 방법에는 여러 가지가 있다. 가장 기본적인 방법은 재귀(recursion)를 사용하는 것이며, 반복(iteration)을 사용하는 방법도 있다.

재귀적 방법

재귀적 방법은 피보나치 수열의 정의를 그대로 구현하는 방법이며, 코드로 표현하면 다음과 같다.

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

console.log(fibonacci(10)); // 55

이 코드에서는 fibonacci 함수가 n이 0이거나 1일 때까지 자기 자신을 계속 호출하면서 각 피보나치 수를 계산한다. 하지만 이 방식은 n이 커질수록 계산 시간이 급격히 늘어나게 되는데, 중복된 계산이 너무 많이 발생하기 때문이다.

반복적 방법

반복적 방법은 이전 값을 저장해두고 이를 이용해 다음 피보나치 수를 계산한다.

function fibonacciIterative(n) {
    let a = 0,
        b = 1,
        temp;
    if (n === 0) return a;
    for (let i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

console.log(fibonacciIterative(10)); // 55

이 방식은 재귀 호출을 사용하지 않고, 단순히 반복문을 이용해 피보나치 수열을 계산한다.
따라서 시간 복잡도는 O(n)으로 효율적이다.

동적 계획법(Dynamic Programming)

동적 계획법을 사용하면 중복 계산을 피하고, 재귀적 방법보다 훨씬 빠르게 피보나치 수를 구할 수 있다. 또한 메모이제이션(Memoization)을 사용하여 이미 계산한 값을 저장해두고 필요할 때 다시 사용하는 방식이다.

function fibonacciDP(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;
    memo[n] = fibonacciDP(n - 1, memo) + fibonacciDP(n - 2, memo);
    return memo[n];
}

console.log(fibonacciDP(10)); // 55

이 방법은 각 피보나치 수를 한 번씩만 계산하며, 결과를 메모리에 저장하여 재사용한다. 이로 인하여 계산 속도가 크게 향상된다.