피보나치 수열 (Fibonacci Sequence) - JavaScript

 

오늘은 피보나치 수열이 적용된 백준 문제를 풀어본다.

백준 문제 14495번에 대한 정리이다.

 

문제: 피보나치 비스무리한 수

• 입력: 자연수 n
• 로직: n번째 피보나치 비스무리한 수열
  • f(n) = f(n-1) + f(n-3)
  • f(1) = f(2) = f(3) = 1
  • 1, 1, 1, 2, 3, 4, 6, 9, 13, 19, ...
• 출력: 자연수 result

제출한 답안

처음에는 재귀함수를 이용해서 풀었는데 시간 초과로 실패했다.

// 시간 초과로 실패
const input = (
	process.platform === 'linux' ? 
		require('fs').readFileSync('/dev/stdin').toString() : `10`
).trim();
// console.log(input

const getFibonacci = (num) => {
  if (num <= 0) return 0;
  if (0 < num && num <= 3) return 1;
  return getFibonacci(num - 1) + getFibonacci(num - 3);
};

console.log(getFibonacci(Number(input)));

 

시간 제한으로 방법을 찾아 코드를 수정했다.

• 재귀함수를 반복문 형태로 수정
• JS number 원시 자료형의 범위를 벗어나는 경우가 있으므로 BigInt를 사용

const input = (
	process.platform === 'linux' ? 
		require('fs').readFileSync('/dev/stdin').toString() : `10`
).trim();

const getFibonacci = (input) => {
	const idx = Number(input);
	const dp = [0, 1, 1, 1].map(BigInt);
	for (let i = 4; i < idx; i++) {
		dp[idx] = dp[idx-1] + dp[idx-3];
	}
	return dp[idx].toString();
}

console.log(getFibonacci(input));

 

BigInt가 문제였을 수 있지만,

재귀함수로 접근하는 방법이 배열의 인덱싱과 반복문으로 계산하는 것 보다 더 느린 것 같다.

 

 

 

출처 1: 백준 14495번

출처 2: Node.js) 백준 14495번: 피보나치 비스무리한 수열