[LeetCode] 70. Climbing Stairs

말하는 감자·2024년 11월 19일

dynamic programming leetcode python 동적 프로그래밍 리트코드 코딩테스트 코딩테스트 준비 파이썬

LeetCode

목록 보기

12/32

오늘 문제는 Dynamic Programming 알고리즘을 활용하는 문제입니다. 아직 저에겐 정말 DP가 어려운데요! 한 번 풀어보았습니다.

1. 오늘의 학습 키워드

Dynamic Programming
Top-Down
Bottom-Up

2. 문제: 70. Climbing Stairs

단계: Easy
주제: Math, Dynamic Programming, Memoization
출처: https://leetcode.com/problems/climbing-stairs/?envType=problem-list-v2&envId=dynamic-programming&difficulty=EASY

Description

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:

Input: n = 2
Output: 2
Explanation: There are two ways to climb to the top.
1. 1 step + 1 step
2. 2 steps

Example 2:

Input: n = 3
Output: 3
Explanation: There are three ways to climb to the top.
1. 1 step + 1 step + 1 step
2. 1 step + 2 steps
3. 2 steps + 1 step

Constraints:

1 <= n <= 45

3. 문제 풀이

계단을 오르는 데 있어서 이 계단의 꼭대기에 도착하려면 n개의 steps만큼 올라가야 합니다. 한 번 올라갈 때마다 1step 또는 2steps 올라갈 수 있습니다. 꼭대기에 도달하는 방법의 개수는 총 몇가지인지 구하는 문제입니다.

n개를 달성하는 데 1과 2 step만으로 달성하는 문제입니다. 차근차근 살펴보겠습니다.

Step1. 문제 이해하기

Input:
- n step이 입력으로 들어갑니다. 이것은 1과 45사이입니다.
Output:
- 꼭대기에 도달하는 방법의 개수를 반환합니다.

Input과 Ouput이 매우 직관적인 문제입니다. 하지만 입력과 반환값만을 가지고 어떤 알고리즘, 어떤 방식으로 구할지는 떠오르지가 않네요.. 문제 분석을 조금 더 해보겠습니다.

Step2. 문제 분석하기

문제를 분석하며, 주어진 계단 문제의 규칙과 구조를 파악해보겠습니다.

완전 탐색 접근

가장 먼저 생각해볼 수 있는 방법은 완전 탐색입니다. 이는 가능한 모든 경우를 하나하나 나열하여 전체 방법의 개수를 확인하는 방식입니다. 아래는 간단한 예시입니다:

n = 2 (2가지 방법)
- 1 step + 1 step
- 2 steps
n = 3 (3가지 방법)
- 1 step + 1 step + 1 step
- 1 step + 2 steps
- 2 steps + 1 step
n = 4 (5가지 방법)
- 1 step + 1 step + 1 step + 1 step
- 1 step + 2 steps + 1 step
- 2 steps + 1 step + 1 step
- 1 step + 1 step + 2 steps
- 2 steps + 2 steps
n = 5 (8가지 방법)
- 1 step + 1 step + 1 step + 1 step + 1 step
- 1 step + 2 steps + 1 step + 1 step
- 2 steps + 1 step + 1 step + 1 step
- 1 step + 1 step + 2 steps + 1 step
- 2 steps + 2 steps + 1 step
- 2 steps + 1 step + 2 steps
- 1 step + 2 steps + 2 steps
- 1 step + 1 step + 1 step + 2 steps

규칙 파악

위의 예시를 통해 규칙을 찾아보겠습니다.

1. 현재 계단 수 n은 이전 두 계단(n-1, n-2)의 합

각 계단에 도달하는 방법의 수는 다음과 같습니다:

n = 1: 경우의 수는 1
n = 2: 경우의 수는 2
n = 3: 경우의 수는 3
n = 4: 경우의 수는 5
n = 5: 경우의 수는 8

여기서 n번째 경우의 수는 (n-1)번째 경우의 수 + (n-2)번째 경우의 수입니다.

즉, 점화식으로 표현하면:
$f(n) = f(n-1) + f(n-2)$

이는 피보나치 수열과 동일한 구조를 가집니다.

2. 계단의 오름 규칙

계단은 한 번에 1칸 또는 2칸씩 오를 수 있습니다. 이는 다음과 같은 특징을 제공합니다:

f(n-1): 마지막에 한 칸 올라왔을 경우의 경우의 수
f(n-2): 마지막에 두 칸 올라왔을 경우의 경우의 수

따라서, 두 가지 경우의 수를 더하면 총 경우의 수를 얻을 수 있습니다:

$f(n) = f(n-1) + f(n-2)$

초기 조건

점화식을 구현하려면 기본적으로 초기 조건이 필요합니다. 문제에 따라 다음 두 가지가 정의됩니다:

f(1) = 1: 계단이 1칸인 경우, 방법은 한 가지 (1칸 오르기)
f(2) = 2: 계단이 2칸인 경우, 방법은 두 가지 (1칸+1칸 or 2칸)

왜 DP를 사용할까?

만약 n이 매우 커질 경우, 완전 탐색으로 모든 경우를 계산하면 비효율적입니다. 특히 중복된 계산이 많아지기 때문입니다.

이를 해결하기 위해 Dynamic Programming (DP)을 활용하여 중복 계산을 줄이고 효율적으로 문제를 해결할 수 있습니다.

Top-Down (재귀 + 메모이제이션) 재귀적으로 문제를 쪼개며 이미 계산된 값을 저장하여 중복 계산을 방지합니다.
Bottom-Up (반복문) 작은 문제에서 큰 문제로 확장하며, 배열을 사용해 이전 결과를 저장해 점진적으로 계산합니다.

이제 점화식과 초기 조건을 바탕으로 DP 알고리즘을 설계해보겠습니다.

저는 DP 문제를 풀면 Top-Down식으로 문제를 먼저 푸는 연습을 하려고 합니다. 왜냐하면 재귀적으로 구현하는 것은 다른 곳에서도 정말 많이 쓰이기 때문에 재귀가 익숙해지기 위해 Top-Down식으로 먼저 풀어보려는 연습을 하고 있습니다. 따라서 Top-Down식으로 먼저 구현을 진행해보도록 하겠습니다.

Step3. 코드 설계

Top-Down 방식은 문제를 가장 큰 상태로 정의하고, 이를 재귀적으로 쪼개서 해결하는 방식입니다. 이를 구현하기 위해 다음을 고려합니다:

1. Base Case 설정

Base Case는 가장 작은 경우를 정의해야 합니다. 문제에서 n이 다음과 같을 때 반환값은 다음과 같습니다:

n = 0: 계단을 오를 필요가 없으므로 방법은 0개 → 반환값: 0
- 제약 조건에서 n은 1보다 큽니다. 하지만 Top-down은 재귀 방식이므로 n이 0인 경우도 나올 수 있습니다. 따라서 반환값 0으로 설정합니다.
n = 1: 계단이 한 칸인 경우, 방법은 한 가지 (1칸 오르기) → 반환값: 1
n = 2: 계단이 두 칸인 경우, 방법은 두 가지 (1칸 + 1칸 또는 2칸) → 반환값: 2

2. 재귀 함수 정의

점화식 f(n) = f(n-1) + f(n-2)을 사용합니다:

f(n-1): 한 칸 전에서 올라오는 경우의 수
f(n-2): 두 칸 전에서 올라오는 경우의 수

3. Memoization 사용

재귀 함수의 중복 계산을 방지하기 위해 결과를 저장하는 메모이제이션을 사용합니다. dict 또는 list를 활용해 계산된 값을 저장합니다:

이미 계산된 값이 있다면 메모에서 값을 반환
계산되지 않은 경우, 점화식을 통해 값을 계산하고 메모에 저장

그럼 Bottom-up방식은 어떻게 하면 될까요?

비슷하지만, 재귀 함수가 아닌 반복문을 통해서 구현하면 될 것 같습니다.

그럼 코드 구현을 진행해보겠습니다.

Step4. 코드 구현

Top-Down

class Solution(object):
    # Top-down
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        
        memo = {}
        def dp(n):
            if n == 0 or n == 1:
                return 1
            if n in memo:
                return memo[n]
            memo[n] = dp(n - 1) + dp(n - 2)
            
            return memo[n]
        
        return dp(n)

코드 설명:

Top-Down 방식은 재귀적으로 문제를 쪼개어 해결하며, 중복 계산을 방지하기 위해 메모이제이션을 활용합니다.

Base Case:
- n == 0 또는 n == 1일 경우, 방법의 수는 1입니다.
점화식 구현:
- dp(n) = dp(n-1) + dp(n-2)
- n-1은 한 칸 올라가는 경우, n-2는 두 칸 올라가는 경우를 나타냅니다.
Memoization:
- 중복 계산을 방지하기 위해 이미 계산된 값을 memo 딕셔너리에 저장합니다.
- 값이 메모에 있으면 바로 반환하여 불필요한 계산을 방지합니다.

시간 복잡도: $O(n)$

메모이제이션을 통해 각 계단에 대해 한 번만 계산합니다.

결과:
https://leetcode.com/problems/climbing-stairs/submissions/1457279529

Bottom-Up

class Solution(object):
# Bottom-Up
    def climbStairs(self, n):
        """
        :type n: int
        :rtype: int
        """
        case = [1] * (n + 1)
        
        for i in range(2,n+1):
            case[i] = case[i -1] + case[i - 2]
            
        return case[n]

코드 설명:

Bottom-Up 방식은 작은 문제부터 점진적으로 큰 문제를 해결하는 방식으로, 반복문과 배열을 사용합니다.

초기 값 설정:
- 계단이 1칸인 경우, 방법의 수는 1 (case[1] = 1).
- 계단이 2칸인 경우, 방법의 수는 2 (case[2] = 2).
점화식 구현:
- 반복문을 통해 case[i] = case[i-1] + case[i-2]를 계산합니다.
- 이전 두 계단(i-1, i-2)의 값을 더해 현재 계단의 방법 수를 구합니다.
결과 반환:
- case[n]에 저장된 값을 반환합니다.