Climbing Stairs Explanation

Problem Summary

Find how many ways to climb n stairs when you can take 1 or 2 steps at a time.

Detailed Explanation

이 문제는 **동적 프로그래밍**과 **피보나치 패턴**을 학습합니다. ## 핵심 개념: 계단 오르기와 피보나치 n번째 계단에 도달하는 방법 = (n-1번째에서 1칸) + (n-2번째에서 2칸) ### 점화식 ``` f(n) = f(n-1) + f(n-2) ``` - f(1) = 1 (1칸) - f(2) = 2 (1+1 또는 2) - f(3) = 3 (1+1+1, 1+2, 2+1) ### 공간 최적화된 풀이 ```javascript let a = 1, b = 2; for (let i = 3; i <= n; i++) { [a, b] = [b, a + b]; } return b; ``` ### 왜 피보나치인가? - n번째 계단에 도달하려면 - n-1번째에서 1칸 오르거나 - n-2번째에서 2칸 오르면 됨 - 이 두 경우의 수를 더함 ### DP vs 재귀 재귀는 O(2^n)으로 매우 느립니다. 반복 또는 메모이제이션을 사용하세요.

Solution Code

solution.js

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

Key Concepts from This Problem

1. 동적 프로그래밍

2. 피보나치 수열

3. 점화식

4. 공간 최적화

Common Mistakes

✗ 재귀로 풀면 시간 초과가 발생합니다

✗ f(1)=1, f(2)=2 초기값을 정확히 설정해야 합니다

✗ n이 0일 때 예외 처리가 필요할 수 있습니다

Hints

Hint 1: 피보나치 수열과 비슷한 패턴입니다.

Complexity Analysis

Time Complexity

O(n)

Grows linearly with input size

Space Complexity

O(1)

Uses almost no additional memory

Related Tags

#알고리즘 #동적프로그래밍 #피보나치