JavaScript로 해결하는 거스름돈 문제 (Greedy Algorithm)

거스름돈 문제란?

"거스름돈 문제"는 주어진 금액을 가장 적은 개수의 동전으로 만들기 위한 전략을 찾는 문제입니다. 이 문제는 "탐욕 알고리즘(Greedy Algorithm)"의 대표적인 예시로 자주 사용되며, ATM 출금, 자동결제 시스템, 화폐 자동 교환기 등 다양한 실무 분야에서도 적용됩니다.

---

문제 정의

• 동전 단위가 담긴 배열 coins[]와 목표 금액 amount가 주어짐
• 목표: 동전을 조합해 총합이 amount가 되도록 하고, 사용한 동전의 개수를 최소화
• 동전은 무한정 사용할 수 있음

예: coins = [500, 100, 50, 10], amount = 1260이면 정답은 동전 6개 (500x2, 100x2, 50x1, 10x1)

---

탐욕 알고리즘의 접근 방식

핵심 전략

"큰 단위 우선"의 전략을 사용합니다. 가장 큰 동전부터 가능한 만큼 사용하고, 남은 금액에 대해서 다음 큰 단위를 반복 적용합니다.

조건

• 탐욕 알고리즘이 항상 최적 해를 보장하려면 동전 단위가 배수 관계여야 합니다.
• 예: [10, 50, 100, 500]은 탐욕 해가 항상 최적, [5, 3]은 그렇지 않음

---

JavaScript 예제 코드

function greedyChange(coins, amount) {
  coins.sort((a, b) => b - a); // 큰 단위부터 정렬
  let count = 0;
  for (let coin of coins) {
    const use = Math.floor(amount / coin); // 현재 단위로 사용할 수 있는 동전 수
    count += use;
    amount -= coin * use; // 남은 금액 갱신
  }
  return amount === 0 ? count : -1; // 정확히 맞으면 개수 반환, 안 맞으면 -1
}

// 예시 실행
console.log(greedyChange([500, 100, 50, 10], 1260)); // 결과: 6
console.log(greedyChange([5, 3], 7)); // 결과: -1 (탐욕으로는 실패)

---

시간 복잡도 분석

• 시간 복잡도: O(n log n) (정렬) + O(n) (반복문) → 총 O(n log n)
• 공간 복잡도: O(1)

---

주의할 점

"탐욕적 선택"은 항상 최적의 해를 보장하지는 않습니다. 가능한 경우의 수가 복잡하거나, 동전 단위가 배수 관계가 아닐 때는 "동적 계획법(DP)" 같은 다른 전략이 필요합니다.

예시: 탐욕으로는 실패하는 경우

• coins = [5, 3], amount = 7
• 탐욕: 5 → 남은 2 → 실패
• 실제 해: 3 + 3 + 1 = 3개 (이 경우 탐욕 실패)

---

실전에서의 활용 사례

• 현금 결제 시스템의 거스름돈 계산
• 게임 아이템 가격 단위 계산
• 티켓 자동 발권기 금액 처리

---

마무리 및 학습 자료

"탐욕 알고리즘"은 문제의 성질을 파악하고 빠르게 근사 해를 구하는 데 매우 유용합니다. 하지만 항상 최적의 결과를 보장하지 않기 때문에 문제 조건에 따라 다른 알고리즘과 병행해서 비교하는 것이 좋습니다.

추천 학습 자료:

• Greedy Algorithm Basics (GeeksforGeeks)
• LeetCode: Coin Change Problems