자바스크립트 코딩테스트 강좌, 최소 비용 구하기

문제 설명

주어진 비용 배열이 있습니다. 배열의 각 인덱스는 특정 위치에 도달하는 비용이며, 특정 지점에서 시작하여 끝 지점에 도달할 때의 최소 비용을 계산하십시오.

예를 들어, 비용 배열이 [10, 15, 20]이라면, 첫 번째 인덱스(0)에서 시작하여 두 번째 인덱스(1) 또는 세 번째 인덱스(2)까지 가는 최소 비용을 찾아야 합니다. 이 경우, 1 인덱스를 거치는 비용 15가 결정됩니다.

입력

– 비용 배열: cost (1 <= cost.length <= 100)

출력

– 최소 비용인 숫자를 반환합니다.

제한 사항

– 비용은 양의 정수입니다.

해결 과정

이 문제를 해결하기 위해 동적 프로그래밍(Dynamic Programming) 방법을 사용할 것입니다. 이 방법은 이미 계산된 결과를 저장하여 중복 계산을 피하고 효율성을 높이는 기법입니다.

1단계: 문제 이해하기

비용 배열이 주어지면, 우리는 첫 번째 인덱스에서 종료 지점으로 가는 최소 비용을 계산합니다. 각 인덱스에서 다음 인덱스로 가는 비용을 누적하여 전체적인 비용을 계산해야 합니다.

2단계: 동적 프로그래밍 테이블 정의하기

우리는 dp라는 배열을 정의할 것입니다. dp[i]는 인덱스 i까지의 최소 비용을 저장합니다. 첫 번째 인덱스의 비용은 그 자체이므로 dp[0]는 cost[0]로 초기화합니다.

3단계: 초기 상태 설정

초기 상태는 아래와 같이 설정됩니다:

let dp = new Array(cost.length);
dp[0] = cost[0];

4단계: 점화식 구성

점화식은 다음과 같습니다:

dp[i] = cost[i] + Math.min(dp[i - 1], dp[i - 2]);

즉, 현재 인덱스 i에 도달하기 위한 비용은 현재 인덱스의 비용과 이전 두 인덱스(이전 값과 그 이전 값)에서의 최소 비용의 합이 됩니다.

5단계: 전체 코드 작성

function minCost(cost) {
    let n = cost.length;
    if (n === 0) return 0;
    if (n === 1) return cost[0];

    let dp = new Array(n);
    dp[0] = cost[0];
    dp[1] = cost[1];

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

    return Math.min(dp[n - 1], dp[n - 2]);
}

// 사용 예시:
console.log(minCost([10, 15, 20])); // 출력: 15

6단계: 코드 분석

이 코드는 비용 배열의 크기가 1일 때와 0일 때를 처리하는 초기 조건을 포함하고 있습니다. 그 후, 반복문을 통해 각 인덱스에 대해 최소 비용을 계산하며, 마지막에는 최종적으로 최소 비용을 반환합니다.

7단계: 시간 복잡도

시간 복잡도는 O(n)입니다. (n은 비용 배열의 길이). 각 인덱스를 한 번만 조회하므로 효율적입니다.

8단계: 추가 설명

이 문제는 실생활에서도 유용한 알고리즘으로, 길을 찾거나 최단 경로를 구하는 문제에 적용될 수 있습니다. 이러한 원리를 다른 복잡한 문제에 확장하여 활용할 수 있으며, 알고리즘에 대한 이해도를 높이는 데 도움이 됩니다.

© 2023 자바스크립트 코딩테스트 강좌