문제 소개
이번 글에서는 JavaScript로 동전 교환(Coin Change) 문제를 해결하는 방법을 알아보겠습니다.
함수의 첫 번째 인자는 배열 arr입니다. 이 배열은 우리가 사용할 수 있는 동전의 종류(액면가)를 나타냅니다. 예를 들어 [1, 2, 5]라면 1원, 2원, 5원짜리 동전을 각각 무제한으로 사용할 수 있다는 의미입니다.
두 번째 인자는 숫자 amount로, 만들고자 하는 목표 금액을 뜻합니다. 함수는 이 금액을 정확히 맞추기 위해 필요한 최소 동전 개수를 반환해야 합니다.
만약 어떤 조합으로도 해당 금액을 만들 수 없다면 -1을 반환하도록 합니다.
예시 입력과 출력
입력이 다음과 같다고 가정해 보겠습니다.
const arr = [1, 2, 5]; const amount = 17;
이때 기대하는 출력은 다음과 같습니다.
const output = 4;
출력 설명
17이라는 금액은 5원짜리 동전 3개와 2원짜리 동전 1개, 즉 총 4개의 동전으로 만들 수 있기 때문입니다. 이보다 적은 수의 동전으로 17을 만드는 방법은 없습니다.
풀이 접근법: 동적 계획법(DP)
이 문제는 그리디(Greedy) 방식으로 풀 경우 항상 최적해를 보장할 수 없기 때문에, 동적 계획법(Dynamic Programming)을 사용하는 것이 안전합니다.
핵심 아이디어는 다음과 같습니다.
- 0부터 amount까지 각 금액을 만들 때 필요한 최소 동전 개수를 순차적으로 계산하여 배열에 저장합니다.
- 특정 금액
i를 만들 때는, 사용 가능한 각 동전c에 대해changes[i - c]값에 1을 더한 것 중 최솟값을 선택합니다. - 만들 수 없는 금액은 매우 큰 값(여기서는
Math.pow(2, 31) - 1)로 초기화하여, 나중에 도달 불가능 여부를 판별합니다.
구현 코드
전체 코드는 다음과 같습니다.
const arr = [1, 2, 5];
const amount = 17;
const minCoins = (arr = [], amount = 1) => {
// changes[i] = i 금액을 만들기 위한 최소 동전 개수
const changes = [];
changes[0] = 0; // 0원을 만드는 데 필요한 동전은 0개
while (changes.length <= amount) {
// 일단 도달 불가능한 큰 값으로 초기화
let change = Math.pow(2, 31) - 1;
for (let i = 0; i < arr.length; i++) {
// 현재 금액에서 동전 값을 뺀 결과가 음수면 스킵
if (changes.length - arr[i] < 0) {
continue;
}
change = Math.min(change, 1 + changes[changes.length - arr[i]]);
}
changes.push(change);
}
// 끝까지 도달하지 못했다면 -1 반환
return changes[amount] === Math.pow(2, 31) - 1 ? -1 : changes[amount];
};
console.log(minCoins(arr, amount));실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
4
코드 설명
changes[0] = 0: 금액 0을 만드는 데는 동전이 하나도 필요하지 않으므로 기본값으로 0을 설정합니다.while루프는changes배열의 길이가amount + 1이 될 때까지 반복하며, 즉 0부터 목표 금액까지 모든 경우를 계산합니다.- 내부
for루프에서는 각 동전 종류를 시도해 보며, 현재 금액에서 해당 동전을 하나 사용했을 때의 최소 개수를 갱신합니다. - 마지막에
changes[amount]가 여전히 초기화용 큰 값이라면 해당 금액을 만들 수 없다는 의미이므로-1을 반환합니다.
시간 복잡도
이 알고리즘의 시간 복잡도는 O(amount × arr.length)입니다. 목표 금액만큼 순회하면서 매 단계마다 동전 종류 수만큼 비교하기 때문입니다. 공간 복잡도는 금액별 결과를 저장하는 배열 때문에 O(amount)입니다.