Greedy의 사전적 정의는 "탐욕스러운, 욕심 많은" 이란 뜻을 지니고 있습니다. 말 그대로 탐욕 알고리즘은 결정의 순간마다 당장 눈앞에 보이는 최적의 상황만을 탐욕적으로 쫓아 최종적인 해답에 도달하는 방법입니다. 이러한 탐욕 알고리즘의 문제 해결법을 보다 단계적으로 나누어 본다면 다음과 같을 것입니다.
선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택합니다.
적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사합니다.
해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 1번으로 돌아가 위의 과정을 반복합니다.
이러한 탐욕 알고리즘을 우리가 흔히 겪을 수 있는 사례에 적용해 볼까요?
김코딩은 오늘도 편의점에서 열심히 아르바이트하고 있습니다. 손님으로 온 박해커는 과자와 음료를 하나씩 집어 들었고, 물건 가격은 총 4,040원이 나왔습니다. 박해커는 계산을 하기 위해 5,000원을 내밀며, 거스름돈은 동전의 개수를 최소한으로 하여 거슬러 달라고 하였습니다.
이때 김코딩은 어떻게 거슬러 주어야 할까요? 김코딩의 입장에 탐욕 알고리즘의 문제 해결 과정을 적용하면 아래와 같이 문제를 단계화할 수 있습니다.
선택 절차 : 거스름돈의 동전 개수를 줄이기 위해 현재 가장 가치가 높은 동전을 우선 선택합니다.
적절성 검사 : 1번 과정을 통해 선택된 동전들의 합이 거슬러 줄 금액을 초과하는지 검사합니다. 초과하면 가장 마지막에 선택한 동전을 삭제하고, 1번으로 돌아가 한 단계 작은 동전을 선택합니다.
해답 검사 : 선택된 동전들의 합이 거슬러 줄 금액과 일치하는지 검사합니다. 액수가 부족하면 1번 과정부터 다시 반복합니다.
이 과정을 통해 얻은 문제에 대한 해답은 다음과 같습니다.
가장 가치가 높은 동전인 500원 1개를 먼저 거슬러 주고 잔액을 확인한 뒤, 이후 100원 4개, 50원 1개, 10원 1개의 순서대로 거슬러 줍니다.
한 가지 예제를 더 살펴봅시다.
시장 최나무는 도시 내의 모든 동을 연결하는 새로운 도로의 건설을 계획하고 있습니다. 각 동과 동을 연결하는 도로 건설 비용은 아래와 같으며, 예산의 한계 때문에 최소의 비용으로 건설하려 합니다. 최나무는 어떻게 도로 설계를 해야 할까요?
단, 세 개 이상의 동을 순환(cycle)하는 도로는 건설하지 않습니다.
이 문제에 다시 한번 탐욕 알고리즘의 문제 해결 과정을 적용해 보겠습니다.
선택 절차 : 건설 비용이 저렴한 도로부터 선택합니다. 단, 최소 비용을 구해야 하니 선택 전에 비용 순으로 오름차순 목록을 만들고 시작합니다.
적절성 검사 : 순환 여부를 검사합니다. 순환한다면 가장 마지막에 선택된 도로를 삭제하고 1번으로 돌아가 직전 선택보다 한 단계 비싼 도로를 선택합니다.
해답 검사 : 선택된 도로들이 모든 동을 연결하는지 검사합니다. 연결되지 않은 동이 있다면 1번 과정부터 다시 반복합니다.
이 선택과 검사를 하는 일련의 과정을 표로 만들어 보면 다음과 같습니다.
최초에 건설 비용을 오름차순으로 정리하는 과정이 추가되었지만, 현재 상태의 최적의 선택(최소 비용)-적절성 검사(순환 여부)-해답 검사(모두 연결)라는 탐욕 알고리즘의 풀이 과정을 통해 해결할 수 있었습니다. 이 문제는 도로를 건설하는데 드는 최소 비용을 구하는 문제였지만 사실은 최소비용 신장 트리(Minimum Spanning Trees)를 만드는 문제였고, 풀이는 Kruskal 알고리즘을 이용한 것입니다.
이처럼 탐욕 알고리즘은 기준에 따라 좋은 것을 선택하는 알고리즘이므로 그래프나 정렬, 유명한 다익스트라(Dijkstra) 알고리즘까지 폭넓은 영역에서 사용됩니다.
최소비용 신장 트리 : 그래프 내의 모든 정점을 최소 비용으로 연결하는 트리
Kruskal 알고리즘 : 최소비용 신장 트리를 만드는 알고리즘 중 탐욕 알고리즘을 이용한 풀이
마지막으로 한가지 예시만 더 살펴보겠습니다.
김코딩이 아르바이트를 하러 간 사이 안타깝게도 김코딩의 집에 도둑이 들었습니다. 도둑의 가방은 35kg까지만 물건을 담을 수 있으며, 김코딩의 집에는 4개의 물건이 있습니다.
도둑이 탐욕 알고리즘을 사용한다면 문제는 다음과 같이 간단해집니다.
1. 가방에 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다.
2. 그다음으로 넣을 수 있는 물건 중 가장 비싼 물건을 넣습니다. 이 과정을 반복합니다.
도둑의 가방은 35kg까지 담을 수 있고, 그림이 가장 비싸니 그림을 먼저 훔치겠죠. 남는 공간이 5kg밖에 안 되니 이제 더는 훔칠 수 있는 물건은 없고, 훔친 물건의 총 가치는 $3,000입니다. 하지만 만약 그림 대신 컴퓨터와 반지를 훔쳤다면 어떨까요? 35kg 이 넘지 않으면서 총 가치는 $3,500으로 최적의 해답이 됩니다.
탐욕 알고리즘은 문제를 해결하는 과정에서 그 순간순간마다 최적이라 생각되는 해답(locally optimal solution)을 찾으며, 이를 토대로 최종 문제의 해답(globally optimal solution)에 도달하는 문제 해결 방식입니다. 하지만 도둑의 예와 같이 항상 최적의 결과를 보장하지는 못한다는 점을 명심해야 합니다.
따라서 탐욕 알고리즘을 사용하려면 문제가 아래의 2가지 조건을 성립하여야 잘 작동합니다. 즉, 아래의 조건을 만족하는 "특정한 상황" 이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못합니다.
탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않습니다.
최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성됩니다.
항상 최적의 결과를 도출하는 것은 아니지만 어느 정도 최적해에 근사한 값을 빠르게 도출할 수 있는 장점이 있기 때문에 근사 알고리즘으로 사용이 가능합니다.
