📌개요
Greedy는 '탐욕스러운, 욕심 많은' 이란 뜻으로, 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
매 순간 가장 좋아 보이는 것만 선택하며, 현재의 선택이 나중에 미칠 영향에 대해서는 고려하지 않는다.
동적 프로그래밍 사용 시 지나치게 많은 일을 한다는 것에서 착안하여 고안된 알고리즘이다.
🔎사용 조건
1. 탐욕 선택 속성
이전의 선택이 이후에 영향을 주지 않음
2. 최적 부분 구조
부분 문제의 최적결과가 전체에도 그대로 적용될 수 있어야 함
💁♀️그리디 알고리즘 문제를 해결하는 방법
1. 선택 절차(Selection Procedure)
현재 상태에서의 최적의 해답을 선택한다.
2. 적절성 검사(Feasibility Check)
선택된 해가 문제의 조건을 만족하는지 검사한다.
3. 해답 검사(Solution Check)
원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
🙅♂️DP와의 차이
DP의 경우에는 문제가 Overlapping되기 때문에 다음에 풀 문제가 이전의 작은 문제의 ㅕㄹ과에 영향을 받게 된다. 즉, 동일한 형식의 문제가 점점 커질 뿐, 이전의 경우에 영향을 받는다.
하지만 그리디 알고리즘은 이와 달리 영향 받아서는 안된다. 그래야 다른 경우의 결과에 상관 없이 최적해를 구할 수 있다.
💸예시) 거스름돈
거스름돈으로 사용할 500원, 100원, 50원, 10원짜리 동전이 무한히 존재한다고 한다. 거슬러줘야 할 돈이 N원일때 거슬러 줘야 할 동전의 최소 개수를 구하라
문제 해설
가장 큰 화폐 단위부터 돈을 거슬러 주어야 한다.
500원으로 최대한 많이 거슬러 주고, 순서대로 100원, 50원, 10원을 써서 거슬러 주면 된다.
예시로 N을 2680으로 두겠다.
int[] coinUnit = {500, 100, 50, 10};
int money = 2680;
for(int i = 0; i <coinUnit.length; i++){
System.out.println(coinUnit[i]+"원: " + money / coinUnit[i]);
money %= coinUnit[i];
}
야호