그리디 알고리즘(Greedy Algorithm)은 최적의 해를 찾기 위해 매 순간마다 가장 적합한 선택을 하는 알고리즘입니다. 전체 문제를 최적화하기 위해서 매 순간 최적이라고 생각되는 선택을 하는 것이며, 이 선택이 항상 전체 문제의 최적의 해를 보장하지는 않습니다. 하지만 그리디 알고리즘을 통해 쉽게 문제를 해결할 수 있는 경우도 많기 때문에 많이 사용됩니다.
문제: 동전 거스름돈
당신은 가게 주인으로, 손님에게 동전으로 거스름돈을 주어야 합니다. 가게에는 다음과 같은 동전들이 있습니다:
- 500원짜리 동전
- 100원짜리 동전
- 50원짜리 동전
- 10원짜리 동전
당신은 손님에게 최적의 동전 개수를 사용하여 거스름돈을 주고 싶습니다. 만약 손님이 1260원의 거스름돈을 요청하면, 당신은 다음과 같이 동전을 줄 수 있습니다:
- 2장 – 500원
- 2장 – 100원
- 1장 – 50원
- 1장 – 10원
즉, 총 6장의 동전을 주게 됩니다. 프로그램의 입출력 형식은 다음과 같습니다:
입력
첫 번째 줄: 거스름돈을 줄 금액 N (1 <= N <= 10,000)
출력
최소 동전 개수
문제 해결 과정
1. 문제 이해
문제를 해결하기 위해 우리는 주어진 금액의 동전 개수를 최소화해야 합니다. 가장 높은 가치의 동전부터 사용하여 남은 금액에 대해 다시 동전을 계산하는 방식으로 접근합니다.
2. 알고리즘 설계
그리디 알고리즘을 적용하여 다음과 같은 단계를 거칩니다:
- 주어진 금액 N을 확인합니다.
- 동전의 가치를 큰 것에서 작은 순서로 정렬합니다.
- 각 동전의 가치를 사용해 나아가면서 금액을 줄여나갑니다.
- 동전이 사용될 때마다 개수를 카운트합니다.
- 남은 금액이 0이 될 때까지 이 과정을 반복합니다.
3. 코드 구현
이제 문제를 해결하기 위한 자바스크립트 코드를 작성해보겠습니다.
function minCoins(N) {
const coins = [500, 100, 50, 10]; // 동전의 가치
let count = 0; // 동전 개수 카운트
for (let i = 0; i < coins.length; i++) {
// 현재 동전의 가치를 N으로 나눠 최대 몇 개를 쓸 수 있는지 계산
count += Math.floor(N / coins[i]);
// 사용한 만큼 N에서 차감
N %= coins[i];
}
return count;
}
// 사용 예
const amount = 1260; // 요청한 거스름돈
console.log(`최소 동전 개수: ${minCoins(amount)}`); // 출력: 6
4. 코드 설명
위의 코드에서:
minCoins함수는 매개변수N을 통해 거스름돈을 입력받습니다.coins배열에는 동전의 가치를 큰 것부터 나열했습니다.- for 루프를 통해 각 동전의 가치를 확인하며
Math.floor(N / coins[i])를 사용하여 사용 가능한 동전 개수를 계산합니다. - 동전이 사용된 후 남은 금액은
N %= coins[i]로 업데이트합니다. - 최종적으로 동전의 개수를 반환합니다.
5. 동작 확인
이제 위의 코드를 통해 여러 가지 테스트 케이스를 실행하여 동작을 확인합니다. 다양한 입력을 테스트해 보겠습니다.
console.log(minCoins(5000)); // 출력: 10
console.log(minCoins(1000)); // 출력: 2
console.log(minCoins(560)); // 출력: 2
console.log(minCoins(9999)); // 출력: 특정값
결론
이번 강좌에서는 그리디 알고리즘을 사용하여 동전 거스름돈 문제를 해결했습니다. 그리디 알고리즘은 단순한 문제에서 매우 유용하게 활용되며, 동전이나 배낭 문제와 같은 다양한 문제를 해결하는 데 기여합니다. 앞으로도 다양한 그리디 알고리즘 문제를 해결해보며 더 많은 경험을 쌓아보시기 바랍니다.