Climbing Stairs

문제 링크

https://leetcode.com/problems/climbing-stairs/

문제 설명

당신은 n 계단의 꼭대기에 도달하기 위해 계단을 올라가고 있습니다. 한 번에 1계단 또는 2계단을 오를 수 있다고 할 때, 꼭대기까지 오르는 서로 다른 방법의 수를 구하세요.

입력: 정수 n (계단 수)
출력: 꼭대기까지 오르는 서로 다른 방법의 수

예제

예제 1
- 입력: n = 2
- 출력: 2
- 설명: 꼭대기까지 오르는 방법은 다음과 같습니다:
  1. 1 계단 + 1 계단
  2. 2 계단
예제 2
- 입력: n = 3
- 출력: 3
- 설명: 꼭대기까지 오르는 방법은 다음과 같습니다:
  1. 1 계단 + 1 계단 + 1 계단
  2. 1 계단 + 2 계단
  3. 2 계단 + 1 계단

풀이 전략

이 문제는 피보나치 수열과 유사한 점화식을 통해 풀 수 있습니다. 계단의 맨 마지막 위치에 오르는 방법을 생각해보면:

n번째 계단에 도달하려면 (n-1)번째 계단에서 1계단을 오르거나, (n-2)번째 계단에서 2계단을 오르는 방법이 있습니다.
즉, n번째 계단을 오르는 방법의 수는 (n-1)번째 계단까지 오르는 방법의 수와 (n-2)번째 계단까지 오르는 방법의 수를 합한 것과 같습니다.

이를 수식으로 표현하면:
[ \text{ways}(n) = \text{ways}(n-1) + \text{ways}(n-2) ]
초기값으로는 ways(0) = 1, ways(1) = 1로 설정할 수 있습니다.

코드 분석

방법: 동적 프로그래밍(DP) 사용

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1

        # 초기화
        dp = [0] * (n + 1)
        dp[0], dp[1] = 1, 1

        for i in range(2, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]  # 점화식 적용

        return dp[n]

동작 원리:
- dp 배열을 생성하여 dp[i]에 i번째 계단까지 오르는 방법의 수를 저장합니다.
- dp[0]과 dp[1]은 각각 1로 초기화하고, 2번째 계단부터 n번째 계단까지의 방법 수를 점화식을 사용해 채워 나갑니다.
- 최종적으로 dp[n]이 꼭대기까지 오르는 방법의 수가 됩니다.
시간 복잡도: (O(n)) - n번의 반복문이 필요합니다.
공간 복잡도: (O(n)) - dp 배열에 n+1개의 값을 저장합니다.

방법: 공간 최적화

동적 프로그래밍에서 이전 두 값만 필요하므로 배열을 쓰지 않고 두 변수만으로 해결할 수도 있습니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n <= 1:
            return 1

        a, b = 1, 1
        for _ in range(2, n + 1):
            a, b = b, a + b  # 이전 두 값을 이용해 현재 값을 계산

        return b

동작 원리:
- 두 변수 a와 b는 각각 n-2번째와 n-1번째 계단까지의 방법 수를 저장합니다.
- a, b = b, a + b을 반복하여 b에 최종 결과를 저장합니다.
시간 복잡도: (O(n)) - n번의 반복문이 필요합니다.
공간 복잡도: (O(1)) - 두 변수만 사용합니다.

요약

이 문제는 피보나치 수열의 점화식을 이용하여 해결할 수 있습니다.
동적 프로그래밍(DP) 배열 사용과 공간 최적화 방법으로 구현할 수 있습니다.
최적화된 방법은 시간 복잡도 (O(n)), 공간 복잡도 (O(1))로 매우 효율적입니다.