[LeetCode] - 70. Climbing Stairs

LeetCode는 프로그래밍 문제를 풀며 코딩 실력을 향상할 수 있는 온라인 플랫폼입니다. 다양한 알고리즘 및 데이터 구조 문제를 제공하며, 면접 대비에 유용합니다. 해당 문제는, LeetCode Problems에서 볼 수 있는 난이도 '쉬움 (Easy)' 단계인 "Climbing Stairs" 문제입니다.

--> https://leetcode.com/problems/climbing-stairs/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

---

이 문제는 계단을 오르는 문제로, 꼭대기까지 n개의 계단이 있습니다. 한 번에 1 계단 또는 2 계단 씩 오를 수 있습니다. 각 단계에서 가능한 오르는 방법의 수를 구하는 문제입니다. 예를 들어, n=2일 때는 2가지 방법이 있고, n=3일 때는 3가지 방법이 있습니다. 유명한 DP 문제인데요, 바로 한 번 보시겠습니다 : 

class Solution {
    public int climbStairs(int n) {
        
        int[] dp = new int[n+1];
        dp[0] = 1;
        dp[1] = 1;

        for (int i = 2; i <= n; i++) {
            dp[i] = dp[i-1] + dp[i-2];
        }

        return dp[n];

    }
}

 

제 코드를 간단하게 3 단계로 나눠보자면, 

1. dp 배열 초기화 :
   • dp 배열을 선언하고, 0번째와 1번째 계단에 도달하는 방법의 수를 각각 1로 초기화합니다.
2. 반복문을 통해 동적 계획법 적용 :
   • 2번째 계단부터 n번째 계단까지 반복하며, 각 계단에 도달하는 방법의 수는 이전 두 계단에 도달하는 방법의 수의 합입니다.
3. 결과 반환 :
   • dp 배열의 n번째 요소를 반환합니다. 이는 n번째 계단에 도달하는 방법의 수를 의미합니다.

시간 및 공간 복잡도 :

1. 시간 복잡도 :
   • O(n) : 반복문을 통해 2부터 n까지 순회하므로, 시간 복잡도는 O(n)입니다.
2. 공간 복잡도 :
   • O(n) : dp 배열을 사용하여 n+1개의 요소를 저장하므로, 공간 복잡도는 O(n)입니다.

이 코드는 동적 계획법을 사용하여 효율적으로 계단을 오르는 방법의 수를 계산합니다. 각 단계에서 이전 두 단계의 값을 더하여 현재 단계의 값을 결정하는 방식으로, 피보나치수열과 유사한 구조를 가지고 있습니다.

---

내 코드 Runtime 결과