:: ADVANCE ::
[Greedy] Greedy Algorithm (그리디, 탐욕 알고리즘) 본문
[Greedy] Greedy Algorithm (그리디, 탐욕 알고리즘)
정의 : 미리 정한 기준에 따라서 매번 가장 좋은 답, 최선의 답을 선택하는 알고리즘
최적화 문제를 푸는 데 사용한다.
단계 단계 별로 가장 최적인 해를 구한다.
효율적이긴 하나 반드시 전체의 최적의 해를 구해준다는 보장은 없다.
1. 해 선택 (Selection Procedure) : 지금 가장 최적인 해를 구하여 부분해 집합에 추가한다.
2. 적절성 검사 (Feasibility Check) : 새로운 부분해 집합이 적절한지 검사한다.
3. 해 검사 (Solution Check) : 새로운 부분해 집합이 문제의 해가 되는지 검사한다. 그렇지 않을 경우 1번부터 반복한다.
탐욕 알고리즘의 대표적인 예로, 최소의 동전 수로 거스름돈 주기 문제가 있다.
거스름돈을 줄 때 최소의 동전 수로 거슬러 주도록 하는 문제이다.
예를 들어 동전이 1원, 5원, 10원짜리가 있다고 가정한다.
손님에게 14원의 동전을 거슬러 주어야 할 때,
10원 1개, 1원 4개 이렇게 거슬러 주는 것이 최소의 동전 수, 최선의 답이다.
이는 가장 큰 수의 동전으로 먼저 거슬러 주고 남은 돈을 다시 거슬러 줄 수 있는 동전 중 가장 큰 돈으로 거슬러 주는 식으로
최적 해를 구할 수 있다.
즉, 바로 지금 단계에서 가장 좋은 답인 가장 큰 동전으로 거슬러주고 남은 돈으로 같은 단계를 반복해 거쳐 나가면
최종적으로 가장 최선의 답을 찾는 것이다.
하지만, 만약 동전이 1원, 7원, 10원짜리 였을 경우
위와 같은 방법으로 거슬러 줄 시, 10원 1개, 1원 4개로 거슬러주게 될 것이다.
하지만 7원 2개로 거슬러 주는 것이 전체의 최적해이다.
여기서 유의해야 할 점은 매 순간마다 최선의 선택을 통해 나온 해가 반드시 전체의 최적해가 될 수는 없다는 것이다.
거스름돈 교환 문제의 경우 탐욕 알고리즘으로 문제를 풀려면, 동전의 단위가 배수를 이루어야 한다는 것이다.
그래야 큰 돈으로 거스르고 다음 돈을 다른 동전으로 거스를 때 예외가 생기지 않는다.
그리디 (탐욕)알고리즘의 응용으로는
다익스트라 최단 경로 알고리즘
최소 비용 신장 트리
배낭 채우기
문제 등이 있다.
최종적으로 정리를 하자면
정의 : 미리 정한 기준에 따라서 매번 가장 좋은 답, 최선의 답을 선택하는 알고리즘
최적화 문제를 푸는 데 사용, 단계 단계 별로 가장 최적인 해를 구한다.
주의 : 매 순간마다 최선의 선택을 하여 나온 해가 반드시 전체적인 최적해가 아닐 수도 있다.
따라서, 탐욕 알고리즘을 사용할 때에는 전체적인 최적해 인지를 항상 염두해어야 한다.
--> 탐욕 알고리즘을 사용하기 전에 검증 단계를 꼭 거쳐야 한다.