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

 탐욕 알고리즘(greedy algorithm)은 선택의 순간마다 당장 눈앞에 보이는 최적의 상황만을 쫓아 최종적인 해답에 도달하는 방법이다. 즉, 최적해를 구하는 데에 사용되는 근사적인 방법이다.

 

 순간마다 하는 선택은 그 순간에 한해서는 최적이지만 그러한 선택들을 통해 최종적인 해답을 얻었다고 해서 그 해답이 최적이라는 보장이 없다. 예외의 상황이 있을 수 있기 때문이다. 따라서, 이러한 예외 상황을 배제하고 탐욕 알고리즘을 통해 최적의 해를 구하기 위해서는 다음과 같은 두 가지 조건을 만족시켜야 한다.

 

• 탐욕적 선택 속성(Greedy Choice Property)
  : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
  
  
• 최적 부분 구조(Optimal Substructure)
  : 문제에 대한 최적해가 부분문제에 대해서도 최적해이다.

 

 위의 두 조건이 성립하지 않는 경우에 탐욕 알고리즘은 최적해를 구하지 못할 수도 있다. 하지만, 이러한 경우에도 근사 알고리즘으로 사용이 가능할 수도 있고 대부분 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다.

 

 

 

 

적용 방법

 탐욕 알고리즘으로 문제를 해결하는 방법은 다음과 같이 단계적으로 구분할 수 있다.

 

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

 

 예를 들어, 마트에 가서 장을 보고 총 가격이 49040원이 나왔다고 한다. 잔돈을 받아야 하는데 동전의 개수를 최소한으로 해서 거슬러 받을 경우에 탐욕 알고리즘을 적용할 수 있다.

 

1. 선택 절차 -> 동전 개수를 줄이기 위해 가장 가치가 높은 동전을 선택한다.
2. 적절성 검사 -> 1번 과정을 통해 선택된 동전들의 합이 잔돈을 초과하는지 확인한다. 만약 초과한다면 마지막에 선택한 동전을 삭제하고 1번으로 돌아가서 한 단계 작은 동전을 선택한다.
3. 해답 검사 -> 동전들의 합이 잔돈과 일치하는지 검사한다. 만약 액수가 부족하면 다시 1번 과정부터 반복한다.

 이 과정을 통해서 먼저 500원 동전 1개를 받고 순서대로 100원 4개, 50원 1개, 10원 1개를 받는다.