JavaScript로 숫자가 피보나치 수열에 포함되는지 확인하는 방법

문제 개요

숫자를 하나 입력받아, 해당 숫자가 피보나치 수열(Fibonacci series)에 포함되어 있는지 판별하는 JavaScript 함수를 작성해야 합니다. 함수는 판별 결과에 따라 불리언(Boolean) 값인 true 또는 false를 반환해야 합니다.

피보나치 수열이란?

피보나치 수열은 첫 두 항이 0과 1로 시작하고, 세 번째 항부터는 바로 앞의 두 항을 더한 값이 차례로 이어지는 수열입니다.

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

접근 방법

가장 효율적인 방법은 피보나치 수열의 값을 처음부터 하나씩 생성하면서 입력값과 일치하는지 비교하는 것입니다. 생성된 값이 입력값보다 커지는 순간, 이후에는 더 이상 일치하는 값이 나올 수 없으므로 반복을 중단하고 false를 반환하면 됩니다. 피보나치 수는 기하급수적으로 증가하기 때문에 이 방식의 시간 복잡도는 O(log n) 수준으로 매우 효율적입니다.

예제 코드

구현 코드는 다음과 같습니다.

const num = 89;

const isFib = query => {
    if(query === 0 || query === 1){
        return true;
    }
    let prev = 1;
    let count = 2;
    let temp = 0;
    while(count <= query){
        if(prev + count === query){
            return true;
        }
        temp = prev;
        prev = count;
        count += temp;
    }
    return false;
};

console.log(isFib(num));

출력 결과

콘솔에 출력되는 결과는 다음과 같습니다.

true

코드 설명

입력값이 0 또는 1이면 피보나치 수열의 시작 값에 해당하므로 즉시 true를 반환합니다.

변수 prev는 현재 항의 이전 항을, count는 현재 항을 나타냅니다. 반복문 안에서 prev + count는 다음 피보나치 수가 되며, 이 값이 입력값과 일치하면 true를 반환합니다.

count가 입력값보다 커지면 수열에서 해당 값을 더 이상 찾을 수 없으므로, 반복문을 종료하고 false를 반환합니다. 이렇게 하면 불필요한 연산 없이 입력값이 피보나치 수인지 빠르고 정확하게 판별할 수 있습니다.