[알고리즘] Greedy Algorithm

Greedy Algorithm 

Greedy Algorithm은 말그대로 탐욕적인 알고리즘이다. 목표를 이루기 위해 큰 그림을 바라보지 않고, 현재 가장 좋아보이는 것으로 이동해나간다. 예를 들어, 더 높은 산을 가기위한 알고리즘을 구현한다고 할때 A산은 현재 30도의 경사를 보이고, B산은 현재 40도의 경사를 보인다고 하자.  B산이 현재 경사가 더 높다고 해서 더 높은 산이 되는 것은 아닐 것이다. 하지만 Greedy Algorithm은 해당 정보를 기반으로 B산을 선택하고 올라간다. 이렇듯, Greedy Algorithm은 완벽한 결과를 보장해주지는 않는다. 하지만 간혹 Greedy Algorithm이 완벽한 결과를 도출해내는 경우도 있고, 속도가 매우 빨라 다른 느린 알고리즘을 대신하여 많이 사용된다.

---

Greedy Algorithm의 조건

 

만약 문제가 최적 부분 구조를 가졌고, 탐욕적 선택 속성을 가졌다면 Greedy Algorithm을 활용해도 최적의 답을 얻어낼 수 있다. 여기서 탐욕적 선택 속성이란, 각 단계에서 탐욕적 선택을 하는 것이 문제에서 최적을 답을 얻어낼 수 있는 경우를 말한다.

 

예를 들어, 거스름돈을 거슬러주는 경우를 떠올려 보자. 가장 적은 동전으로 거슬러 주려면 어떻게 해야할까? 매 순간마다 최대한 높은 단위의 동전을 거슬러주어야 제일 적은 동전을 거슬러 줄 수 있을 것이다. 이런 것이 탐욕적 선택속성을 가진 문제이다.

---

Greedy Algorithm의 선택조건

 

Greedy Algorithm에서 또 하나 중요한 것이 있다. 탐욕적 선택의 선택조건은 유지되어야 한다는 것이다. 그러니까 i번째 문제에서 A라는 조건으로 선택헀다면, i번째가 아닌 다른 문제에서도 A라는 조건으로 선택해야 한다는 것이다.

(한번 제일 높은 단위의 동전을 선택했다면, 그 다음에도 제일 높은 단위의 동전을 선택해야한다.)

---

Greedy Algorithm의 수행과정

 

1) 해 선택 : 먼저 현재 상태에서 접근 가능한 부분 문제의 최적해를 구한뒤, 이를 부분 해 집합에 추가한다.

2) 실행 가능성 검사 : 새로운 부분 해 집합이 실행 가능한지 확인한다. 문제의 제약조건을 위반하는지 검사한다.

3) 해 검사 : 새로운 부분 해 집합이 문제의 해가 되는지 확인한다. 아직 전체 해가 완성되지 않았다면 해 선택부터 다시 시작한다.

 

ex 거스름 돈 주기 문제

1) 해 선택 : 가장 단위가 큰 동전을 골라 거스름돈에 추가한다.

2) 실행 가능성 검사 : 거스름돈이 현재 손님에게 줘야할 액수를 초과하는지 확인하고, 초과할 경우 마지막으로 추가한 거스름돈 정보를 제거하고, 해 선택으로 가서 현재보다 한단계 작은 단위의 거스름돈 추가한다.

3) 해 검사 : 결과값이 액수와 일치하는지 확인한다. 액수가 모자라면 다시 해 선택으로 돌아간다.