자바스크립트로 숫자가 피보나치 수열에 포함되는지 확인하는 방법

이번 글에서는 숫자를 입력받아 해당 숫자가 피보나치 수열에 포함되는지 판별하는 자바스크립트 함수를 작성해 보겠습니다. 함수는 숫자가 피보나치 수열에 속하면 true, 그렇지 않으면 false를 반환합니다.

피보나치 수열이란?

피보나치 수열은 첫 두 항이 0과 1로 시작하고, 이후의 모든 항은 바로 앞의 두 항을 더한 값으로 이루어지는 수열입니다.

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

구현 방법

가장 직관적인 방법은 0과 1부터 시작해 피보나치 수를 차례대로 생성하면서, 입력값과 같아지면 true를 반환하고 입력값을 초과하면 false를 반환하는 것입니다.

예시 코드

const num = 89;

const isFibonacci = num => {
  // 음수는 피보나치 수열에 포함되지 않음
  if (num < 0) {
    return false;
  }
  let prev = 0;
  let curr = 1;
  // curr이 num 이상이 될 때까지 수열 생성
  while (curr < num) {
    const next = prev + curr;
    prev = curr;
    curr = next;
  }
  // 수열이 정확히 num에 도달했는지 확인
  return curr === num;
};

console.log(isFibonacci(num));

코드 설명

• prev와 curr은 각각 수열에서 연속된 두 항을 나타냅니다.
• 반복문 안에서 next = prev + curr로 다음 항을 계산한 뒤, 두 변수를 한 칸씩 앞으로 이동시킵니다.
• 반복문이 종료되는 시점의 curr은 입력값보다 크거나 같은 가장 작은 피보나치 수입니다.
• 따라서 curr === num이라면 입력값은 피보나치 수열에 포함되는 것입니다.

출력 결과

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

true

89는 피보나치 수열의 항(55 + 34)이므로 true가 출력됩니다.

수학적 공식을 활용한 대안

조금 더 수학적인 접근도 가능합니다. 어떤 수 n이 피보나치 수일 필요충분조건은 5n² + 4 또는 5n² − 4가 완전제곱수라는 것이며, 이 성질을 이용하면 반복문 없이 상수 시간에 판별할 수 있습니다.

const isPerfectSquare = x => Number.isInteger(Math.sqrt(x));

const isFibonacci = n =>
  n >= 0 && (isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4));

console.log(isFibonacci(89)); // true
console.log(isFibonacci(50)); // false