[2024] Day17. 70. Climbing Stairs

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 1월 17일 (수)
Leetcode daily problem

70. Climbing Stairs

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

Problem

매번 1개의 계단, 혹은 2개의 계단을 오를 수 있다고 가정할 때,
n번째에 위치한 계단의 정상에 도달하기 위해서 얼마나 많은 방법이 있을지 경우의 수를 반환한다.

예를 들면 1번째 계단은 1회 이동 -> 1가지
2번째 계단은 2계단 1회 이동 혹은 1계단 2회 이동 -> 2가지
3번째 계단은 1계단 3번 이동 혹은 2계단 1회/1계단 1회 및 1계단 1회/2계단 1회 -> 3가지 이다.

그렇다면 n번째 위치한 계단을 오를 수 있는 방법은?

Solution

동적 프로그래밍(Dynamic Programming)

해당 문제는 피보나치 수열과 비슷한 방법으로 풀면 된다.
정상 n계로 이루어진 계단을 오를 때 가능한 방법의 수는 이전 계단을 오를 때의 방법의 수, 그 이전 계단을 오를 때의 방법의 수를 더한 값과 같다.
그래서 점화식은 f(n) = f(n-2) + f(n-1) 이 된다.

Code

class Solution:
    def climbStairs(self, n: int) -> int:
        tmp = [0,1,2]
        if n < len(tmp):
            return tmp[n]
        for i in range(3, n+1):
            step = tmp[i-1] + tmp[i-2]
            tmp.append(step)

        return tmp[n]

Complexicity

시간 복잡도

반복문이 계단의 개수 n 만큼 반복하므로 시간 복잡도는 O(n)이다.

공간 복잡도

공간복잡도 또한 n만큼 tmp의 길이가 늘어나고 있어 선형적으로 증가한다. O(n)이다.

---