[99클럽 코테 스터디] 40일차 TIL - Min Cost Climbing Stairs

오늘의 학습 키워드

</> 동적계획법

공부한 내용 본인의 언어로 정리하기

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        
        // 최소 비용을 저장할 dp 배열
        int[] dp = new int[n + 1];
        
        // 초기 값 설정: 첫 번째와 두 번째 계단에 도달하는 비용은 각각 cost[0], cost[1]
        dp[0] = 0; // 0번째 계단에 서있는 비용은 0
        dp[1] = 0; // 1번째 계단에 서있는 비용도 0
        
        // 각 계단에 도달하는 최소 비용 계산
        for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }
        
        // 최종적으로, dp[n]이 목적지인 계단에 도달하기 위한 최소 비용을 의미
        return dp[n];
    }
}

오늘의 회고

오늘 문제는 계단이 있고, 각 계단마다 그 계단에 오르기 위해 지불해야 하는 비용 cost[i]가 주어진다.
계단은 첫 번째 또는 두 번째 계단에서 시작할 수 있고 한번에 한 계단 또는 두 계단을 올라갈 수 있다.
최종 반환해야할 결과는 맨 꼭대기에 도달할 때 까지 최소한으로 지불해야할 비용을 구하는 것이다.

오늘 문제는 유형을 따라 동적 계획법을 이용하여 풀이를 하였다.
dp[i]를 i번째 계단에 도달하는 데 드는 최소 비용으로 정의하고 비용의 이전 계단 또는 두 계단 전으로 볼 수 있다.
그리고 이 두 값을 비교하여 더 적용 비용을 선택해서 현재 계단의 비용을 더하는 방식이다.

우선 총 계단의 수를 정의해줬다

int n = cost.length;

그리고 각 계단에 도달하는 최소 비용을 저장한다.
그리고 범위초과를 방지하기 위해 배열의 범위를 n+1로 설정해주었다.

int[]dp = new int[n+1];

초기값으로 계단의 시작 비용을 0으로 초기화한다.

dp[0] = 0;
dp[1] = 0;

중요한 각 계단에 도달하는 최소 비용을 계산한다. 한 계단 또는 두 계단을 오를 수 있으므로 두 가지 다 비교해서 낮은 값을 구한다.

for (int i = 2; i <= n; i++) {
            dp[i] = Math.min(dp[i - 1] + cost[i - 1], dp[i - 2] + cost[i - 2]);
        }

최종적으로 계단의 꼭대기에 도달할 때 까지의 최소 비용을 반환한다.

return dp[n];

AI 코드리뷰

현재 코드의 장점

1. 동적 프로그래밍(DP)을 사용하여 문제를 효율적으로 해결합니다.
2. 코드가 간결하고 이해하기 쉽습니다.
3. 배열 크기를 n+1로 설정하여 마지막 계단에 도달하는 비용을 쉽게 계산합니다.

현재 코드의 단점

1. 추가적인 O(n) 공간을 사용합니다 (dp 배열).
2. 모든 계단의 비용을 계산하고 저장하므로, 큰 입력값에 대해 불필요한 메모리를 사용할 수 있습니다.

시간 복잡도

• 시간 복잡도: O(n), 여기서 n은 계단의 수입니다.
• 공간 복잡도: O(n), dp 배열 때문입니다.

개선된 코드 제안

class Solution {
    public int minCostClimbingStairs(int[] cost) {
        int n = cost.length;
        int first = 0, second = 0;
        
        for (int i = 2; i <= n; i++) {
            int current = Math.min(first + cost[i-2], second + cost[i-1]);
            first = second;
            second = current;
        }
        
        return second;
    }
}

개선된 코드의 장점

1. 공간 복잡도가 O(1)로 개선되었습니다. 전체 dp 배열 대신 두 개의 변수만 사용합니다.
2. 여전히 동적 프로그래밍 접근 방식을 유지하면서 메모리 사용을 최적화했습니다.
3. 코드가 더 간결해졌습니다.

개선된 코드의 단점

1. 원래 코드에 비해 약간 더 이해하기 어려울 수 있습니다.
2. 중간 결과를 저장하지 않아 디버깅이 조금 더 어려울 수 있습니다.

시간 복잡도

• 시간 복잡도: O(n), 여전히 모든 계단을 한 번씩 순회합니다.
• 공간 복잡도: O(1), 고정된 수의 변수만 사용합니다.

이 개선된 버전은 원래 솔루션의 로직을 유지하면서 공간 효율성을 크게 향상시켰습니다. 큰 입력값에 대해 더 효율적으로 작동할 것입니다.

---

내일 공부할 것 :

동적계획법 복습

문제

https://leetcode.com/problems/min-cost-climbing-stairs/