최소 동전 교환 문제

최소 동전 교환 문제를 Swift로 구현한 알고리즘이다. 동적 프로그래밍 알고리즘 설계와 전통적인 탐욕적 접근법을 비교한다.

Swift Algorithm Club을 위해 Jacopo Mangiavacchi가 작성했다.

소개

전통적인 동전 교환 문제에서는 주어진 금액을 특정 동전 세트(예: 1센트, 2센트, 5센트, 10센트 등)를 사용해 교환할 수 있는 모든 방법을 찾아야 한다.

예를 들어, 유로 센트를 사용할 때 4센트를 교환하는 방법은 다음과 같다:

• 1센트 동전 4개
• 2센트 동전 2개
• 2센트 동전 1개와 1센트 동전 2개

최소 동전 교환 문제는 일반적인 동전 교환 문제의 변형으로, 가장 적은 수의 동전을 사용해 금액을 교환하는 최적의 방법을 찾는 문제다.

예를 들어, 유로 센트를 사용할 때 4센트를 교환하는 최적의 방법은 2센트 동전 2개로 총 2개의 동전을 사용하는 것이다.

탐욕 알고리즘 솔루션

최소 동전 교환 문제를 매우 효율적으로 구현하는 간단한 방법은, 주어진 금액에서 가능한 가장 큰 동전 값을 빼고, 남은 금액에 대해 같은 논리를 반복 적용하는 것이다.

예를 들어, 위의 예시에서 4유로 센트를 거슬러 줄 때, 5센트 이상의 동전은 4센트보다 크기 때문에 먼저 2센트 동전을 사용한다. 첫 번째 2센트 동전을 사용한 후, 남은 2센트에 대해 같은 논리를 적용해 다시 2센트 동전을 선택한다. 최종적으로 두 개의 2센트 동전이 최적의 거스름돈으로 반환된다.

대부분의 경우 이 탐욕 알고리즘은 최적의 결과를 제공하지만, 특정 동전 조합에서는 최적이 아닐 수 있다.

실제로, 1, 3, 4센트 동전 세트를 사용해 6센트의 최적 거스름돈을 구할 때, 이 탐욕 알고리즘을 적용하면 4센트 동전 하나와 1센트 동전 두 개를 반환한다. 하지만 실제 최적의 해는 3센트 동전 두 개이다.

동적 프로그래밍 솔루션

전통적인 동적 프로그래밍 전략은 주어진 동전 집합에서 가능한 동전을 순서대로 선택하고, 선택한 동전과 전달된 값의 차이에 대해 재귀 호출을 통해 최소 동전 거스름돈을 찾는다. 알고리즘은 각 단계에서 가능한 모든 조합 중에서 사용된 동전 수가 가장 적은 조합을 선택한다.

동적 프로그래밍 접근 방식은 항상 최적의 거스름돈을 선택하지만, 목표 금액에 대해 최소한 이차적인 수의 단계가 필요하다.

이 Swift 구현에서는 전체 성능을 최적화하기 위해 이전 값들에 대한 최소 동전 거스름돈 결과를 캐싱하는 내부 데이터 구조를 사용한다.