그리디(Greedy) 알고리즘이란? (+ 백준 5585번 : 거스름돈)
그리디(Greedy) 알고리즘이란?
그리디(Greedy)란 탐욕스러운, 욕심 많은 이란 뜻으로 탐욕 알고리즘, 탐욕법이라고도 불린다.
탐욕법은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다.
하지만 최적의 상황을 쫓는다고 해서 항상 최적의 해답을 보장하는 것은 아니다.
예를 들어 위와 같은 경우, 최적의 선택은 3 - 100 을 선택하는 경로이지만, 탐욕법은 지금 당장 큰 값인 10 - 8 경로를 선택하게 되기 때문에 선택의 순간에는 최적의 선택이지만, 최종적으로는 최적의 선택이 아닐 수 있다는 것이다.
탐욕 알고리즘 문제를 해결하는 방법
선택 절차
현재 상태에서 최적의 해답을 선택한다.
적절성 검사
선택된 해가 문제의 조건을 만족하는지 검사한다.
해답 검사
원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택절차로 돌아가 위의 과정을 반복한다.
그리디 알고리즘 적용 문제의 조건
그리디 알고리즘을 사용해서 문제를 풀기 위해서는 해당 문제가 2가지의 조건을 만족해야한다.
1. 탐욕스러운 선택 조건(greedy choice property)
한번의 선택이 다음 선택에는 전혀 무관한 값이어야 한다는 의미
2. 최적 부분 구조(optimal substructure)
문제의 최적 해결 방법은 부분 문제에 대한 최적 해결 방법으로 구성된다는 의미이다.
즉, 지금 당장 최선의 선택들이 문제를 해결하는 최적의 해답이라는 것
위의 조건이 성립되지 않는다면, 그리디 알고리즘을 통해서 최적의 해를 구하지 못한다.
그러나, 위의 조건이 성립되지 않더라도 그리디 알고리즘은 근사 알고리즘으로 사용이 가능하다.
근사(Approximation) 알고리즘
어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘이다.
가장 최적화 되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며, 어느정도 보장된 근사해를 계산할 수 있다.
예제문제
https://www.acmicpc.net/problem/5585
5585번: 거스름돈
타로는 자주 JOI잡화점에서 물건을 산다. JOI잡화점에는 잔돈으로 500엔, 100엔, 50엔, 10엔, 5엔, 1엔이 충분히 있고, 언제나 거스름돈 개수가 가장 적게 잔돈을 준다. 타로가 JOI잡화점에서 물건을 사
www.acmicpc.net
거스름돈(500, 100, 50, 10, 5, 1)을 최소한으로 거슬러주면 되는 문제이다.
선택 절차
거스름돈의 동전 개수를 줄이기 위해 가장 큰 동전을 우선선택한다.
적절성 검사
반환금액이 가장 큰 동전의 값보다 낮은지 검사한다.
가장 큰 동전의 값 보다 낮다면, 그 다음 큰 값의 동전으로 검사한다.
해답 검사
"반환금액 = 반환금액 - 위에서 고른 동전"을 하고,
반환금액이 0이 될 때 까지 위의 과정을 반복한다.
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int[] change = {500,100,50,10,5,1};
int num = 1000-Integer.parseInt(br.readLine());
int count = 0;
while(num!=0) {
for(int i : change) {
if(num>=i) {
num = num - i;
count++;
break;
}
}
}//end while
System.out.println(count);
}
}참고자료
https://namu.wiki/w/%EA%B7%B8%EB%A6%AC%EB%94%94%20%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98#s-5