1. 정의
- 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한
알고리즘 - 지금의 선택이 앞으로 남은 선택들에 거떤 영향을 끼칠지 고려하지 않는다.
- 당장 눈 앞의 이익만을 좇는다.
- 일반적인 상황에서 그리디 알고리즘은 최적의 해를 보장할 수 없을 때가 많다.
- 그리디 알고리즘은 대체로 좋은 결과를 기대할 수 없지만, 특정 문제에서는 그리디
알고리즘이 최적해를 보장해주기도 한다.
각 단계의 합이 최대값이고 싶을 때
최적: 103
그리디: 18
2. 필요 조건
아래 두 가지 조건을 만족하면 그리디 알고리즘을 사용하여 최적해를 도출할 수 있다.
탐욕적 선택 속성
- 앞의 선택이 이후의 선택에 영향을 주지 않는다.
최적 부분 구조
- 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
3. 문제 예시
문제: 거스름돈
거스름돈으로 사용할 수 있는 500원, 100원, 50원, 10원짜리 동전이 무한이 존재한다고 가정한다.
손님에게 거슬러 줘야 할 돈이 1260원일 때 거슬러 줘야 할 동전의 최소의 개수를 구하여라.
문제 해설
그리디 알고리즘을 이용해 풀어보면, 가장 큰 화폐 단위부터 돈을 거슬러 주면 된다.
가장 먼저 500원으로 거슬러 줄 수 있을 만큼 거슬러주고, 100 -> 50 -> 10원짜리 동전을 차례대로 거슬러 줄 수 있을 만큼 거슬러 주면 최소의 동전 개수로 모두 거슬러 줄 수 있다.
public class CoinChange {
// 동전 종류를 상수로 정의
private static final int[] COIN_TYPES = {500, 100, 50, 10};
public static void main(String[] args) {
int amount = 1260; // 거스름돈 총액
System.out.println("Minimum coins needed: " + calculateMinimumCoins(amount));
}
private static int calculateMinimumCoins(int amount) {
int count = 0;
for (int coin : COIN_TYPES) { // 500, 100, 50, 10
count += amount / coin;
amount %= coin;
}
return count;
}
}| Coin Type | Count |
|---|---|
| 500원 | 2개 |
| 100원 | 2개 |
| 50원 | 1개 |
| 10원 | 1개 |
ref.
https://velog.io/@falling_star3/%EA%B7%B8%EB%A6%AC%EB%94%94-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Greedy-Algorithm
https://choiyeonho903.tistory.com/65
