Greedy Algorithm (탐욕 알고리즘, 그리디 알고리즘)

Greedy Algorithm은 해답에 포함될 원소들을 차례로 선택하는 과정을 거치게 되는데, 각 단계에서는 전체적인 상황을 종합적으로 판단하고, 고려하여 결정하는 것이아니라 현 시점의 정보를 바탕으로 가장 이익이 되는 원소들을 선택하는 방법이라고 할 수 있다.

복잡한 과정을 거치지 않고, 상황을 종합적으로 판단하는게 아니기 때문에 매우 빠른 알고리즘이라고 할 수 있다. 이러한 Greedy Algorithm은 '최적화 문제(optimization problem)'를 해결하기 위한 방법의 일환으로서, 예를들어 최소비용신장트리를 구하는 문제를 예로 들 수 있다.

주어진 문제에 대해 최적해를 구하는데 있어서, 문제가 부문제들로 쪼개지고, 그러한 각 부문제들의 최적해로부터 효율적으로 최적해를 구하게 될 때 Greedy Algorithm을 적용하는 것이다.

Greedy Algorithm은 최적해를 구하기 위해 다음 세 가지 작업을 수행한다.

1. 선택작업 : 현 상테에서 최적해에 포함시킬 대안을 선택

2. 타당성 조사 : 선택된 해가 주어진 문제의 조건을 만족하는지 검사

3. 해답 조사 : 원래의 문제가 해결되었는지를 조사

* Greedy Algorithm *

greedy_method(){

solution={};

while(condition){

s = select(); // 원소 s를 선택

if(feasible(s)){ // 원소 s 가 가능한 solution 이라면

solution = solution U {s}; // solution에 포함시킴

if(problem_solved(solution)) return solution; // 문제를 해결 했을 때 solution을 도출

}

}

}

Greedy Algorithm 예시

손님이 상점에서 물건을사고, 상점의 주인이 거스름돈을 내어주는 상황을 생각해 볼 때, 예를들어 570원을 거슬러주려면, 500원 동전 1개, 50원 동전 1개, 10원 동전 2개를 거슬러 주는 것이 최적해가 된다. 일상생활을 예시로 든거라 당연히 그렇게 생각 될 수 있겠지만, 천천히 살펴보자면

어떻게 하면 가장 적은 수의 동전을 거슬러 줄 수 있을지 생각해보자.

먼저, 가장 큰 액면을 가진 동전부터(현 시점에서 가장 이익이 되는 것, 욕심을 부림) 차례로 선택하여, 남은 액수보다 작을 경우 해답에 포함시키면 된다.

가장 액면이 큰 500원을 선택하고, 그다음 70원이 남았으므로, 그 다음 액면이 큰 100원은 선택할 수 없고, 50원 동전 1개를 선택한다. 20원이 남았으므로, 50원 짜리 동전은 선택할 수 없고, 그 다음 액면이 큰 10원 동전 2개를 차례로 선택하고, 잔액이 0원이 되면 종료가 된다.

Greedy Algorithm을 적용한 동전 거스름돈 알고리즘

// 거스름돈 액수를 입력받는다 (change), 출력은 동전 갯수 (solution)

int coin_change_making_GM(int change){

int solution = 0, coin = 500; // 최초의 동전은 500원 부터 시작 

while(true){

if(change >= coin){ // 거스름 돈 액수보다 동전이 작거나 같으면 solution

solution++;

change = change - coin;

if(change == 0) return solution; // 종료조건

}

else coin = select_next(coin); // 거스름 돈 액수보다 동전이 크면 다음 동전(ex 100원)으로 이동

}

}

하지만, 위에 적용한 Greedy Algorithm이 항상 최적의 해를 가지는 것은 아니다. 예를 들어 130원 짜리 동전을 한국은행에서 발행했다고 가정했을 때, 거스름돈이 150원 이라면 위의 알고리즘대로 적용하면, Solution = 3 (130원, 10원, 10원) 이 된다. 하지만 최적의 해는 Solution = 2 (100원, 50원) 이다. 그렇기 때문에 일반적인 동전 거스름돈 문제는 Greedy Algorithm을 적용하는 것이 아니라 나중에 살펴볼 DP(Dynamic Programming)을 사용하여 최적의 해를 구할 수 있다.

Greedy Algorithm을 사용하는 대표적인 알고리즘이 있다.

바로 '최소 신장 트리'이다.

신장트리란 주어진 연결그래프에서 사이클을 형성하는 간선을 제거하여 만든 트리이다. 그렇기 때문에 정점의 수가 n개 일 때, 간선의 수는 n-1개라는 특징을 가진다.

그래프는 사이클을 형성하는 간선이 존재하는 것이고,

신장트리는 사이클을 형성하는 간선이 존재하지 않는 트리이다.

이러한 신장트리는 여러 분야에 활용할 수 있는데, 모든 도시들을 연결하는 최소한의 도로망도 될 수 있다. 여기서 신장트리에서 비용(길이)을 최소화하여 모든 정점을 연결할 때 '최소 신장 트리'를 사용한다.

Greedy Algorithm의 대표적인 알고리즘 두가지가 있다.

1. Kruskal Algorithm ( 크루스칼 알고리즘)

2. Prim Algorithm ( 프림 알고리즘)

이 두가지는 다음 포스팅에서 살펴보도록 하겠다.