문제 개요
숫자 하나를 인수로 받아 해당 숫자가 피보나치 수(Fibonacci number), 즉 피보나치 수열에 속하는 값인지 판별하는 자바스크립트 함수를 작성해 보겠습니다. 함수는 입력값이 피보나치 수이면 true, 그렇지 않으면 false를 반환해야 합니다.
피보나치 수열이란?
피보나치 수열은 첫 두 항이 0과 1이고, 세 번째 항부터는 바로 앞의 두 항을 더한 값이 되는 수열입니다.
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ...
구현 코드
const num = 2584;
const isFibonacci = num => {
if(num === 0 || num === 1){
return true;
}
let prev = 1;
let count = 2;
let temp = 0;
while(count <= num){
if(prev + count === num){
return true;
};
temp = prev;
prev = count;
count += temp;
};
return false;
};
console.log(isFibonacci(num));
console.log(isFibonacci(6765));
console.log(isFibonacci(45));
console.log(isFibonacci(8767));
콘솔 출력 결과
true true false false
코드 동작 원리
위 함수는 다음과 같은 순서로 동작합니다.
- 입력값이 0 또는 1이면 정의상 피보나치 수이므로 즉시
true를 반환합니다. prev와count변수를 각각 1과 2로 초기화한 뒤, while 루프 안에서 두 값을 계속 더해가며 피보나치 수열을 차례로 생성합니다.- 매 반복마다
prev + count가 입력값과 같은지 검사하고, 일치하면 해당 숫자는 피보나치 수이므로true를 반환합니다. count가 입력값을 초과할 때까지 일치하는 값이 없다면 피보나치 수가 아니므로false를 반환합니다.
대안: 수학적 성질을 이용한 판별법
반복문 없이 수학적 성질을 활용할 수도 있습니다. 어떤 수 n이 피보나치 수일 필요충분조건은 5n² + 4 또는 5n² − 4가 완전 제곱수라는 것입니다. 이를 이용하면 코드를 훨씬 간결하게 작성할 수 있습니다.
const isPerfectSquare = x => Number.isInteger(Math.sqrt(x)); const isFibonacciMath = n => isPerfectSquare(5 * n * n + 4) || isPerfectSquare(5 * n * n - 4); console.log(isFibonacciMath(2584)); // true console.log(isFibonacciMath(45)); // false
두 방식 모두 주어진 숫자가 피보나치 수열에 속하는지 정확하게 판별할 수 있으며, 상황에 따라 가독성과 성능을 고려해 선택하면 됩니다.