[자료구조/알고리즘]
Chapter - Greedy Algorithm
Greedy는 탐욕스러움 욕심이 많다는 뜻이다. Greedy Algorithm은 말 그대로 선택의 순간마다 당장에 보이는 최적의 상황을 찾아 최종적인 해답에 도달하는 방법이다.
Greedy Algorithm은
- 탐욕 선택 속성(Greedy choice property)
- 최적 부분 구조(optimal substructure)
특정을 갖는 문제들을 해결하는데 강점이 있다. 즉, 한번의 선택이 다음 선택에는 전혀 무관한 값이여야 하며 매 순간의 최적해가 문제에 대한 최적해여야 한다는 의미이다.
동전 거슬러주기 예시를 들 수 있겠다.
편의점에서 물건을 사고 가격이 4,040원이 나왔다. 계산을 위해 5,000원을 건내어 줬다면 동전의 개수를 최소한으로 받고 싶을 때, 어떻게 거슬러 받으면 될까?
이와 같은 설명을 단계로 설명하면,
- 선택 절차 : 거스름 돈의 동전갯수를 최대로 줄이기 위해 가장 가치가 높은 동전을 우선선택한다.
- 적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사한다. 초과하면 가장 마지막에 선택한 동전을 삭제하고 1번으로 돌아가 한 단계 작은 동전을 선택한다.
- 해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사한다. 액수가 부족하면 1번으로 돌아간다.
Greedy Algorithm으로 동전의 개수를 헤아리는 일은 우리가 일반적으로 거스름돈으로 동전을 선택하는 방법과 동일하다. 거스름돈 960원을 채우기 위해 먼저, 500원짜리 동전을 한 개 선택한다. 그 다음은 100원짜리 동전 4개, 50원짜리 한 개 10원까지 한 개를 선택할 것이다.
위와같이 탐욕 알고리즘(Greedy Algorithm)은 문제를 해결하는 과정에서 매 순간 최적이라 생각되는 해답을 찾으며 이를 토대로 해답에 도달하는 문제 해결방식이다.하지만 최적의 결과를 보장하지 못하는 경우도 있다.
예시 2번째
세기의 도둑 월급루팡은 도둑질은 잘하지만, 조금 멍청한 도둑이다. 월급루팡은 파브르 박물관에 전시 되어 있는 물건을 훔치려고 한다. 월급루팡은 항상 35kg의 무게를 들 수 있는 가방을 가지고 다니는데, 월급루팡이 최대한 많은 돈을 벌기 위해 가져갈 수 있는 금액은 얼마가 될까?
도둑이 Greedy Algorithm을 사용한다면 문제는 간단해진다.
- 가방에 넣을 수 있는 물건중 가장 비싼 물건을 넣는다.
- 그 다음으로 넣을 수 있는 물건중 가장 비싼 물건을 넣는다.
- 위의 과정을 반복한다.
월급루팡의 가방은 35kg까지 담을 수 있고 그림이 가장 비싸니 그림을 먼저 가방에 담을 수 있겠다. 하지만 그림을 넣는다면 남는 공간이 5kg밖에 남지 않아 더 이상 훔칠 수 있는 물건이 없어 총 3000$ 밖에 벌지 못한다. 만약 컴퓨터와 반지를 담았다면 3500$을 벌었을 것이다.
Greedy Algorithm은 이와 같이 항상 최적이라고 생각되는 해를 찾기 때문에 최적이라고 생각되는 값이 항상 최적의 결과를 보장하지는 못한다. 따라서 두 가지의 조건을 만족하는 "특정한 상황"이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다.
앞서 말했던 두가지 조건을 성립해야 최적의 해를 갖을 수 있다.
- 탐욕 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.
- 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.
