Greedy 알고리즘 디자인 패턴은 최적의 해결책을 얻을 때까지 일련의 행동을 따르며
각 순간 가장 최적의 해답을 찾음으로써 최적의 해에 근사하는 알고리즘이다.
MST [minimum spanning tree] 문제 해결 알고리즘 Prim Greedy Algorithm을 보자.
- 공집합 F, Y를 준비한다.
- MST를 찾으려고 하는 그래프 G [V, E]에서 vertex 하나를 집합 Y의 원소로 한다.
- 집합 X = V - Y의 vertex들에서 Y의 원소들과 연결된 것 중 edge weight가 가장 낮은 것을 선택한다.
- 해당 vertex를 Y원소로 한다. 그리고 해당 edge를 F의 원소로 한다.
- 2, 3, 4번을 Y = V가 될때까지 반복한다.
- MST G[Y, F]를 구한다.
처음 선택한 vertex에 따라서 서로 다른 sub graph를 결과로 할 수는 있지만
MST를 획득한다는 관점에서는 잘 작동한다.
이번에는 0-1 knapsack problem을 보도록 하자.
물건 3개가 다음과 같다.
(P_1=[$50,5kg], P_2=[$60,10kg], P_3=[$140,20kg])
그리고 가방에 담을 수 있는 최대 무게가 30kg이라고 하자.
이때, 알고리즘을 다음과 같이 생각해 보자.
- 단위 무게당 가격이 높은 물건을 가방에 넣는다.
- 1번을 최대 무게를 초과하기 전까지 반복한다.
단위 무게당 가격이 가장 높은 물건은 첫 번째 물건이므로 1번 물건을 가방에 넣는다.
그리고 그다음 가격이 높은 3번 물건을 가방에 넣으면 남은 무게는 5kg이므로
알고리즘은 종료되고 결과는 $190이다.
하지만 이 문제는 2번, 3번 물건을 가방에 넣는 것이 $200로 최적의 답이다.
이렇듯 이 문제는 매 순간 가장 최적의 선택을 한다는
greedy choice property를 만족하지 못한다고 볼 수 있겠다.
문제를 해결하기 위해 알고리즘을 고안할 때, Greedy algorithm을 적용하려면
substructure의 선택들을 통해 문제의 최적의 해답을 찾을 수 있는
optimal substructure을 만족하는지 생각해보아야 한다.