동전을 적게 쓰려면 큰 액면부터 꺼내면 될까요? 실제 원화 동전과 관계없는 가상 계산이에요. 1단위, 3단위, 4단위 동전은 종류마다 충분히 많고, 금액을 정확히 지불하며 거스름돈은 받지 않아요. 목표는 6단위를 내는 동전 개수를 최소화하는 거예요.
규칙을 명확히 정해 볼까요? 남은 금액 이하인 가장 큰 액면을 하나 고르고, 그 금액을 빼며, 잔액이 0이 될 때까지 반복해요. 처음에는 4를 고르고 잔액 2에는 1, 잔액 1에도 1을 골라요. 결과는 다음과 같아요.
이 알고리즘은 정확한 금액을 만들지만 동전은 세 개예요. 반면 3+3은 같은 6단위를 두 개로 내요. 동전 한 개의 최대 액면이 4라 6을 한 개로 낼 수 없으므로 두 개가 최솟값임도 확인돼요.
지금 가장 큰 것을 고르는 이런 방식을 탐욕법이라고 해요. 하나씩 정한 선택이 전체 목적에 가장 좋은지는 별도 증명이 필요해요. 1단위 동전이 있어 잔액을 계속 줄여 종료하는 것과, 개수가 가장 적다는 것은 다른 성질이에요. 이번 사례는 모든 동전 체계에서 탐욕법이 실패한다는 말이 아니라, 액면 조건을 보지 않고 일반 규칙으로 믿을 수 없다는 반례예요.
참고한 수학 개념: Plus · Maths in a minute: Algorithms.
이 글의 생활 상황과 계산 예시는 수학 이야기에서 새로 구성했습니다.