Swift 코딩테스트 - 탐욕(Greedy) 알고리즘

Greedy Algorithm

최적 해에 가까운 값을 구할 때 사용합니다. 매 순간마다 최적의 방법을 선택하여 값을 구하지만 결과적으로 최적 해라는 보장은 없습니다.

다음 그림을 탐욕 알고리즘으로 풀면 다음과 같이 13 + 11 = 24라는 값이 도출됩니다.
하지만 실제로는 7 + 100 = 107이 나올 수 있는 최대 값입니다. 이렇게 탐욕 알고리즘은 최적 해라는 보장이 없습니다.
최적 해를 구하는 동적 계획법을 사용하면 되지만 속도가 월등히 빠르다는 장점이 있습니다.

---

대표적으로 최소 동전 개수로 돈을 거슬러 주는 예가 있습니다.

• 거스름돈 : 1200원
• 동전 종류 : 500원, 400원, 100원

탐욕 알고리즘에 의하면 500원 2개, 100원 2개로 총 4개가 나옵니다. 하지만 실제로 최적의 개수는 400원 3개입니다.

 

실제 알고리즘 문제를 풀어봅시다. 백준의 11047 동전 0 이라는 문제입니다.
동전의 종류와 거스름돈이 주어질 때 필요한 최소 동전 개수를 구하는 문제입니다.

#11047

 

거스름돈이 4200원일 경우 1000원 4개, 100원 2개로 총 6을 출력해야 합니다.
거스름돈이 4790원일 경우 1000원 4개, 500원 1개, 100원 2개, 50원 1개, 10원 4개로 총 12를 출력해야 합니다.

 

동전 종류를 Int Array로 관리하며, 최솟값을 산출하기 위해 큰 단위의 화폐부터 선택합니다.
낼 돈이 0이 되면 결과를 출력합니다.