그리디 알고리즘 (1): 거스름돈 문제 (Coin Change Problem)

1. 거스름돈 문제란?

거스름돈 문제(Coin Change Problem)는 최소한의 동전 개수로 특정 금액을 거슬러 주는 문제다. 일반적으로 그리디 알고리즘(Greedy Algorithm)을 활용하여 해결할 수 있으며, 일부 경우에는 동적 계획법(Dynamic Programming)이 필요할 수도 있다.

1.1 문제 정의

• 동전의 종류가 주어졌을 때, 최소 개수의 동전을 사용하여 특정 금액을 만들기
• 일반적인 화폐 단위에서는 그리디 알고리즘이 최적해를 보장
• 특정 동전 조합에서는 최적해가 보장되지 않을 수 있음

1.2 거스름돈 문제의 특징

• 탐욕적 선택 속성(Greedy Choice Property): 가장 큰 단위의 동전부터 선택
• 최적 부분 구조(Optimal Substructure): 부분 문제의 최적해가 전체 문제의 최적해로 이어짐 (일부 경우 제외)

2. 거스름돈 문제의 동작 원리

거스름돈 문제는 다음과 같은 절차로 해결된다:

1. 동전 단위 내림차순 정렬: 큰 단위의 동전부터 선택
2. 가장 큰 동전부터 사용: 현재 남은 금액에서 가능한 한 많이 사용
3. 남은 금액 갱신: 사용한 동전 수를 기록하고 남은 금액을 줄임
4. 금액이 0이 될 때까지 반복

3. 거스름돈 문제의 예제

3.1 예제 설명

예를 들어, 거슬러 줄 금액이 1260원이고 사용할 수 있는 동전이 500원, 100원, 50원, 10원이라고 하자.

그리디 알고리즘을 적용하면 다음과 같다:

1. 500원 동전 → 2개 사용 (남은 금액: 260원)
2. 100원 동전 → 2개 사용 (남은 금액: 60원)
3. 50원 동전 → 1개 사용 (남은 금액: 10원)
4. 10원 동전 → 1개 사용 (남은 금액: 0원)

최소 동전 개수: 6개

3.2 거스름돈 문제의 구현 (Java)

import java.util.*;

public class CoinChange {
    public static void main(String[] args) {
        int[] coins = {500, 100, 50, 10}; // 동전 단위 (내림차순 정렬)
        int amount = 1260; // 거스름돈
        int count = 0;

        for (int coin : coins) {
            count += amount / coin; // 해당 동전 개수 추가
            amount %= coin; // 남은 금액 갱신
        }

        System.out.println("필요한 동전의 최소 개수: " + count);
    }
}

4. 거스름돈 문제의 성능 분석

4.1 시간 복잡도

• O(n) (n: 동전 종류 수)
• 반복문을 한 번만 실행하므로 빠르게 동작

4.2 공간 복잡도

• O(1) (추가적인 메모리 사용 없음)

5. 거스름돈 문제의 장점과 단점

5.1 장점

• 빠른 계산: 선형 시간 내에 해결 가능
• 단순한 구현: 직관적인 방법으로 해결 가능
• 실제 화폐 단위에서 유용: 대부분의 통화 시스템에서 최적해 보장

5.2 단점

• 일부 동전 조합에서는 최적해가 보장되지 않음
  • 예를 들어, 동전 단위가 {1, 3, 4}이고 거슬러 줄 금액이 6일 때,
    • 그리디 방식: 4 + 1 + 1 = 3개
    • 최적해: 3 + 3 = 2개
  • 이 경우 동적 계획법이 필요함

6. 거스름돈 문제의 활용 사례

• ATM 및 자동판매기: 최소한의 동전 또는 지폐 개수로 거스름돈 제공
• 교통카드 시스템: 잔액 반환 시 효율적인 화폐 사용
• 기업 회계 시스템: 가장 적은 금액의 지출로 비용 계산

7. 결론

거스름돈 문제는 그리디 알고리즘을 활용하여 빠르게 해결할 수 있는 대표적인 문제이다. 대부분의 경우 최적해를 보장하지만, 일부 동전 조합에서는 동적 계획법을 적용해야 할 수도 있다. 문제의 조건을 분석하여 적절한 알고리즘을 선택하는 것이 중요하다.