[Algorithm] 그리디 알고리즘

그리디 알고리즘이란?

탐욕 알고리즘은 답을 하나씩 고르는데, 미리정한 기준에 따라서 매번 '가장 좋아 보이는' 답을 선택한다. 탐욕 알고리즘은 동적계획과 마찬가지로 최적화 문제를 푸는데 주로 사용한다. 상대적으로 탐욕 알고리즘이 설계하기 훨씬 쉽다. 동적계획은 재귀 관계식을 세워서 입력사례를 더 작은 입력사례로 분할한다. 반면, 탐욕 알고리즘은 입력사례를 분할하지 않는다. 탐욕 알고리즘은 순서대로 답을 하나씩 모아서 최종 답을 구축하는데, 가장 좋아 보이는 답을 선택하여 모은다. 즉 어떤 답을 선택하던지 선택할 당시(locally) 최적이다.
그러므로 항상 최적인 해를 구하고 싶지만, 항상 최적인 해를 얻는다는 보장은 없다.

총 세가지 단계로 구분

1. 선택과정
2. 적절성 검사
3. 해답점검

거스름돈을 예시로 들어보자. 그리디 알고리즘의 최적의 해답은 동전의 개수가 최소가 되는 집합이다. 처음에 빈손으로 시작해서 액면가가 가장 높은 동전부터 시작한다. 즉 어느 동전이 가장 좋은지(지역적으로 최적)을 결정하는 기준은 동전의 액면가이다. 이를 그리디 알고리즘에서는 선택과정 이라고 부른다. 손에 있는 거스름돈의 총액이 거슬러주어야 할 액수와 같은지 검사한다. 이를 탐욕 알고리즘에서 "적절성검사"라고 한다.
만약 거스름돈의 총액이 거슬러주어야 할 액수를 초과하지 않으면, 방금 올려놓은 동전은 거스름돈에 포함된다. 만약 거스름돈의 총액이 거슬러주어야 할 액수와 같은지 검사한다. 이를 탐욕 알고리즘에서는 "해답점검"이라고 한다.

while(동전이 남아있고 문제 미해결){
	가장 가치가 높은 동전을 잡는다;
    if(동전을 더하여 거스름돈의 총액이 거슬러주어야 할 액수를 초과)
    	동전을 도로 집어 넣는다.;
    else
    	거스름돈에 동전을 포함시킨다.;
    if(거스름돈의 총액이 거슬러 주어야 할 액수가 같다.)
    	문제해결;
}