거스름돈 문제편집자 확인

거스름돈 문제는 주어진 금액을 가능한 한 적은 수의 동전과 지폐로 구성하는 최적화 문제이다. 이 문제는 탐욕 알고리즘의 대표적인 예시로, 각 단계에서 가장 큰 단위의 화폐를 최대한 많이 사용하는 방식으로 해결한다. 자판기, 금융 거래, 계산 시스템 등 현금을 효율적으로 처리해야 하는 다양한 분야에서 실제로 응용된다.

이 문제는 알고리즘과 컴퓨터 과학의 기본적인 학습 주제이며, 조합 최적화 문제의 한 종류로 분류된다. 탐욕 알고리즘은 특정 조건 하에서 항상 최적해를 보장하는데, 이는 사용하는 화폐 체계가 표준 화폐 체계일 때 성립한다. 그러나 모든 화폐 체계에서 탐욕법이 최적해를 찾는 것은 아니며, 이 경우 다이나믹 프로그래밍 등의 다른 접근법이 필요하다.

거스름돈 문제는 특정 금액을 지불하거나 거슬러 줄 때, 주어진 동전과 지폐의 단위를 사용하여 그 금액을 구성하는 방법 중에서 사용한 화폐의 총 개수를 최소화하는 조합 최적화 문제이다. 이 문제는 알고리즘 이론, 특히 탐욕 알고리즘을 설명하는 가장 대표적인 예시로 자주 등장한다.

문제의 핵심은 사용 가능한 화폐의 단위 집합과 목표 금액이 주어졌을 때, 그 금액을 정확히 맞추면서도 필요한 화폐의 개수가 가장 적은 조합을 찾는 것이다. 예를 들어, 한국 원화의 표준 단위인 1원, 10원, 50원, 100원, 500원 동전과 1000원, 5000원, 10000원, 50000원 지폐가 있다고 가정하고, 7,800원을 가장 적은 수의 화폐로 구성하려면 5000원 지폐 1장, 1000원 지폐 2장, 500원 동전 1개, 100원 동전 3개를 사용하면 총 7개로 만들 수 있다.

이 문제는 단순해 보이지만, 사용 가능한 화폐 체계에 따라 최적해를 찾는 방법이 달라진다. 대부분의 현실 통화 체계는 탐욕 알고리즘이 항상 최적해를 찾을 수 있도록 설계되어 있어, 가장 큰 단위의 화폐부터 가능한 많이 사용하는 방법이 효율적이다. 이러한 특성 덕분에 이 문제는 자판기, 금융 거래 시스템, 계산 시스템 등에서 효율적인 현금 처리를 구현하는 데 널리 응용된다.

거스름돈 문제를 해결하는 또 다른 방법은 다이나믹 프로그래밍이다. 이 방법은 탐욕 알고리즘이 항상 최적해를 보장하지 못하는 화폐 체계에서 특히 유용하다. 다이나믹 프로그래밍은 큰 문제를 작은 하위 문제로 나누어 해결하고, 그 결과를 저장해 중복 계산을 피하는 방식으로 작동한다. 거스름돈 문제에서는 목표 금액을 만들기 위한 최소 동전 개수를 점진적으로 구축해 나간다.

구체적으로, 0원부터 목표 금액까지 각 금액을 만들 수 있는 최소 동전 개수를 저장할 배열을 만든다. 초기값으로 0원은 0개의 동전으로 만들 수 있고, 나머지 금액은 무한대(또는 매우 큰 수)로 설정한다. 이후 각 화폐 단위를 순회하며, 현재 금액에서 해당 화폐 단위를 뺀 금액의 최소 동전 개수에 1을 더한 값과 기존 값을 비교해 더 작은 값으로 갱신한다. 이 과정을 모든 금액과 모든 화폐 단위에 대해 반복하면 최종적으로 목표 금액의 최소 동전 개수를 얻을 수 있다.

이 접근법의 핵심 장점은 모든 가능성을 체계적으로 고려하기 때문에 어떤 화폐 단위 조합이 주어지더라도 항상 최적해를 찾을 수 있다는 점이다. 예를 들어, 화폐 단위가 1, 3, 4원인 체계에서 6원을 만드는 경우, 탐욕법은 4원, 1원, 1원(총 3개)을 선택하지만, 다이나믹 프로그래밍은 3원, 3원(총 2개)이라는 최적해를 정확히 찾아낸다. 따라서 유한 수학이나 조합론적 최적화가 필요한 보다 일반적인 경우에 강력한 도구가 된다.

다만, 이 방법은 시간 복잡도와 공간 복잡도 측면에서 탐욕법보다 비용이 더 든다. 시간 복잡도는 목표 금액과 사용 가능한 동전 종류의 수에 비례하며, 공간 복잡도는 목표 금액에 비례하는 배열을 필요로 한다. 그럼에도 불구하고 정확성을 보장해야 하는 금융 소프트웨어나 자동 거래 시스템 등에서는 다이나믹 프로그래밍 접근법이 선호될 수 있다.

거스름돈 문제를 해결하는 두 가지 주요 알고리즘인 탐욕 알고리즘과 다이나믹 프로그래밍은 각각 장단점이 뚜렷하다. 두 방법의 핵심 차이는 최적해를 보장하는 조건과 계산 비용에 있다.

탐욕 알고리즘은 항상 가장 큰 단위의 화폐부터 사용하는 직관적인 방식을 따른다. 이 방법은 계산 속도가 매우 빠르고 구현이 간단하다는 장점이 있다. 그러나 이 알고리즘이 항상 최소 개수의 화폐를 보장하는 것은 아니다. 탐욕법이 최적해를 보장하려면 해당 화폐 체계가 특별한 성질, 즉 '탐욕적 선택 속성'을 만족해야 한다. 대표적인 예로 미국 달러나 유로의 일반적인 동전 체계(1¢, 5¢, 10¢, 25¢)는 이 조건을 만족한다. 반면, 임의의 화폐 단위가 주어지면, 예를 들어 1, 3, 4원 동전으로 6원을 만들 경우, 탐욕법(4+1+1)은 최적해(3+3)를 찾지 못한다.

반면, 다이나믹 프로그래밍 접근법은 모든 가능한 조합을 체계적으로 검토한다. 이 방법은 주어진 금액에 대해 0원부터 목표 금액까지의 모든 부분 문제를 해결하며, 각 금액을 만드는 데 필요한 최소 동전 개수를 기록한다. 이 과정은 메모이제이션이나 타뷸레이션 기법을 사용한다. 다이나믹 프로그래밍은 어떤 화폐 체계에서도 항상 최적해를 보장한다는 결정적인 장점이 있다. 그러나 그 대가로 탐욕법에 비해 상대적으로 느린 실행 시간과 더 많은 메모리 사용량이 요구된다. 특히 목표 금액이 크고 화폐 종류가 많을수록 이 차이는 두드러진다.

따라서 실제 금융 시스템이나 자판기처럼 화폐 단위가 표준화되어 탐욕적 속성이 확실한 경우에는 탐욕 알고리즘이 효율성과 간결함 때문에 선호된다. 반면, 화폐 단위가 임의적이거나 문제가 변형된 경우, 또는 최적해 보장이 절대적으로 중요한 경우에는 다이나믹 프로그래밍이 필수적인 해법이 된다.

거스름돈 문제는 기본 형태 외에도 다양한 응용 분야와 변형 문제가 존재한다. 가장 직접적인 응용은 자판기나 POS 시스템과 같은 현금 거래가 일어나는 금융 및 소매 시스템에서 효율적인 현금 처리를 구현하는 것이다. 또한 은행의 현금 인출기나 교통카드 충전기의 잔액 환불 시스템에서도 동일한 원리가 적용된다.

이 문제의 주요 변형 중 하나는 각 동전의 개수에 제한이 있는 경우이다. 예를 들어, 특정 액면가의 동전이 무한정 공급되지 않고 유한한 수량만 있을 때, 주어진 금액을 만들 수 있는지 여부를 판단하거나 최소 개수의 동전을 사용하는 방법을 찾는 문제로 확장된다. 이는 자원 제약 하의 조합 최적화 문제로 볼 수 있다.

또 다른 중요한 변형은 동전 체계 자체가 달라지는 경우이다. 탐욕 알고리즘이 항상 최적해를 보장하지 않는 일반적인 화폐 체계에서 최소 동전 개수를 찾는 문제는 다이나믹 프로그래밍의 전형적인 적용 사례가 된다. 이는 특정 국가의 비표준 통화 단위를 모델링하거나, 게임 내 가상 화폐 시스템을 설계할 때 고려해야 할 수 있다.

더 나아가, 거스름돈 문제는 배낭 문제의 특수한 형태로도 해석될 수 있으며, 정수 계획법이나 그래프 이론을 이용한 접근법도 연구된다. 이러한 변형들은 알고리즘 이론 교육에서 기본 개념을 이해하고 더 복잡한 최적화 문제로 나아가는 중요한 교두보 역할을 한다.

• 위키백과 - 거스름돈 문제

• 위키백과 - 탐욕 알고리즘

• 위키백과 - 동적 계획법

• 위키백과 - NP-완전

• 위키백과 - 배낭 문제

• 위키백과 - 조합 최적화

• 위키백과 - 유한 자동 기계

• 위키백과 - 정수 계획법