LeetCode 70 - Climbing Stairs

이 문제는 계단을 한 번에 1칸 또는 2칸씩 오를 수 있을 때, 정상까지 가는 서로 다른 방법의 수를 구하는 문제다. 난이도는 Easy이고, 단순 재귀가 왜 중복 계산을 만들며 memoization이 그 중복을 어떻게 줄이는지 확인하기 좋다.

문제 링크 & 설명

문제 링크: 70. Climbing Stairs
요약: 자연수 n이 주어졌을 때, 1칸 또는 2칸씩 올라서 정확히 n번째 계단에 도달하는 서로 다른 방법의 수를 반환하는 문제다.

예를 들어 n = 2라면 가능한 방법은 두 가지다.

1 + 1
2

n = 3이면 다음 세 가지가 가능하다.

1 + 1 + 1
1 + 2
2 + 1

현재 위치에서 할 수 있는 선택은 1칸 오르거나 2칸 오르는 것뿐이다. 그래서 처음에는 재귀로 현재 계단에서 다음 상태를 나눠보는 방식이 자연스럽게 떠오른다.

접근 방법

1. 재귀로 경우의 수 나누기

현재 계단을 step이라고 하면, 다음 선택지는 step + 1과 step + 2다. 두 경로에서 나오는 경우의 수를 더하면 현재 위치에서 정상까지 가는 방법의 수가 된다.

종료 조건은 두 가지로 나눌 수 있다. 현재 위치가 n이면 정확히 도착한 것이므로 1을 반환하고, 현재 위치가 n을 넘어가면 유효하지 않은 경로이므로 0을 반환한다.

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]):
        if step > n:
            return 0
        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)
        return first_way + second_way

이 방식은 직관적이어서 문제의 내용 그대로를 표현하기에는 좋은데, 같은 step에 도달하는 경로가 여러 개 생기면 그 이후의 계산을 계속 반복하게 된다.

예를 들어 n = 4라고 하면 단순 재귀 호출은 대략 다음처럼 퍼진다.

climb(0)
├── climb(1)
│   ├── climb(2)
│   │   ├── climb(3)
│   │   │   ├── climb(4) ✓
│   │   │   └── climb(5) ✗
│   │   └── climb(4) ✓
│   └── climb(3)
│       ├── climb(4) ✓
│       └── climb(5) ✗
└── climb(2)
    ├── climb(3)
    │   ├── climb(4) ✓
    │   └── climb(5) ✗
    └── climb(4) ✓

여기서 climb(2)와 climb(3)이 여러 번 다시 계산된다. 특정 step에서 정상까지 가는 방법의 수는 그 step에 어떻게 도착했는지와 상관없이 같으므로, 이 값을 저장해두면 같은 하위 문제를 다시 풀지 않아도 된다.

2. memoization으로 중복 계산 줄이기

중복 계산을 줄이려면 각 step에서 정상까지 가는 방법의 수를 한 번 계산한 뒤 저장하면 된다. 이후 같은 step이 다시 나오면 재귀를 더 내려가지 않고 저장된 값을 바로 반환한다.

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]):
        if step > n:
            return 0
        if step in memo:
            return memo[step]
        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)
        memo[step] = first_way + second_way
        return memo[step]

여기서 memo는 step을 key로, 그 위치에서 정상까지 가는 방법의 수를 value로 저장한다. 같은 위치에 다시 도달했을 때 이미 계산된 값을 재사용하므로, 각 계단 위치는 한 번만 계산된다.

제공한 코드에서는 시작할 때 1칸을 먼저 오른 경우와 2칸을 먼저 오른 경우를 나눠서 더했다.

return self.climb_rec(n, 1, memo) + self.climb_rec(n, 2, memo)

즉, 첫 선택지를 바깥에서 한 번 나눈 뒤, 이후의 중복 상태는 같은 memo를 공유하면서 계산하는 구조다. n = 1일 때는 1칸 오르는 방법 하나뿐이므로 바로 1을 반환한다.

복잡도 분석

시간 복잡도: O(n)
- memoization을 사용하면 각 계단 위치에 대한 경우의 수를 한 번씩만 계산한다. 따라서 입력값 n에 비례한다.
공간 복잡도: O(n)
- memo dictionary에 계단 위치별 결과를 저장하고, 재귀 호출 스택도 최대 n 깊이까지 내려갈 수 있다.

구현 코드

최종 코드는 재귀와 memoization을 사용했다. 현재 위치에서 1칸 또는 2칸 이동한 결과를 더하고, 한 번 계산한 위치는 memo에 저장한다.

from typing import Dict

class Solution:
    def climb_rec(self, n: int, step: int, memo: Dict[int, int]) -> int:
        if step > n:
            return 0

        if step in memo:
            return memo[step]

        if step == n:
            return 1

        first_way = self.climb_rec(n, step + 1, memo)
        second_way = self.climb_rec(n, step + 2, memo)

        memo[step] = first_way + second_way
        return memo[step]

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

        memo: Dict[int, int] = {}
        return self.climb_rec(n, 1, memo) + self.climb_rec(n, 2, memo)

요약 및 회고

이 문제는 현재 위치에서 1칸 또는 2칸을 선택하는 구조라 재귀로 생각하기 쉽다. 다만 단순 재귀는 같은 계단 위치에서 남은 경우의 수를 여러 번 다시 계산하기 때문에 입력이 커질수록 비효율적이다.

memoization을 붙이면 각 step의 결과를 저장해서 재사용할 수 있고, 그 결과 시간복잡도를 O(n)으로 줄일 수 있다. 결국 이 문제에서 중요한 점은 경로 전체를 저장하는 것이 아니라, 특정 계단 위치에서 정상까지 가는 방법의 수가 항상 같다는 사실을 이용해 중복 상태를 캐싱하는 것이다.