[알고리즘] 거스름돈 문제: 그리디가 언제나 통할까? (필요충분조건과 증명 스케치)

알고리즘 수업에서 Greedy Algorithm 예시로 접하는 것이 바로 거스름돈 문제(Change-Making Problem) 이다.

"가장 적은 개수의 동전으로 거스름돈을 주려면 어떻게 해야 할까?"

가장 먼저 "가장 큰 단위의 동전부터 낼 수 있는 만큼 낸다"는 그리디(Greedy) 전략을 떠올릴 수 있다. 아주 직관적이며, 한국의 원화 $\{10, 50, 100, 500\}$나 미국의 달러 체계에서는 이 전략이 유효하다.

하지만 동전 체계가 $\{1, 3, 4\}$라면 어떨까?

• 목표 금액: 6
• 그리디 알고리즘: $4 + 1 + 1$ (3개)
• 최적 해: $3 + 3$ (2개)

그렇다면 "언제 그리디 알고리즘이 잘 작동할까?"라는 의문이 생긴다.
하나의 추측은 동전들이 서로 배수 관계인 것이다. 실제 대부분의 통화 시스템의 공통점을 살펴보면 떠올릴 수 있는 추측이며, 서로 배수 관계일 때 그리디 알고리즘은 잘 작동한다.

• 배수 관계라는 것은 구체적으로 10의 배수 50, 50의 배수 100, 100의 배수 500처럼 바로 다음 크기의 동전이 배수인 것이다.
• 그런데 100이 5개 이상 있으면 500으로 대체되므로 100은 최대 4개 있을 수 있다. 마찬가지로 50은 1개, 10은 4개까지 가능하다.
• 그렇다면 500없이 만들 수 있는 금액은 최대 10×4 + 50×1 + 100×4 = 490으로 500을 넘을 수 없다.
• 따라서 500이상 금액을 만드려면 반드시 500을 포함해야하며, 반복적으로 적용하면 500을 최대한 많이 포함해야한다.
• 이것이 결국 그리디 알고리즘의 선택과 일치한다.

하지만 꼭 배수 관계여야하는 것은 아니다.
$\{1, 5, 10, 25\}$에서 25는 10의 배수가 아니지만 그리디 알고리즘이 잘 작동한다.

거스름돈 문제에서 그리디 알고리즘이 잘 작동하는 화폐 시스템을 Canonical Coin System라 부른다. 그런데 이를 판별하기 위한 필요충분조건은 배수 관계처럼 간단히 설명할 수 없다. 그 조건을 살펴보고 직관적으로 이해해보자.

---

1. 문제 정의

$n$가지 동전이 크기 순으로 있다.
$1 = c_1 < c_2 < \dots < c_n$

어떤 금액 $x$를 만들 때, 그리디 알고리즘으로 구한 동전 개수를 $G(x)$, 실제 최적 동전 개수를 $O(x)$라고 하자. 이때, 모든 자연수 $x$에 대해 $G(x) = O(x)$를 만족하는 동전 체계를 Canonical Coin System이라고 한다.

---

2. 어디까지 확인해봐야 할까? (Kozen & Zaks의 정리)

직관적으로 생각해보면, 반례(Counterexample, $G(x) > O(x)$인 경우)가 있는 지 확인할 때 적당한 범위 안에서만 확인하면 될 것 같다. Kozen과 Zaks(1994)이 반례가 존재할 수 있는 상한선을 수학적으로 증명해두었다.

핵심 정리

그리디 알고리즘이 최적해를 보장하기 위한 필요충분조건은 다음과 같다.

"다음 범위 내에 반례 $x$가 존재하지 않는다."
$c_3 + 1 < x < c_n + c_{n-1}$

즉, 이 범위 안에서 반례가 발견되지 않으면, 그보다 큰 어떤 숫자에서도 반례는 나오지 않는다.

증명 스케치 (Intuition)

이 증명은 귀류법(Proof by Contradiction)과 공통 동전 제거(Reduction) 아이디어를 사용한다.

1. 가정: 가장 작은 반례가 $x$이고 $x$가 아주 큰 수라고 가정하자.
2. 논리: $x$가 충분히 크다면, 그리디 알고리즘은 당연히 가장 큰 동전 $c_n$을 포함한다.
3. 모순 유도:
   3-1. 만약 최적 해($O$)에도 $c_n$이 포함되어 있다면 양쪽에서 $c_n$을 하나씩 빼버리면 $x$보다 작은 반례가 나와 모순이다.
   3-2. 만약 최적 해($O$)에 $c_n$이 없다면?
4. 결론: 따라서 가장 작은 반례 $x$의 최적 해에는 가장 큰 동전 $c_n$이 절대 포함될 수 없다.
   • 가장 큰 동전을 쓰지 않고 작은 동전들만으로 합을 구성해야 하므로, $x$가 커지는 데에는 한계가 있다.
   • 그 수학적 한계선이 바로 두 큰 동전의 합인 $c_n + c_{n-1}$ 이다.

3-2.를 생각해보자.
$x$는 아주 크므로($c_n + c_{n-1}$이상) 최적해($O$)의 동전 일부 또는 전체를 선택하여 $c_n$보다 크게 만들 수 있다. 그러한 조합 중 합이 가장 작은 조합을 생각해보자. 그 조합의 합을 $S$라고 하면, $S \le c_n + c_{n-1}$이다. 왜냐하면 동전 하나를 빼면 $c_n$이하이다. 거기에 동전 하나를 더한다면 가장 큰 값이 $c_{n-1}$이므로 $S \le c_n + c_{n-1}$이다.
$x$가 $S$보다 크므로, 가장 작은 반례라고 한 $x$가 $x$ = $S + (x-S)$ 두 부분으로 나누어진다. $S$는 가장 작은 반례 $x$보다 작으므로 그리디 알고리즘으로 최적해를 찾을 수 있고 $S > c_{n}$이므로 $S$의 최적 해는 $c_{n}$을 포함한다. 따라서 $x$ = $S + (x-S)$의 최적 해는 $S$의 그리디 해와 $(x-S)$의 최적 해의 합으로 구할 수 있는데, $S$의 그리디 해에 $c_{n}$이 포함된다. 결국 $x$의 최적 해에 $c_{n}$이 포함되므로 3-2가 일어날 수 없고 반드시 3-1이 된다.

---

3. 더 효율적인 판별법 (Pearson의 알고리즘)

Kozen & Zaks의 정리는 탐색 범위를 획기적으로 줄여주었다. Pearson(2005)은 이를 개선하여 범위 안의 모든 수가 아니라 검사해야하는 후보를 추려서 다항 시간($O(n^3)$) 내에 판별할 수 있는 방법을 제시했다.

핵심 아이디어

반례는 아무 숫자에서나 뜬금없이 튀어나오지 않는다. 그리디 알고리즘이 실수를 범하는 순간은 "작은 동전들을 모아 큰 동전 하나로 바꿀 수 있는 경계" 근처이다.

Pearson은 반례가 될 수 있는 후보군(Test Set)이 두 동전의 합($c_i + c_j$)과 밀접한 관련이 있음을 밝혔다.

예를 들어 $\{1, 3, 4\}$ 시스템에서 $3+3=6$은 $4$보다 크다. 그리디 알고리즘이 $4+1+1$을 선택하게 만들어 최적 해($3+3$)를 깨뜨리는 결정적인 반례 후보가 된다. $3$을 모아서 $4$보다 커지는 경우가 검사할 후보가 된다.

알고리즘 메커니즘

모든 $x$를 다 뒤질 필요 없이, 아래와 같은 형태의 '위험군' 숫자들만 검사하면 된다.

1. 임의의 두 동전 $c_i, c_j$ ($1 \le i \le j < n$)를 선택한다.
2. 두 동전의 합보다 작지만, 그리디 알고리즘으로는 큰 동전을 쓰게 만드는 임계값을 계산한다.
3. 이 소수의 후보군($O(n^2)$개)에 대해서만 $G(x)$와 $O(x)$를 비교해본다.

---

4. 결론 및 참고 문헌

우리가 흔히 사용하는 화폐 시스템은 그리디가 통하지만, 꼭 그렇지만은 않다.

• 동전들이 서로 배수 관계라면 그리디는 항상 성립한다. (충분조건)
• 배수 관계가 아니더라도, $c_n + c_{n-1}$ 미만의 범위에서 반례가 없다면 그리디는 성립한다. (필요충분조건)

References (엄밀한 증명이 궁금하다면)

1. Kozen, D., & Zaks, S. (1994). Optimal Bounds for the Change-Making Problem.
   • 반례가 존재할 수 있는 상한선을 증명한 논문
2. Pearson, D. (2005). A Polynomial-time Algorithm for the Change-Making Problem.
   • 전수 조사가 아닌, $O(n^3)$ 알고리즘으로 판별 가능함을 증명한 논문