[Algorithm] 탐욕 알고리즘(Greedy Algorithm) + 예제(백준 5585번)

① 탐욕 알고리즘(Greedy Algorithm) 이란?

• 탐욕 알고리즘은 '선택의 순간마다 당장 눈 앞의 최적의 상황을 선택 해 최종적인 해답에 도달'하는 방법이다
• 기술적인 용어론 지역 최적해(locally optimal)를 찾음으로써 최종적으로는 전역 최적해(globally optimal)을 구한다
• 탐욕 알고리즘은 구현이 간단하면서도 높은확률로 상당히 정답에 가까운 해결책을 도출 해 내는 장점이 있다.
• 하지만 순간순간의 최적해를 구하는 만큼 전역적으로 그것이 최적해라는 보장은 없다.

ex1) 탐욕 알고리즘으로 전역 최적해와 다른 해가 나오는 경우

 

ex2)탐욕 알고리즘으로 최적해를 구했을 때 전역 최적해가 아닌 경우

• 그렇기에 탐욕 알고리즘은, NP-완전문제와 같이, 모든 가능한 경우를 따져야 하는 방대한 계산을 요구하는 문제의 근사 알고리즘으로써 사용하기에 좋다. (※근사 알고리즘이란? 어떤 최적화 문제의 해의 근사값을 구하는 알고리즘)

---

② 탐욕 알고리즘(Greedy Algorithm)의 조건(정당성)

• 탐욕 알고리즘이 잘 작동하는 문제는 대체로 탐욕스런 선택 조건(greedy choice property)와 최적 부분 구조 조건(optimal substructure) 을 만족한다.
• 탐욕스런 선택 조건(greedy choice property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
• 최적 부분 구조 조건(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
• 탐욕 알고리즘은 근사 알고리즘이기에 이 조건(정당성)을 만족하는지를 체크한 뒤 적용시키는 것이 좋다.

---

③ 탐욕 알고리즘(Greedy Algorithm) 예시 문제(백준 5585번)

5585번 문제

• 문제는 다음과 같고 1000엔 이하의 물건에 대한 지불 비용을 1000엔 지폐 한장으로 했을때, 잔돈의 동전 개수를 최소한으로 받는 문제이다.
• 먼저 위 문제를 탐욕 알고리즘으로 풀어도 된다는 정당성을 확보해야한다.
• 위 거스름돈의 돈 들은 항상 동전 중에서 큰 단위가 작은 단위의 배수이므로 작은 단위의 동전들을 조합 해 다른 경우의 수가 나올 일이 없으므로 탐욕 알고리즘을 통해 최적해를 도출해 낼 수 있다.
• 따라서 가장 큰 단위의 거스름돈부터 최대 개수로 사용 해 나가며(부분 문제에 대한 해결) 결국 동전의 개수를 최소로 사용하여 거스름돈을 줄 수 있는 것이다(전역 문제에 대한 해결)
• 해결 코드는 아래와 같다.

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;

public class BJ5585 {
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		/* 지불할 돈 입력 후 잔돈금액으로 만들어줌 */
		int money = Integer.parseInt(br.readLine());
		money = 1000 - money;
		/* 잔돈으로 줄 수 있는 돈 배열 */
		int[] changes = {500, 100, 50, 10, 5, 1};
		int num;
		int cnt=0;
		
		/* 현재 금액에서 가장 높은 잔돈금액부터 최대의 갯수로 할당 */
		for(int i=0; i<6; i++) {
			num = money / changes[i];
			money = money - changes[i]*num;
			cnt+=num;
		}
		bw.write(String.valueOf(cnt)+"\n");
		bw.flush();
	}
}

---

그림 출처: Wikipedia, https://www.quora.com/What-is-an-intuitive-explanation-of-greedy-algorithms