그리디 알고리즘(Greedy Algorithm) 개념 및 구현

Greedy는 사전 상 탐욕스러운, 욕심 많은의 의미를 가지고 있다. 그래서 탐욕 알고리즘이라고도 한다. 

 

탐욕 알고리즘은 "최적해"를 구하는데 사용되는 근사적인 방법이다. "최적해"를 구한다는 보장은 없지만 단순하게 동작하기 때문에 실용적이다. 

 

최적해를 얻을 수 있는 조건 

1. 탐욕스러운 선택 속성(Greedy choice property)

탐욕스러운 선택 속성이 존재한다는 말은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 뜻이다.  

 

2. 최적 부분 구조 조건(Optimal Substructure)

최적 부분 구조 조건은 문제에 대한 최적해가 부분 문제에 대해서도 역시 최적해라는 것이다. 

 

 "탐욕스러운 선택 속성과 "최적 부분 구조 조건"을 가지고 있는 경우는 탐욕 알고리즘을 이용해서 항상 최적해를 찾을 수 있다. 

이러한 구조를 "매트로이드"라고 한다. 매트로이드를 만들 수 없다면 근사해를 얻는 방법으로 사용할 수 있다.  

 

 

예시) 동전교환

 

import java.util.Scanner;

public class Main
{
	public static void main(String[] args) {
	    Scanner scan = new Scanner(System.in);
	    int total = scan.nextInt();
	    int minCoinCnt = 0;
	    int coins[] = {500, 100, 50, 10};
	    
	    for (int coin : coins){
	        minCoinCnt += (total/coin);
	        total %= coin;
	    }
		
		System.out.println("result = " + minCoinCnt);
	}
}

 

각 동전은 서로 배수와 약수 관계다. 이 조건 때문에 이 문제는 메트로이드가 된다. 하지만 배수와 약수 관계가 아니면 근사해를 얻는다. 

예를 들어 10원, 6원, 1원 동전인 국가가 있다. 이때 18원을 동전을 교환하면 10원 1개, 6원 1개, 1원 2개가 된다. 하지만 6원 3개를 주면 더 적게 줄 수 있다.