JS 피보나치(Fibonacci)

피보나치 수열은 코딩 면접에서 자주 출제되는 주제 중 하나입니다. 단순한 수학적 구조로 시작하지만, 이를 구현하는 방법에 따라 지원자의 재귀, 반복문, 동적 계획법에 대한 이해를 평가할 수 있기 때문입니다. 각 방식의 효율성과 구조적 차이는 알고리즘적 사고력을 확인하는 좋은 기준이 됩니다.

---

재귀 방식

function fibRecursive(n) {
  if (n === 0) return 0;
  if (n === 1) return 1;
  return fibRecursive(n - 1) + fibRecursive(n - 2);
}

재귀 방식은 수학적 정의와 유사한 형태로 구현할 수 있어 직관적입니다. 다만, 동일한 계산이 반복되기 때문에 효율이 매우 떨어집니다.

시간 복잡도: O(2^n)
공간 복잡도: O(n) (호출 스택 기준)

---

반복문 방식

function fibIterative(n) {
  if (n === 0) return 0;
  let a = 0, b = 1;
  for (let i = 2; i <= n; i++) {
    [a, b] = [b, a + b];
  }
  return b;
}

반복문은 명확하고 실행 속도가 빠르며, 메모리도 적게 사용합니다. 코딩 테스트나 실무 환경에서 가장 선호되는 방식입니다.

시간 복잡도: O(n)
공간 복잡도: O(1)

---

동적 계획법 (메모이제이션)

function fibMemo(n, memo = {}) {
  if (n in memo) return memo[n];
  if (n === 0) return 0;
  if (n === 1) return 1;
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

재귀 구조를 유지하면서도 계산 결과를 저장해 중복 호출을 줄입니다. 코드의 가독성과 성능을 동시에 고려할 수 있습니다.

시간 복잡도: O(n)
공간 복잡도: O(n)

---

방식 비교 요약

방식	시간 복잡도	공간 복잡도	특징
재귀	O(2^n)	O(n)	간결하나 비효율적
반복문	O(n)	O(1)	빠르고 메모리 효율 우수
동적 계획법	O(n)	O(n)	재귀 구조 유지 + 성능 개선

---

알고리즘 면접 준비를 위한 추천

피보나치 수열은 알고리즘 입문의 핵심 개념입니다. 다양한 방식으로 구현해보며 함수 호출 흐름, 시간 복잡도, 최적화 전략을 익히는 데 효과적입니다.

아래의 강의와 실습 플랫폼은 면접과 코딩 테스트 준비에 도움이 됩니다:

• 프로그래머스 알고리즘 강의: https://school.programmers.co.kr/
• LeetCode JavaScript 문제집: https://leetcode.com/
• FastCampus 코딩 테스트 강의: https://fastcampus.co.kr/