70. Climbing Stairs

• 난이도: 쉬움 (Easy)
• 링크: LeetCode 70
• 풀이 날짜: 2025.10.13

1. 문제 이해

한 번에 1계단 또는 2계단을 오를 수 있을 때, n개의 계단을 오르는 서로 다른 방법의 총 수를 구하는 문제이다.

 

예를 들어,

• n = 2 → (1+1, 2) → 총 2가지
• n = 3 → (1+1+1, 1+2, 2+1) → 총 3가지

즉, n번째 계단에 도달하는 방법은

(n-1)번째에서 한 칸, 또는 (n-2)번째에서 두 칸 올라오는 경우의 합이다.

한번더 풀어서 설명하면, n-1 번째까지 오르는 경우의 수 + n-2 번째까지 오는 경우의 수 를 합하면 n번째에 오르는 경우의 수인 것이다.

점화식은 dp[i] = dp[i-1] + dp[i-2] 이다.

 

2. 접근 아이디어 및 자료구조

이 문제는 1차원 DP(1Dimensional Dynamic Programming) 로 해결할 수 있다.

즉, 각 계단마다 “해당 계단까지 오르는 경우의 수”를 저장하면서 앞선 두 계단의 값을 더해가는 방식이다.

• dp[i] = i번째 계단까지의 방법 수
• dp[1] = 1, dp[2] = 2
• 이후 dp[i] = dp[i-1] + dp[i-2]

이 문제는 이전 두 값만 알면 되므로, 배열 전체를 쓸 필요 없이 변수 2개만으로 최적화할 수 있다.

 

DP

여기에서 DP(Dynamic Programming, 동적 프로그래밍)는 복잡한 문제를 더 작은 하위 문제(subproblem)로 나누고,

그 결과를 저장(Memoization) 해가며 전체 문제를 효율적으로 해결하는 알고리즘 기법이다.

 

아래의 풀이코드에서 first, second 변수는 DP 배열의 압축판이라 할 수 있는데,

전형적인 DP 풀이라면 아래와 같이 dp 배열을 만들지만, 이렇게 하면 O(n) 공간이 필요하다.

dp[1] = 1;
dp[2] = 2;
for(let i=3; i<=n; i++){
    dp[i] = dp[i-1] + dp[i-2];
}
return dp[n];

대신에, first와 second 변수를 사용하면, 배열 대신 마지막 두 단계의 값만 저장해서 공간을 O(1)로 최적화한 형태가 된다.

즉, 배열을 쓰지 않고 메모이제이션(Memoization) 효과만 유지한 것이라서 여전히 DP라고 부를 수 있다.

 

3. 풀이 코드

var climbStairs = function(n) {
  if (n <= 2) return n; // 2이하인 경우, early return.

  let first = 1, second = 2;

  for (let i = 3; i <= n; i++) {
    const third = first + second;
    // 다음 계단으로 진행되기 때문에, 
    first = second; // first 는 second 값이,
    second = third; // second 는 가장 최근 값인 third 값이 할당된다.
  }

  return second; // 마지막 계단인 n 에서의 총 가지수 합인 third (first + second) 값이 할당되어 있다.
};

구분	복잡도	설명
시간 복잡도	O(n)	n번 반복문 수행
공간 복잡도	O(1)	변수 3개만 사용

 

4. 정리 및 요약

포인트	설명
문제 유형	1D DP (피보나치 응용)
핵심 로직	dp[i] = dp[i-1] + dp[i-2]
메모리 최적화	배열 대신 변수 2개 사용
유사 문제	Fibonacci Number, House Robber, Min Cost Climbing Stairs

이 문제의 핵심은 “DP의 점화식을 이해하고, 공간을 최소화하는 것” 으로

결국 계단 오르기는 피보나치 수열의 형태로 귀결된다.

탐색이 아니라 누적 계산 문제이며, 반복문으로 간단히 처리할 수 있는 전형적인 1D DP 문제다.