그리디 알고리즘
매 선택에서 현재 당장 최적인 답을 선택하여 최종 답에 도달하는 알고리즘
하지만 그리디 알고리즘은 전체에서 최적값을 언제나 구할 수는 없다는 문제점을 가진다.
예를 들어
다음과 같은 트리를 탐색할 때,
보통 가장 큰 수를 찾기 위해서는 제일 큰 수인 99에 도달하기 위해 3 → 99의 경로를 선택할 것이다.
하지만 그리디 알고리즘으로 탐색할 경우 3과 12 중에서 당장 더 큰 수인 12를 선택하고, 다음으로는 6을 선택하게 된다.
첫 선택에서 부분 최적해는 구했지만, 전체 문제에서의 최적값을 구하지는 못하게 된 것.
그럼에도 불구하고 그리디는 시간복잡도가 낮다는 장점이 있어 다음과 같은 조건이 만족될 경우에 사용한다.
- 탐욕 선택 속성
이전의 선택이 이후의 선택에 영향을 미치지 않음
- 최적 부분 구조
문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성
→ 부분 문제의 최적 결과가 전체에도 적용될 수 있어야 함
그리디 알고리즘의 예시
가장 대표적인 그리디 문제인 거스름돈 문제로 이해해보자.
Q.
낸 돈은 10000원, 물건의 가격은 8700원일 때, 거스름돈을 최소한의 동전으로 거슬러주면 몇 개를 받게 될까?
(잔돈 단위는 500원, 100원, 50원, 10원, 1원)
A.
거스름돈이 1300원이므로1300/500 = 2, 500원 2개
300/100 = 3, 100원 3개총 5개의 동전을 받게된다.
즉, 최소한의 동전을 거슬러주기 위해서는 가장 큰 단위의 동전부터 선택해야만 다음 단계에서 최적해에 가장 근접해질 수 있다는 것.
가격을 입력받는다 가정하고, 코드로 간단하게 구현하면 다음과 같다
public class greedy{
public static int charge(int price){
int pay = 10000;
int[] coins = {500, 100, 50, 10, 1};
int count = 0;
for(int i=0; i<coins.length; i++){
if(pay % coins[i] >= 0){
count += pay / coins[i];
pay %= coins[i];
}
}
return count;
}
}BUT, 이 문제에서 400원 동전이 추가된다면 ?
Q.
낸 돈은 10000원, 물건의 가격은 8700원일 때, 거스름돈을 최소한의 동전으로 거슬러주면 몇 개를 받게 될까?
(잔돈 단위는 500원, 400원, 100원, 50원, 10원, 1원)
A.
그리디로 풀었을 때는 5개가 답이였지만,
이 경우에서의 최적해는1300/400 = 3, 400원 3개
100/100 = 1, 100원 1개총 4개가 된다.
즉, 이 경우 탐욕 선택 속성을 만족하지 못하므로 그리디보다는 다른 알고리즘 (DP)을 사용해 최적해를 구해야 함.
[이미지 출처] https://pixx.tistory.com/167
