[알고리즘] 탐욕 알고리즘(Greedy Algorithm)

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

• 선택의 순간마다 당장 눈 앞에 보이는 최적의 해답(local optional solution)을 찾으며, 이를 바탕으로 최종 문제의 해답(global optional solution)에 도달하는 방법이다.
• 매 순간의 선택은 지역적으로는 최적의 해답이지만, 그 선택들을 반복하여 얻은 최종적인 해답이 최적이라는 보장은 없다.
• 항상 최적의 해답을 찾는 것은 아니지만, 최적에 근사한 값을 빠르게 찾을 수 있다. 따라서 근사 알고리즘(approximation algorithm)으로 사용할 수 있다. 
• 동적 계획법보다 효율적이지만, 동적 계획법처럼 반드시 최적의 해를 구한다는 보장을 하지 못한다.

탐욕 알고리즘 조건

아래 두가지 조건을 만족하는 경우, 탐욕 알고리즘을 사용하여 최적해를 구할 수 있다. 

1.  탐욕스런 선택 조건(greedy choice property): 앞의 선택이 이후의 선택에 영향을 주지 않는다.
2. 최적 부분 구조 조건(optimal substructure): 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

탐욕 알고리즘을 사용하여 문제를 해결하는 단계

1. 선택 절차(Selection Procedure): 현재 상태에서 최적의 해답을 선택
2. 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

예시

최소수의 동전으로 거스름돈 거슬러주기

1. 선택 절차(Selection Procedure)

가장 값이 높은 동전을 우선으로 거스름돈을 구성하면 거슬러줄 동전의 개수가 줄어든다. 따라서 현재 고를 수 있는 가장 값이 높은 동전을 골라서 집합에 추가한다.

 

2. 적절성 검사(Feasibility Check)

부분해 집합이 거슬러 줄 금액을 초과하는지 검사한다. 만약 초과한다면, 가장 최근에 추가한 동전을 삭제하고 다시 '선택 절차'로 돌아가서 현재보다 한단계 작은 동전을 추가한다.

 

3. 해답 검사(Solution Check)

부분해 집합이 거슬러줄 금액과 일치하는지 검사한다. 거슬러줄 금액보다 액수가 적다면 다시 '선택 절차'로 돌아가서 부분해 집합에 추가한 동전을 고른다.