탐욕 알고리즘: 큰 동전 선택과 반례로 확인하는 최적성

탐욕 알고리즘은 지금 가장 좋아 보이는 선택을 확정합니다. 큰 동전부터 고르는 규칙이 항상 동전 수를 최소로 만드는 것은 아니므로, 적용 조건의 증명과 작은 반례 확인이 필요합니다.

선수 지식: 정수 나눗셈·나머지·배열 정렬·최솟값 비교

• 선택 기준과 남은 상태를 분리하기
• 동전 수 최소화의 반례 설명하기
• 만들 수 없는 나머지를 결과에 보존하기

선택한 개수와 남은 금액을 함께 갱신합니다

동전 종류마다 개수가 무한히 있고, 목표 금액을 정확히 만드는 데 쓴 동전 수를 줄인다고 하겠습니다. 가장 큰 동전부터 가능한 만큼 고르는 규칙은 이해하기 쉽습니다. 예제 함수는 양의 안전한 정수인 동전 값을 중복 제거 후 내림차순으로 정렬합니다. 현재 동전 값이 c이고 남은 금액이 r이면 floor(r/c)개를 선택하고 그만큼의 금액을 r에서 뺍니다. 동전을 한 개씩 빼는 반복보다 상태 변화가 명확하게 드러납니다.

중요한 상태는 “이미 선택한 동전의 합 + 남은 금액 = 원래 목표”입니다. 각 단계에서 이 등식은 유지되며, 작은 동전으로 넘어간 뒤 큰 동전 선택을 다시 검토하지 않습니다. 이것이 탐욕적인 결정입니다. 반환값에는 종류별 개수, 전체 개수, 남은 금액을 모두 담습니다. 선택이 끝났다고 해서 목표를 정확히 만들었다는 뜻은 아니므로 나머지도 함께 읽어야 합니다.

1·3·4로 6을 만들면 큰 동전부터 고르기가 실패합니다

동전 값이 1, 3, 4이고 목표가 6이면 탐욕 선택은 4를 먼저 고릅니다. 남은 2에서는 3을 쓸 수 없으므로 1을 두 개 고릅니다. 총 세 개로 목표 금액을 정확히 만들지만, 3+3이면 두 개로 충분합니다. 따라서 “합이 맞는다”는 실행 가능성과 “개수가 가장 적다”는 최적성은 서로 다른 주장입니다. 한 가지 반례만 있어도 모든 동전 체계에 대한 일반적인 최적성 주장은 성립하지 않습니다.

이 반례를 통해 마지막 동전을 고르는 부분이 아니라 첫 결정 자체를 살펴볼 수 있습니다. 4를 먼저 확정하면 이후에 아무리 잘 골라도 3+3으로 돌아갈 수 없습니다. 작은 입력에서 가능한 조합을 열거하거나 동적 계획법으로 최소 개수를 계산하면 탐욕 규칙의 실패를 찾는 데 도움이 됩니다. 몇 개의 입력에서 맞았다는 사실만으로 모든 금액에 대한 증명이 되지는 않습니다.

좋아 보이는 선택을 최적해로 바꿀 수 있는지 묻습니다

탐욕 규칙을 쓰려면 어떤 최적해가 현재의 선택을 포함하도록 바뀔 수 있는지 설명해야 합니다. 예를 들어 각 큰 동전이 바로 아래 동전의 정수 배수인 체계에서는 작은 동전 여러 개를 큰 동전 한 개로 교환하면 개수가 늘지 않는다는 방향으로 증명을 시작할 수 있습니다. 이런 교환을 반복하여 큰 동전부터 사용하는 최적해가 있음을 보이는 것입니다. 특정 화폐의 이름이나 익숙함 자체가 증명의 근거는 아닙니다.

첨부 예시와 같은 500·100·50·10에서는 위 배수 관계를 확인할 수 있고, 2380은 500원 4개, 100원 3개, 50원 1개, 10원 3개로 나뉩니다. 합은 2380이고 개수는 11개입니다. 목표가 10의 배수가 아니면 이 동전들로는 정확히 만들 수 없다는 조건도 함께 따릅니다. 동전마다 사용 가능한 개수가 제한되거나 종류별 비용이 달라지면 다른 문제가 되므로 같은 증명을 그대로 적용하지 않습니다.

나머지와 입력 범위를 결과의 일부로 봅니다

동전 4와 6으로 금액 5를 처리하면 함수는 4 한 개를 고르고 나머지 1을 반환합니다. 이 결과를 성공한 거스름돈으로 출력하면 안 됩니다. 더 나아가 동전 3과 4로 금액 6을 처리하면 탐욕의 나머지는 2이지만 3+3이라는 해가 있습니다. 따라서 나머지가 남았다는 결과도 “이 탐욕 선택으로 완성하지 못했다”는 뜻이며, 모든 조합이 불가능하다는 판정은 아닙니다.

동전 값 0은 금액을 줄이지 못하고 음수는 의미를 뒤집으므로 거절합니다. 소수 금액도 이 정수 동전 계약에 포함되지 않습니다. 목표 0은 아무 동전도 고르지 않아 개수와 나머지가 모두 0입니다. 입력 종류 수가 K이면 중복 제거와 정렬 후 한 번씩 계산하므로 보통 비교 정렬 비용을 O(K log K), 결과와 정렬 복사 공간을 O(K)로 셉니다. 실제로 선택한 동전 수만큼 배열을 늘리지 않으므로 큰 금액을 출력 목록으로 펼치는 비용은 들지 않습니다.

전체 코드와 직접 실행

개념을 읽었다면 아래 예제를 직접 실행하며 상태 변화를 확인할 수 있습니다.

function greedyCoins(denominations, amount) {
  if (!Array.isArray(denominations)) throw new TypeError('동전 배열이 필요합니다.');
  for (const value of denominations) {
    if (!Number.isSafeInteger(value) || value <= 0) {
      throw new RangeError('동전 값은 양의 안전한 정수여야 합니다.');
    }
  }
  if (!Number.isSafeInteger(amount) || amount < 0) {
    throw new RangeError('금액은 0 이상의 안전한 정수여야 합니다.');
  }
  const values = [...new Set(denominations)].sort((a,b) => b-a);
  let remainder = amount;
  let count = 0;
  const coins = values.map(value => {
    const used = Math.floor(remainder/value);
    remainder -= used*value;
    count += used;
    return { value, count: used };
  });
  return { coins, count, remainder };
}

console.log(JSON.stringify(greedyCoins([1,3,4],6)));
console.log('대안: 3 + 3 = 6, 동전 2개');
console.log(JSON.stringify(greedyCoins([4,6],5)));

node algorithm-greedy-coin-counterexample.mjs

{"coins":[{"value":4,"count":1},{"value":3,"count":0},{"value":1,"count":2}],"count":3,"remainder":0}
대안: 3 + 3 = 6, 동전 2개
{"coins":[{"value":6,"count":0},{"value":4,"count":1}],"count":1,"remainder":1}

비용과 적용 범위

동전 입력 종류 K개에 대해 비교 정렬을 O(K log K)로 세면 전체 시간 O(K log K), 결과와 정렬 복사 공간 O(K)입니다. 무한히 쓸 수 있는 양의 안전한 정수 동전·0 이상의 안전한 정수 금액을 다루며, 일반 동전 체계의 최적성이나 해 존재 여부를 보장하지 않습니다.

직접 확인해 보기

동전 [3,4]로 6을 처리한 탐욕 결과의 나머지는 얼마일까요? 이 값으로 정확한 조합이 없다고 결론 내릴 수 있을까요?

함께 읽을 글

• 완전탐색과 쌍 비교: 중복 없는 후보 열거와 순위 계산 — 작은 후보들을 직접 비교하여 탐욕 반례를 찾는 관점으로 연결합니다.
• JavaScript 배열: 인덱스 조회와 삽입·삭제 비용 — 입력 동전 목록을 복사하고 정렬할 때 원본 배열의 역할을 이해합니다.

참고 자료

• Competitive Programmer’s Handbook — 6.1 Coin problem — 큰 동전 우선 선택의 한계, 반례와 탐욕 최적성의 조건.