자바스크립트 코딩테스트 강좌, 세일즈맨의 고민

작성일:

작성자: 코딩전문가

문제 설명

한 세일즈맨이 다양한 도시들을 방문해 상품을 판매하고 있습니다. 이 세일즈맨은 각 도시에서 판매할 수 있는 상품의 가격과 각 도시 간의 이동 비용을 알고 있습니다. 세일즈맨은 목표를 설정하고 이 목표를 달성하는 가장 효율적인 경로를 찾아야 합니다. 즉, 세일즈맨은 각 도시를 한 번만 방문하고, 가능한 한 최대의 수익을 얻으면서 돌아오는 경로를 찾아야 합니다.

입력

입력으로는 도시의 수 n, 각 도시의 판매 가격 prices 배열, 도시 간 이동 비용 costs 2차원 배열이 주어집니다. 가격은 prices[i]로 i번째 도시의 상품 가격을 나타내며, 이동 비용은 costs[i][j]로 i번째 도시에서 j번째 도시로 가는 비용을 나타냅니다.

출력

세일즈맨이 천천히 돌아올 수 있는 최대 이익을 반환해야 합니다.

제한사항

  • 2 ≤ n ≤ 10
  • 0 ≤ prices[i] ≤ 1000
  • 0 ≤ costs[i][j] ≤ 1000

문제 해결 접근법

이 문제는 ‘외판원 문제’와 유사하여, 백트래킹이나 동적 계획법을 사용하여 해결할 수 있습니다. 근본적으로, 세일즈맨이 모든 도시를 방문하고 돌아오는 경로를 최적화하기 위해 가능한 모든 조합을 시도해야 합니다.

1단계: 문제 이해하기

세일즈맨은 모든 도시를 방문해야 하므로, 모든 도시 간의 경로를 탐색하면서 각 경로에서의 아이템 판매 수익과 이동 비용을 고려해야 합니다. 목표는 수익과 비용을 계산하여 최적의 경로를 선택하는 것입니다.

2단계: 알고리즘 설계

이 문제를 해결하기 위해 다음의 단계를 따릅니다:

  • 모든 도시를 시작 도시로 가정하고, 각 도시를 방문하여 가능한 모든 경로를 탐색합니다.
  • 각 경로의 판매 수익과 이동 비용을 계산하여 최적의 수익을 갱신합니다.
  • 모든 도시를 방문한 후 원래 도시로 돌아오는 비용도 포함하여 계산합니다.

3단계: 구현

이제 구현 단계로 넘어가겠습니다. 자바스크립트를 이용하여 세일즈맨의 최대 이익을 찾는 코드를 작성해 보겠습니다.


function maxProfit(n, prices, costs) {
    let maxProfit = -Infinity;

    function backtrack(currentCity, visited, currentProfit) {
        // 모든 도시를 방문했으면 집으로 돌아갑니다.
        if (visited.length === n) {
            const returnCost = costs[currentCity][0]; // 다시 시작 도시로 돌아가는 비용
            const totalProfit = currentProfit - returnCost; // 총 수익 계산
            maxProfit = Math.max(maxProfit, totalProfit);
            return;
        }

        // 각 도시를 방문합니다.
        for (let nextCity = 0; nextCity < n; nextCity++) {
            if (!visited.includes(nextCity)) {
                visited.push(nextCity); // 도시 방문 기록
                const nextProfit = currentProfit + prices[nextCity]; // 다음 도시 수익 계산
                const travelCost = costs[currentCity][nextCity]; // 이동 비용
                backtrack(nextCity, visited, nextProfit - travelCost); // 재귀 호출
                visited.pop(); // 방문 기록 삭제(백트래킹)
            }
        }
    }

    // 0번째 도시에서 시작
    backtrack(0, [0], prices[0]);

    return maxProfit;
}

// 예제 사용
const n = 4;
const prices = [100, 70, 90, 40];
const costs = [
    [0, 10, 15, 20],
    [10, 0, 35, 25],
    [15, 35, 0, 30],
    [20, 25, 30, 0]
];

console.log(maxProfit(n, prices, costs));

4단계: 코드 설명

위의 코드에서 정의한 maxProfit 함수는 다음을 수행합니다:

  • currentCity: 현재 도시를 추적합니다.
  • visited: 현재까지 방문한 도시를 추적합니다.
  • currentProfit: 현재까지의 누적 수익을 추적합니다.

그리고, 우리는 재귀적으로 각 도시를 탐색합니다. 모든 도시를 방문한 후에는 집으로 돌아오는 비용을 계산하여 총 이익을 갱신합니다.

예제 테스트

코드를 실행하면 maxProfit 함수가 최대 이익을 반환합니다. 다양한 입력값으로 실험해보면서 알고리즘의 성능을 확인하는 것이 좋습니다.

결론

이번 강좌에서는 세일즈맨 문제에 대해 알아봤습니다. 코딩테스트에서 자주 나오는 이론적 배경과 구현 방법을 익히는 것이 중요합니다. 다양한 경로를 탐색하며 최적의 이익을 수치적으로 계산하는 과정을 통해 자바스크립트의 강력한 기능을 활용하는 방법을 배웠습니다.

다음 시간에는 다른 알고리즘 문제를 다뤄보겠습니다. 질문이나 피드백이 있다면 댓글로 남겨주세요!