개발자라면 피보나치 수열의 값을 계산하는 함수를 작성하는 작업에 직면했을 것입니다. 이 고전적인 문제는 코딩 인터뷰에서 자주 나타나며 일반적으로 재귀적 구현을 ​​요구합니다. 그러나 면접관은 때때로 특정 접근 방식을 요청할 수 있습니다. 이 글에서는 JavaScript에서 가장 일반적인 피보나치 수열 구현을 살펴보겠습니다.

피보나치 수열이란 무엇입니까?

먼저 기억을 되새기자. 피보나치 수열은 각 숫자가 이전 두 숫자의 합인 일련의 숫자입니다. 0과 1로 시작합니다:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

일반적인 구현 접근 방식

1. 재귀적 접근 방식

가장 전통적인 요청은 재귀 구현입니다.

function fibonacciRecursive(n) {
  if (n 



간단하지만 이 접근 방식은 큰 n 값에 대해서는 성능이 좋지 않습니다. 16GB RAM을 탑재한 MacBook Pro i9에서 40번째 피보나치 수를 계산하는 데 약 1.5초가 걸렸습니다.


console.time('Recursive');
fibonacciRecursive(40);
console.timeEnd('Recursive');

VM379:3 Recursive: 1521.569091796875 ms




50번째 숫자를 계산하려고 하면 Chrome 탭이 응답하지 않습니다.

2. 캐싱을 이용한 재귀적 접근 방식(메모이제이션)

이 질문의 다음 변형은 재귀 구현에 캐싱 메커니즘을 추가하여 성능을 향상시키는 것입니다.


function fibonacciCached(n, cached = {[0]: 0, [1]: 1}) {
  if (n 



이 접근 방식은 초기 값이 0과 1인 캐시된 객체를 도입합니다. 주어진 숫자에 대해 먼저 피보나치 값을 이미 계산했는지 확인합니다. 그렇다면 다시 계산하는 대신 캐시된 결과를 반환합니다. 그렇지 않으면 해당 값을 계산하여 캐시에 저장합니다.

성능 향상은 상당합니다(물론 추가 메모리 사용으로 인해). 40번째 피보나치 수를 계산하는 데 ~0.02ms가 걸렸습니다.


console.time('Recursive, with caching');
fibonacciCached(40);
console.timeEnd('Recursive, with caching');

VM382:3 Recursive, with caching: 0.01806640625 ms




3. for 루프를 사용한 반복적 접근 방식

또 다른 일반적인 변형은 for 루프를 사용하여 피보나치 수열을 구현하는 것입니다.


function fibonacciWithIteration(n) {
    if (n 



이 접근 방식은 기본 재귀 방법(캐싱이 없는 방법)보다 훨씬 빠릅니다.


console.time('With iteration');
fibonacciWithIteration(40);
console.timeEnd('With iteration');

VM44:22 With iteration: 0.10107421875 ms




반복적 접근 방식은 매우 큰 입력 값을 효율적으로 처리할 수 있습니다.


console.time('With iteration');
const result = fibonacciWithIteration(1400);
console.log(result);
console.timeEnd('With iteration');

VM325:22 1.7108476902340223e 292
VM325:23 With iteration: 0.5830078125 ms





  
  
  보너스: 피보나치 수열을 배열로 반환


면접관은 전체 피보나치 수열을 n번째 숫자까지 배열로 반환하도록 요청할 수도 있습니다. 재귀적 접근 방식과 반복적 접근 방식을 모두 사용하여 이를 구현해 보겠습니다.

재귀적 접근 방식


function fibonacciSequence(n) {
  if (n === 0) {
      return [0];
  }
  if (n === 1) {
      return [0, 1];
  }

  const arr = fibonacciSequence(n - 1);
  const currentValue = arr[n - 1]   arr[n - 2];

  return [...arr, currentValue];
}

console.log(fibonacciSequence(5)); // [0, 1, 1, 2, 3, 5]




이 기능은 다음과 같이 작동합니다:

0과 1의 경우 하드코딩된 배열을 반환합니다.
기타 경우:

• 이전 번호의 시퀀스를 가져와서 arr에 저장합니다.
• arr의 마지막 두 값을 합산하여 currentValue를 계산합니다.
• arr과 currentValue를 새로운 배열로 결합하여 반환합니다.

반복적 접근 방식

function fibonacciSequenceWithIteration(n) {
  if (n 



이 기능은 다음과 같이 작동합니다:

입력이 0이면 요소 0만 있는 배열을 반환합니다.
기타 경우:

• 이전 및 다음 값을 저장하기 위해 이전 및 다음 변수를 초기화합니다.
• 초기값 [0, 1]을 사용하여 arr을 생성합니다.
• 2부터 n까지 반복하여 각 반복에서 이전과 다음의 합을 arr로 푸시합니다.
• 이전 값과 다음 값을 업데이트하고 다음 반복을 계속합니다.

결론

이 문서에서는 몇 가지 일반적인 피보나치 수열 구현을 다루지만 전체 목록은 아닙니다. 인터뷰나 작업에서 다른 변형을 발견했다면 댓글로 공유해주세요!

최신 JavaScript 및 소프트웨어 개발 소식을 받아보세요! 더 많은 통찰력과 토론을 보려면 내 Telegram 채널에 가입하세요: TechSavvy: 프런트엔드 및 백엔드.