14. 탐욕 알고리즘 (Greedy Algorithm) - 1

  Greedy 알고리즘으로 많이 불리는 탐욕 알고리즘 역시 매우 자주 사용되는 알고리즘 중 하나입니다. Greedy알고리즘은 주로 최적화 문제에서 사용되고, 최적화 문제의 대표적 알고리즘 입니다. 이름에서도 알 수 있듯이 미래를 예측하지 않고, 순간마다 최선의 선택을 하는 방법입니다. 동적 프로그래밍의 경우가 데이터를 저장하고 문제를 풀어나가며 지속적으로 데이터를 참조합니다. 따라서, 매우 많은 동작이 발생합니다. 그렇기 때문에, 미래를 굳이 확인하지 않아도 직관적으로나, 논리적으로 현재의 선택이 최적화가 된다고 생각 될 때, 사용되는 알고리즘 입니다. 

  Greedy알고리즘의 최대 장점은 무엇보다도 빠르다는 것이며, 단점은 항상 최적화 되지 않는 다는 점입니다. 매번 최선의 선택을 해나가기에 문제를 푸는데 최소한의 노력을 하면 될 것입니다. 하지만, 미래에 대한 고려를 전혀 하지 않고 진행해야 하므로 구한 답이 최적이 아닐 가능성이 존재합니다. 앞에서도 설명했듯이 다익스트라 알고리즘 역시 대표적인 Greedy알고리즘 입니다.

  동적 프로그래밍에서 알아본 동전 문제도 Greedy알고리즘으로 풀 수 있습니다. 우리나라의 동전 체계처럼 하위 동전이 상위 동전의 약수인 경우(10원, 50원, 100원, 500원) Greedy 알고리즘으로 최적의 해를 구할 수 있습니다. 총 960원의 거스름돈을 주어야 한다면 500원 짜리부터 해를 구한다면 최소 거스름돈 동전 개수를 구할 수 있습니다.

  그렇다면 이제부터 Greedy시리즈에 대해 알아보도록 하겠습니다.

1. 프림 알고리즘(Prim's Algorithm)

  프림 알고리즘에 대해 알기 위해서 우선 최소 신장트리에 대해서 알아야 합니다. 최소 신장 트리 (MST, Minimun Spanning Tree)란 그래프 G에 있는 모든 정점을 포함하면서, 가중치 총 합이 가장 작은 트리를 만드는 것입니다. 아래와 같은 그래프가 있다고 가정 해봅시다.

  프림 알고리즘은 시작 정점인 1번으로부터 시작합니다. 만드려는 최소 신장 트리를 A트리라고 한다면 A에 정점 1만을 포함 시킵니다. 그리고 해당 트리 A로부터 각 정점들의 거리를 구합니다. 트리 A로부터의 각 간선 까지의 거리는 아래와 같습니다.

  2(정점: 1, 거리: 4), 3(정점: 1, 거리: 7), 4(정점: -,거리: -), 5(정점: -, 거리: -), 6(정점: -, 거리: -)

이 중에서 가장 거리가 가까운 2번 정점을 트리 A에 포함시킵니다.

  그 다음 트리 A로 부터의 각 정점의 거리를 다시 구합니다.

3(정점: 2, 거리: 1), 4(정점: 2,거리: 2), 5(정점: 2, 거리: 6), 6(정점: -, 거리: -)

  위에서 구한 트리 A로부터 가장 거리가 정점은 3번 정점이다.

 

  이런 과정을 반복하면 최소 신장 트리를 구할 수 있다.

4(정점: 2, 거리: 2), 5(정점: 2, 거리: 6), 6(정점: -, 거리: -)

 5(정점: 2, 거리: 6), 6(정점: 4, 거리: 5)

  6(정점: 4, 거리: 5)

  이 과정을 통해 최소 신장 트리를 구할 수 있다. 헤당 트리는 사이클이 존재하지 않는다. 시간 효율은 시작 정점에서 각 정점의 최단 거리를 알아내야 하므로 O(V^2)이 된다. 최소 신장트리에 대한 Pseudo Code는 아래와 같다.

2. 크루스칼 알고리즘 (Kruskal's Algorithm)

  이번에는 두 번째 그리디 알고리즘인 크루스칼 알고리즘에 대해 소개하겠습니다. 프림 알고리즘이 첫번째 정점을 바탕으로 MST를 만들어 내는 방법이라면, 크루스칼 알고리즘은 가장 짧은 간선을 바탕으로 MST를 찾아낸다. 전체 그래프에서 가장 짧은 간선을 우선 찾고, 하나씩 짧은 간선을 추가 하면서 MST를 만든다. 위에서 살펴본 그래프와 동일한 그래프의 MST를 크루스칼 알고리즘으로 구해보자.

크루스칼 알고리즘에서는 아래의 기준에 따라 간선을 선택하면 된다.

• 전체 정점의 개수 보다 한개 적게 간선을 선택해야한다.

• 간선을 선택했을때, 사이클이 만들어지면 안된다.

전체 그래프 중에서 가장 간선의 길이가 짧은 1(2, 3)을 선택한다.

이번엔 다음으로 짧은 간선인 2(2, 4)를 선택한다.

그 다음 짧은 간선인 4(1, 2)를 선택한다.

  그 다음은 5(6, 9)이다.

  이제 마지막 간선을 MST에 추가해야하는데, 가장 짧은 길이의 간선이 2개가 존재한다. 위와 같은 경우에는 크루스칼에서 정점의 숫자가 낮은 순서대로 추가가 된다. 따라서 6(2, 5)와 6(4, 5)중에서 앞의 간선이 선택된다.

  이 처럼 앞에서 구한 MST와 동일한 그래프가 나오게 된다. 크루스칼 알고리즘의 Pseudo Code는 아래와 같다.

  언뜻 보기에 크루스칼 알고리즘은 전체 간선의 길이만 검색할 수 있다면 쉽게 MST를 구할 수 있을것 같아 보인다. 하지만, 두번째 조건인 사이클 판별이 다소 어렵다. 그렇기에 실제로 걸리는 시간은 프림 알고리즘보다 더 많이 걸리게 된다. 시간 복잡도는 O(E log V)이다. 

  매우 기초적인 그리디 알고리즘 2가지를 배웠습니다. 내용이 너무 길어저 그리디 알고리즘에 대해서 두번의 파트로 나누어 설명할 계획입니다. 다음 시간엔 새로운 그리디 알고리즘을 소개하겠습니다.