LeetCode

LeetCode 70 Climbing Stairs 풀이: 1차원 동적 계획법

작성·코드 검증: solve together · 작성 언어: Python

0. 문제 링크와 출처

각 단계에서 1칸 또는 2칸만 이동할 수 있을 때 정상에 도달하는 방법의 수를 구하는 문제다. 마지막 이동을 기준으로 동적 계획법 점화식을 세워야 하므로 Level 3으로 판단했다.

1. 문제 요약

계단이 n개 있고 한 번에 1칸 또는 2칸을 올라갈 수 있다. 정상에 도착하는 서로 다른 이동 순서의 가지수를 반환해야 한다.

예를 들어 n = 3이면 다음 세 가지 순서가 있다.

1 + 1 + 1
1 + 2
2 + 1

여기서 순서가 다르면 서로 다른 방법으로 세어야 한다.

2. 문제 해결에 사용되는 알고리즘이나 자료구조 설명

마지막 이동이 1칸인지 2칸인지로 경로를 나눈다

i번째 계단에 도착하는 마지막 이동은 두 가지뿐이다.

  • i - 1번째 계단에서 1칸 올라오는 경우
  • i - 2번째 계단에서 2칸 올라오는 경우

dp[i]를 i번째 계단에 도착하는 이동 순서의 수라고 하면, 두 경우는 마지막 이동이 다르므로 서로 겹치지 않는다. 따라서 다음 점화식으로 모든 경로를 한 번씩 센다.

dp[i] = dp[i - 1] + dp[i - 2]

dp[0] = 1은 아직 이동하지 않은 시작 상태를 한 가지 방법으로 세는 값이고, dp[1] = 1이다. 따라서 i = 2부터는 별도 예외 없이 같은 점화식을 사용할 수 있다. 구현은 직전 두 상태만 필요하므로 배열 대신 변수 두 개를 갱신한다.

계단 i 마지막 1칸 이동 dp[i - 1] 마지막 2칸 이동 dp[i - 2] dp[i]
0 — — 1
1 1 — 1
2 1 1 2
3 2 1 3
4 3 2 5

코드의 two_steps_before와 one_step_before는 각각 dp[0], dp[1]에서 시작한다. n = 1이면 반복문을 건너뛰어 1을 반환하고, n >= 2이면 매 반복에서 이 두 값을 다음 계단의 상태로 옮긴다.

3. 문제 해결 코드 (Python)

class Solution:
    def climbStairs(self, n: int) -> int:
        two_steps_before = 1
        one_step_before = 1

        for _ in range(2, n + 1):
            two_steps_before, one_step_before = (
                one_step_before,
                two_steps_before + one_step_before,
            )

        return one_step_before

n개의 계단을 한 번 순회하므로 시간 복잡도는 O(n)이다. 이전 두 상태만 변수로 저장하므로 공간 복잡도는 O(1)이다.

4. 오답 접근과 반례

현재 계단에 도착하는 방법을 매번 모든 이동 순서로 재귀 탐색하면 같은 하위 문제를 반복해서 계산하게 된다. 예를 들어 n = 5를 계산할 때 ways(3)과 ways(2)가 여러 경로에서 반복해서 등장하므로 입력이 커질수록 호출 수가 빠르게 증가한다.

반대로 이동 횟수만 세고 순서를 구분하지 않으면 틀린다. n = 3에서 1 + 2와 2 + 1은 모두 2칸을 이동하지만 서로 다른 방법이므로 각각 따로 세어야 하며, 정답은 3이다.

복사해 실행할 테스트

아래 assert를 풀이 코드와 같은 Python 파일에 붙여 실행하면 점화식의 시작 경계와 공식 예제를 재현할 수 있다.

solver = Solution()
assert solver.climbStairs(1) == 1
assert solver.climbStairs(2) == 2
assert solver.climbStairs(3) == 3
assert solver.climbStairs(45) == 1836311903

5. 공식 예제와 추가 검증

LeetCode 공식 예제 2개를 Python 3.12.4에서 실행했고 기대값과 일치했다.

예제 기대 출력 확인 결과
n = 2 2 통과
n = 3 3 통과

추가 검증 1: 최소 입력

입력: n = 1
기대 출력: 1
확인 결과: 통과
검증 목적: 한 칸을 오르는 유일한 방법 확인

추가 검증 2: 점화식이 처음 적용되는 입력

입력: n = 4
기대 출력: 5
확인 결과: 통과
검증 목적: dp[3]과 dp[2]를 더해 다음 상태를 만드는지 확인

추가 검증 3: 제한에 가까운 입력

입력: n = 45
기대 출력: 1836311903
확인 결과: 통과
검증 목적: 최대 입력에서도 반복 계산 없이 결과를 반환하는지 확인

6. 참고 풀이 비교

  • LeetCode 공식 문제는 1칸 또는 2칸 이동으로 정상에 도달하는 방법의 수를 정의한다.
  • AlgoMonster의 설명은 마지막 이동이 1칸 또는 2칸이라는 관찰에서 동적 계획법 점화식을 도출하는 접근을 설명한다.

재귀에 메모이제이션을 적용하면 같은 점화식을 저장하며 O(n) 시간과 O(n) 공간으로 해결할 수 있다. 이 글에서는 의존하는 상태가 두 개뿐이므로 메모이제이션 배열을 없애고 두 변수만 사용하는 공간 최적화 방식을 선택했다.

마무리

Climbing Stairs는 현재 상태에 도달하는 마지막 선택을 기준으로 점화식을 세우는 동적 계획법의 기본 문제다. 가능한 마지막 이동을 빠짐없이 나누면 피보나치와 같은 점화식이 만들어지고, 이전 두 상태만 보관해 간결하게 구현할 수 있다.

#동적계획법#LeetCode#난이도 3