프로그래머스에서 알고리즘을 공부하다보면 탐욕법에 대한 알고리즘이 많이 눈에 띈다. 탐욕법에 대해서 아는 것은 전체를 보지 않고 당장 눈 앞의 것만 확인한다고 알고 있어 제대로 된 문제 풀이가 되지 않는 것 같다.
이 글에서는 탐욕 알고리즘에 대해서 정리를 해보고, 실제 알고리즘에 적용까지 해보도록 하겠다.
탐욕 알고리즘(Greedy Algorithm)
- Greedy는 탐욕스러운, 욕심 많은 이라는 의미를 가진다.
- 탐욕 알고리즘은 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘이다.
- 즉, 탐욕 알고리즘은 선택을 해야하는 순간마다 현재 상황에서 최적의 상황을 쫓아 결과를 도출해내는 방법이다.
- 최적해를 구하는 데에 사용되는 근사적인 방법이다.
- 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들이 합쳐져 최종적인 해답을 도출해냈다고해서, 그것이 최적이라는 보장은 없다.
- but, 탐욕 알고리즘을 적용할 수 있는 문제들은 지역적으로 최적이면서 전역적으로 최적인 문제들이다.
탐욕 알고리즘 문제 해결법
- 선택 절차(Selection Procedure): 현재 상태에서의 최적의 해답을 선택한다.
- 적절성 검사(Feasibility Check): 선택된 해가 문제의 조건을 만족하는지 검사한다.
- 해답 검사(Solution Check): 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.
탐욕 알고리즘 적용 전제 조건
- 탐욕적 선택 속성(Greedy Choice Property) : 이전의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
위의 조건이 성립하지 않는다면 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우에 계산 결과가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 결과가 최적해에 가까운지 보장하려면 엄밀한 증명이 필요하다.
특별한 구조를 가지고 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 구할 수 있는데, 이 구조를 매트로이드라고 한다.
예시 - 매트로이드
편의점에서 총 7,120원의 물건을 구매했을 때, 10,000원의 거스름돈으로 동전의 개수를 최소한으로 거슬러 달라고 하면 어떻게 거슬러 주어야 할까?
- 선택 절차
- 거스름돈 동전 개수를 줄이기 위해서 가장 가치가 높은 동전을 우선 선택한다.
- 적절성 검사
- 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과할 경우 한 단계 작은 동전을 선택한다.
- 해답 검사
- 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족할 경우 1번 과정부터 반복한다.
해답
- 가장 가치가 높은 동전인 500원을 먼저 거슬러 주고 잔액을 확인한 뒤에, 100원, 50원, 10원의 순서대로 거슬러준다.
- 거슬러 주어야 할 금액은 2,880원으로 500원 5개를 먼저 거슬러 주고, 100원 3개, 50원 1개, 10원 3개를 순서대로 거슬러 준다.
