Greedy algorithm(탐욕 알고리즘)/ Minimum spanning tree(최소 신장 트리)

Greedy algorithm(탐욕 알고리즘)

Greedy algorithm은 그 당시 "가장 최고"라고 생각되는 것을 선택한다. 각 선택은 지역적으로 최적(locally optimal)이 되는 것이다. 하지만 그 것이 전체적으로 최적(globally optimal)이 아닐 수 있다. 따라서 알고리즘이 정말로 최적의 답을 주는지 체크해야 한다.

 

Greedy algorithm을 해결하는 방법은 총 세 가지의 단계로 이루어진다.

1. 선택과정

: 지역적으로 가장 최선의 선택을 한다.

2. 적정성 검사

: 그 선택이 문제의 조건을 벗어나지 않는 지 확인한다.

3. 해답검정

: 방금 한 선택으로 문제가 해결되었는지 확인한다.

 

이렇게만 설명을 하면 감이 오지 않을 수 있으니 예시를 함께 보자.

가령 500원, 100원, 50원, 10원을 가지고 900원을 만들고자 할때 동전의 개수가 최소가 되는 경우를 생각해보자.

 

위의 예시를 이용하여 greedy algorithm을 해결하는 방법을 알아보자.

1. 선택 과정

: 지금 할 수 있는 가장 최선의 선택을 한다. 이 경우에는 500원을 선택하는 것이 가장 탐욕적이라 할 수 있다.

2. 적정성 검사

: 두 번째 동전을 고를 때에도 500원을 선택하고 싶지만, 이번에는 "적정성 검사"에서 막히게 된다. 500원을 2개 선택하게 되면 문제에 제시된 900원이라는 조건을 어기게 되기 때문이다. 그렇기 때문에 그 다음으로 100원을 선택할 수 있다. 이 과정을 반복한다.

3. 해답검정

: 100원짜리를 4번 선택하게 되면 금액이 총 900원이 되어 해답이 완성된다. 이 경우에 멈추면 된다. 결과적으로 500원짜리 1개와 100원짜리 4개 총 5개의 동전을 이용하여 900원을 만드는 것이 최적이라는 결론에 이르게 된다.

 

Greedy Algorithm은 그 순간마다 최적이라고 생각되는 답을 선택한뒤 그것이 조건에 적절한 것인지 판단하면서 해결해 나아가면된다. 비록 이 알고리즘을 통해 구한 답이 최적이 아닌 경우도 있지만, 많은 경우에 greedy algorithm은 효율적이며 직관적으로 해법을 제시한다.

 

Minimum spanning tree(최소 신장 트리)

최소 신장 트리가 무엇인지 공부하기에 앞서, 먼저 "가중치가 있는 연결된 무향 그래프" 하나를 살펴보자.

가중치가 있는 연결된 무향 그래프 G

"가중치가 있는 연결된 무향 그래프"라는 말이 조금 복잡해 보일 수 있지만 그림과 함께 보면 금방 이해가 갈 것이다. 조금 주의할 것이 있다면 "연결된" 그래프는 한 vertex에서 다른 vertex로 이동할 길이 있어야 한다는 것이다. 따라서 (v1, v3)을 잇는 edge가 지워진다해도 여전히 "연결된" 그래프라고 할 수 있지만, (v1, v3)과 (v1, v2)가 모두 지워진다면 v1에서 다른 vertex로 가는 길이 사라지기 때문에 "비연결된" 그래프가 되고 만다.

 

위의 그래프와 조금 친숙해졌다면, 신장 트리에 대해 알아보자. 트리의 속성 중 하나는 순환하지 않는다는 것이다. 이 속성만 안다면 신장 트리에 대해 쉽게 이해할 수 있다. 위 그래프 G는 순환하는 그래프이다. 따라서 G에서 몇개의 edge를 제거하여 트리를 만들어 주면 된다. 그것이 바로 신장트리(spanning tree)가 된다.  아주 쉽게 머릿속에  신장트리 하나씩 그려볼 수 있을 것이다.  

그래프 G에서 얻은 신장트리들

위의 그림은 그래프 G에서 구해낸 신장트리들이다. 몇 개의 edge를 제거해 순환하는 지점을 없애주었다. 여기에서 최소 신장 트리의 개념까지 나아가보자. 

최소신장트리(minimum spanning tree)는 하나의 그래프에서 만들 수 있는 신장 트리들 중에서 가중치의 합이 가장 작은 것을 말한다.

 

그래프 G는 그래프를 이루고 있는 vertex의 집합 V와 edge의 집합 E로 나타낼 수 있다. 이걸 G=(V,E)라고 표기하자.

그렇다면 G의 신장트리인 T는 어떨까? T는 G와 똑같은 vertex 집합을 가져야 하므로 마찬가지로 V라고 표기한다. 그리고 T의 edge는 E에서 몇 개를 제거한 것에 불과하기 때문에 E의 부분집합이라고 할 수 있다. 이 부분집합을 F라고 하자. 그러면 T=(V,F)로 표기할 수 있다. 우리의 목표는 최소신장트리가 되는 F의 집합을 찾아내는 것이다.

 

최소신장 트리를 만드는 방법에는 프림 알고리즘과 크루스칼 알고리즘이 있다. 앞으로 두 개념들을 살펴 볼 것이다.