Climbing Stairs | 알고달레

LeetCode의 Climbing Stairs 문제를 함께 풀어보도록 하겠습니다.

문제

계단을 한 번에 1칸이나 2칸을 올라갈 수 있을 때, n 칸의 높이의 계단을 올라기가 위한 방법이 총 몇가지인지 구하라.

예제 1

입력

n = 2

결과

예제 2

입력

n = 3

결과

풀이 1

”천리길도 한걸음부터”라는 말처럼 이 문제도 차근차근 생각해보면 방법을 찾을 수 있겠죠? 🙂

먼저 계단의 1번째 칸에 오르는 방법은 몇가지 일까요? 당연히 1가지 밖에 없겠죠? 그럼 계단의 2번째 칸에 오르는 방법은 몇가지 일까요? 한 번에 2칸을 올라갈 수도 있고, 두 번에 걸쳐 1칸씩 올라갈 수도 있으니, 2가지 방법이 있습니다. 그럼 계단의 3번째 칸에 오르는 방법은 몇가지 일까요??

방법을 일일이 하나씩 셀 수도 있지만 만약에 10번째, 100번째 칸을 오르는 방법을 일일이 세려면 너무도 많은 시간과 노력이 필요하겠죠? 사실 3번째 칸에 오르는 방법의 개수는 2번째 칸에 오르는 방법과 1번째 칸에 오르는 방법을 더하면 간단하게 구할 수 있습니다. 왜 일까요? 계단을 한 번에 최대 2칸 밖에 올라갈 수 없으므로, 3번째 칸에 발을 딛기 위해서는 바로 아래 칸인 2번째 칸이나 적어도 1번째 칸에 반드시 먼저 올라와있어야 하기 때문입니다. 즉, n 칸에 발을 딛기위해서는 그 전에 n - 1 칸이나 n - 2 칸까지 올라와왔어야 합니다.

이를 일반화해보면 다음과 같은 공식을 얻을 수 있습니다.

(n 번째 칸에 오르는 방법의 개수) = (n-1 번째 칸에 오르는 방법의 개수) + (n-2 번째 칸에 오르는 방법의 개수)

이를 위해서는 계단의 낮은 칸에 올라기기 위해 구해놓은 방법의 개수를 저장해두었다가 높은 칸에 올라가기 위한 방법의 개수를 구할 때 재활용해야하는데요. 이럴 때 흔히 사용하는 코딩 테크닉이 바로 동적 계획법(Dynamic Programming)입니다.

우선 1번째 칸에 오르는 방법의 개수와 두 번째 칸에 오르는 방법을 저장해둔 dp라는 해시 테이블(Hash Table)에 저장해둡니다. 그리고 3번째 칸을 오르는 방법부터는 루프를 돌면서 기존에 해시 테이블에 저장해놓은 값을 이용해서 계산하고 다음 단계를 위해서 그 결과 값을 다시 해시 테이블 저장합니다.

이 알고리즘을 코드로 작성해보겠습니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        dp = {1: 1, 2: 2}
        for i in range(3, n + 1):
            dp[i] = dp[i - 1] + dp[i - 2]
        return dp[n]

이 알고리즘의 시간 복잡도와 공간 복잡도는 모두 O(n)입니다. 루프를 한 번만 돌고 있고, 해시 테이블의 크기는 계단에 높이에 비례하기 때문입니다.

풀이 2

위 알고리즘은 메모리 사용량 측면에서 개선의 여지가 보이는데요. 바로 계단에 오르는 방법의 개수를 굳이 1번째 칸부터 n번째 칸까지 모두 저장할 필요는 없다는 것입니다.

예를 들어, 1번째 칸에 오르는 방법의 개수는 3번째 칸에 오르는 방법의 개수를 구한 이 후로 그 보다 높은 칸에서는 사용할 일이 없습니다. 마찬가지로 2번째 칸에 오르는 방법의 개수는 4번째 칸에 오르는 방법의 개수를 구한 이 후로는 쓸모가 없어집니다.

따라서, 바로 아래 칸, 그리고 바로 아래 아래 칸에 오르는 방법의 개수만 저장하면 된다는 것이죠. 즉, 해시 테이블 대신에 단 2개의 변수만 있으면 구현이 가능해집니다.

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        pre, cur = 1, 2
        for _ in range(n - 2):
            pre, cur = cur, pre + cur
        return cur

이렇게 알고리즘을 최적화해주면 공간 복잡도를 O(1)로 내릴 수 있습니다. 처음에 작성한 코드도 나쁘지는 않지만 이렇게 추가적으로 최적화까지 해주면 코딩 시험에서 더 좋은 결과를 얻을 수 있을 것입니다.

풀이 3

위 알고리즘은 계단을 맨 아래부터 위로 올라가면서 계산을 하는데요. 반대로 계단의 꼭대기부터 아래로 거꾸로 거슬러내려가보면 어떨까요?

바로 재귀 알고리즘을 이용하면 가능한데요!

예를 들어, 5칸으로 된 계단의 꼭대기에 오르는 과정을 재귀 트리로 나타내면 다음과 같습니다.

- 5번째 칸에 오르는 방법의 개수: 5 + 3 = 8
  - 4번째 칸에 오르는 방법의 개수: 3 + 2 = 5
    - 3번째 칸에 오르는 방법의 개수: 2 + 1 = 3
      - 2번째 칸에 오르는 방법의 개수: 2
      - 1번째 칸에 오르는 방법의 개수: 1
    - 2번째 칸에 오르는 방법의 개수: 2
  - 3번째 칸에 오르는 방법의 개수: 2 + 1 = 3
      - 2번째 칸에 오르는 방법의 개수: 2
      - 1번째 칸에 오르는 방법의 개수: 1

그럼, 이 재귀 알고리즘을 그대로 구현해볼까요?

class Solution:
    def climbStairs(self, n: int) -> int:
        if n < 3:
            return n
        return self.climbStairs(n - 1) + self.climbStairs(n - 2)

이 알고리즘의 복잡도는 어떻게 될까요? 함수를 호출할 때 마다 새로운 2개의 함수가 호출이 되기 구조이므로 시간 복잡도와 공간 복잡도가 모두 O(2^n)이 되네요. 🙈

풀이 4

위 재귀 트리를 보면 5번째 칸에 오르는 방법을 개수를 구하기 위해서 3번째 칸에 오르는 방법의 개수를 2번 계산하고 있는 것을 알 수 있습니다. 따라서 이러한 중복 계산을 제거하면 위 재귀 알고리즘의 성능을 비약적으로 향상시킬 수 있을 것입니다.

중복 계산을 줄이는 목적으로 흔히 사용되는 성능 최적화 기법인 메모이제이션(memoization)을 이용해서 코드를 재작성해볼께요.

class Solution:
    def climbStairs(self, n: int, memo: dict = {}) -> int:
        if n not in memo:
            if n < 3:
                return n
            memo[n] = self.climbStairs(n - 1) + self.climbStairs(n - 2)
        return memo[n]

이렇게 중복 계산을 없애면 이 알고리즘의 시간/공간 복잡도는 O(n)으로 떨어지게 됩니다. 🙊

마치면서

Climbing Stairs 문제를 풀면서 발견한 흥미로운 사실은 풀이 방법이 유명한 알고리즘은 피보나치(Fibonacci) 알고리즘과 거의 동일하다는 것입니다. 알고달레에서 피보나치 알고리즘에 대해서도 상세하게 다루고 있으니 함께 참고해보시면 좋을 것 같네요.