⚡

Fibonacci

Fibonacci - Explanation

보통 함수 O(n) O(1)

Problem Summary

Write a function that returns the nth Fibonacci number.

Go to Problem →

Detailed Explanation

이 문제는 **피보나치 수열**과 **반복문 최적화**를 학습합니다. 재귀의 비효율성을 이해하고 반복문으로 개선하는 방법을 배웁니다. **피보나치 수열의 정의** - F(0) = 0 - F(1) = 1 - F(n) = F(n-1) + F(n-2) (n >= 2) 수열: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ... **재귀 vs 반복문** 재귀 구현: `return fibonacci(n-1) + fibonacci(n-2)` - 문제: 같은 값을 여러 번 계산 (지수 시간 복잡도) - fibonacci(50)은 매우 오래 걸림 반복문 구현 (이 문제의 해답): - 이전 두 값만 기억하며 진행 - 선형 시간 복잡도로 효율적 **구조 분해 할당으로 값 교환** `[a, b] = [b, a + b]`는 임시 변수 없이 값을 교환합니다: - 새 a는 이전 b - 새 b는 이전 a + b **fibonacci(6) 계산 과정** - 시작: a=0, b=1 - i=2: [a,b] = [1, 1] - i=3: [a,b] = [1, 2] - i=4: [a,b] = [2, 3] - i=5: [a,b] = [3, 5] - i=6: [a,b] = [5, 8] - 결과: 8

Solution Code

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

Key Concepts from This Problem

1. 피보나치 수열
2. 반복문 최적화
3. 구조 분해 할당
4. 재귀 vs 반복

Common Mistakes

✗ 재귀로 구현하면 큰 n에서 매우 느려집니다 (O(2^n))
✗ n=0과 n=1의 기저 조건을 놓치면 잘못된 결과가 나옵니다
✗ 값 교환 시 임시 변수 없이 a=b; b=a+b;를 하면 잘못된 결과가 나옵니다

Hints

Hint 1: F(0) = 0, F(1) = 1
Hint 2: F(n) = F(n-1) + F(n-2)
Hint 3: 반복문이 재귀보다 효율적입니다.

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#함수 #피보나치 #알고리즘
Solve Problem Other Problems