탐욕법(Greedy Algorithm)
탐욕법이란
탐욕법, 즉 그리디 알고리즘은 문제를 해결하는 데 있어 매 단계에서 가장 최선의 선택을 하는 방식이다.
이 알고리즘은 현재 상황에서 최적의 선택을 하여 문제를 해결하고자 하지만, 이후의 선택이 최종 결과에 미치는 영향을 고려하지 않는다는 점에서 최적의 해를 보장하지 않는다. 따라서 해당 문제가 그리디 알고리즘을 사용하기에 적합한 문제인지 판단하는 것이 중요하다.
그리디 알고리즘의 장점은 구현이 간단하고, 빠른 시간 내에 결과를 도출할 수 있다는 점이다. 하지만 단점으로는 모든 문제에 적용할 수 없고, 최적의 해를 보장하지 않는다는 점이 있다.
탐욕법을 적용하기 위한 기준
탐욕 알고리즘을 적용하기 위해서는 두 가지 기준이 필요하다.
- 문제를 작은 부분 문제로 나누었을 때, 그 부분 문제의 최적해가 전체 문제의 최적의 결과값에 기여해야 한다. ( = 최적 부분 구조)
- 매 단계에서의 선택이 최적의 결과를 보장해야 한다. ( = 탐욕 선택 속성)
그리디 알고리즘의 대표적인 예로는 거스름돈 문제를 들 수 있다.
어떤 사람이 물건을 계산하고 거스름돈을 받아야하는데, 그 거스름돈이 36달러라고 가정해보자.
이 문제는 위에서 정의한 탐욕법을 적용하기 위한 기준을 충족하고있다.
1. 최적 부분 구조
거스름돈 문제는 최적의 결과를 도출하기위해 문제를 작은 부분으로 나눌 수 있다. 각 단계에서 가능한 가장 큰 단위의 동전으로 거슬러주는 것이 최종적으로 최소한의 동전 개수를 사용하는 최적의 방법이다.
즉, 큰 단위의 동전을 먼저 사용하는 것이 나중에 남은 금액을 처리할 때도 유리한 상황인 것이다.
2. 탐욕 선택 속성
매 단계에서 형재 주어진 금액에 대해 가장 큰 동전을 선택하는 것이 최적의 결과를 보장한다.
예를 들어, 만약 36달러의 거스름돈을 줘야 할 때, 20달러를 먼저 주고, 남은 16달러에 대해 10달러, 5달러, 1달러를 차례로 주는 방식은 항상 최소의 동전 개수로 거슬러 줄 수 있게 된다.
예시 문제 풀어보기
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다.
타로가 JOI잡화점에서 물건을 사고 카운터에서 1000엔 지폐를 한장 냈을 때, 받을 잔돈에 포함된 잔돈의 개수를 구하는 프로그램을 작성하시오.
function getMinCoins(amount, coins) {
let totalCoins = 0;
coins.sort((a, b) => b - a); // 동전 종류를 내림차순으로 정렬
for (let coin of coins) {
while (amount >= coin) {
amount -= coin;
totalCoins++;
}
}
return totalCoins;
}
위의 코드에서 getMinCoins 함수는 주어진 금액을 최소한의 동전으로 거슬러 주기 위해 동전의 종류를 내림차순으로 정렬한 후, 큰 동전부터 차례로 빼면서 동전의 개수를 세는 방식으로 동작한다.
이처럼 그리디 알고리즘은 간단한 문제를 빠르게 해결할 수 있는 장점이 있다. 하지만 항상 최적의 결과를 보장하지 않기 때문에, 문제의 특성을 잘 이해하여 적절하게 적용하는 것이 중요하다.
참고 자료
https://en.wikipedia.org/wiki/Greedy_algorithm https://www.geeksforgeeks.org/greedy-algorithms/ https://www.acmicpc.net/problem/5585