탐욕 알고리즘(greedy algorithm)

Goal

• 탐욕 알고리즘과 특징에 대해 설명할 수 있다.
• 탐욕 알고리즘으로 최적해를 구할 수 있는 경우에 대해 설명할 수 있다.

---

탐욕 알고리즘(greedy algorithm)

현재 순간 최적(local optimal)이라고 생각되는 것을 선택함으로써 최종적인 해답에 도달하는 방법

탐욕법(greedy method)이라고도 한다.

 

특징

• 순간 최적 선택한 결과가 전체 문제의 최적이라는 보장이 없다.
• 현재의 선택이 앞으로 남은 선택에 어떤 영향을 끼칠지는 고려하지 않는다.

 

다음 그림은 탐욕 알고리즘이 항상 최적을 보장하지 않음을 나타낸다.

 

 

그렇다면, 항상 최적의 결과라는 것을 보장하지 못하는데 왜 탐욕 알고리즘을 사용하는가?

그 이유는 다음과 같다.

1. 빠르다 : 탐욕 알고리즘을 사용해도 항상 최적해를 구할 수 있는 경우, 동적 계획법보다 수행 시간이 훨씬 빠르다.
2. 적당히 괜찮은 답을 구할 수 있다 : 시간이나 공간적 제약으로 인해 최적해를 찾기 어렵다면 적당히 괜찮은 답을 찾는 것으로 타협할 수 있다. 이때, 탐욕법을 사용하면 임의의 답 보다는 더 괜찮은 답으로 사용될 수 있다.

<참고>

보통 프로그래밍 대회에서는 첫 번째 용도로만 사용된다.

 

두 번째 용도로 사용할 때 현실적이 근사값을 찾기 위한 방법으로 휴리스틱(heuristic)기법 등을 사용할 수 있다.

 

*휴리스틱(heuristic)

'경험에 의거한' 문제 풀이 기법으로, '대충 어림 짐작해서 풀기' 라고 생각하면 된다.

항상 최적의 답을 찾아내지는 못하지만, 근사값 등을 통해 어느 정도 현실에 가까운 답을 빨리 찾기 위한 용도로 사용된다. (최적화 용도로 사용)

ex) A* 알고리즘에서 사용 되는 heuristic 함수들

 

위키백관 참고

'휴리스틱' 또는 '발견법'이란 불충분한 시간이나 정보로 인하여 합리적인 판단을 할 수 없거나, 체계적이면서 합리적인 판단이 굳이 필요하지 않은 상황에서 사람들이 빠르게 사용할 수 있게 보다 용이하게 구성된 간편추론의 방법이다.

 

탐욕 알고리즘이 잘 동작하는(최적해를 찾아내는) 문제는 다음 두 가지 속성을 만족한다.

1. 탐욕적 선택 속성(greedy choice property)
2. 최적 부분 구조(optimal substructure)

 

*greedy choice property

탐욕적으로만 선택을 해도 최적해를 구할 수 있다는 의미

(전체 문제의 최적해가 아닌 현재까지의 최적해이다!)

 

현재의 선택은 이전 까지의 선택에 따라 달라지지만, 앞으로의 선택에 의해서 현재의 선택이 달리지지는 않는다.

즉, 일단 현재 순간의 최적을 한번 선택하면, 이를 번복하지 않는다. (선택한 것을 버리고 다른 것을 취하지 않는다.) 

 

이는 다이나믹 프로그래밍과 가장 큰 차이점으로,

모든 단계를 끝마치고 이전으로 돌아가 재고하는 과정이 없다는 의미이다.

 

*optimal substructure

전체 문제의 최적해가 각 부분 문제들의 최적해로 이루어진 경우

 

이 속성을 만족하면 '최적 부분 구조를 갖는다'라고 한다.

반대로, 부분 문제들의 최적해만으로 전체 최적해를 얻을 수 없는 경우 '최적 부분 구조를 갖지 않는다.'고 한다. 

 

ex) 최적 부분 구조를 갖지 않는 경우

첫 번쨰 선택을 하고 나서 남는 부분 문제는 최적이 아닌 방법으로  풀어야 하는 경우

 

탐욕 알고리즘(Greedy Algorithm) vs 동적 계획법(Dynamic Programming)

탐욕 알고리즘

• 한번 선택하고 나면 번복하지 않는다. (그 순간의 최적을 선택)
• 항상 최적해를 보장하지는 않는다. (정당성 증명 과정을 반드시 거쳐야 함)
• 대게 동적 계획법보다 더 빠른 성능을 보인다.

동적 계획법

• 전체 단계를 마치고, 최적해를 찾기 위해 재고하는 단계를 거친다.
• 항상 최적해를 보장한다.

 

탐욕 알고리즘 문제 풀이 레시피

1. 문제의 답을 만드는 과정을 여러 조각으로 나눈다.
2. 각 조각마다 어떤 우선순위로 선택할지 결정. (이에 대한 직관을 얻기 위해서 작은 입력을 몇 개 풀어봄)
3. 두 가지 속성 증명 (greedy choice property, optimal substructure)

---