15. 탐욕 알고리즘 (Greedy Algorithm) - 2

 이번 시간에는 두번째 그리디 알고리즘에 대해 배워보도록 하겠습니다. 지난 시간에 배웠던 알고리즘과 매커니즘 자체가 크게 차이가 나지 않으므로 각 알고리즘의 차이점에 대해 분석하면서 공부하는 것이 중요할 것입니다. 각각의 알고리즘의 풀이 순서와 결과 값이 매우 유사하므로(특히 그래프의 크기가 작다면) 차이점에 대해 더욱 주의깊게 살펴보아야 합니다.

1. 솔린 알고리즘 (Solin’s Algorithm)

  

 솔린 알고리즘은 한번의 단계에서 여러개의 간선을 선택하여 최소 신장 트리를 만들게 됩니다. 간선을 선택하는 기준은 다음과 같습니다.

• 1번 정점부터 다른 정점으로 연결되는 간선들 중 최소 간선을 선택한다.

• 중복된 선택은 제외한다.

• 모든 정점들이 연결된 하나의 트리로 완성되거나, 더이상 선택할 간선이 없을때까지 반복한다.

위 기준에 따라 정점들을 선택해보자.

첫 번째 단계에서 1번 정점부터 마지막 정점 까지 가장 가중치가 작은 간선을 골라나간다. 1번 정점에서 가장 가까운 정점은 2번 정점에 연결된 선이다.

4(1, 2)

그 다음 2번 정점에 연결된 최소 가중치인 3번 정점과 연결된 간선을 선택한다.

1(2, 3)

그 다음엔 3번 정점과 연결된 최소 가중치 간선을 찾아야 하나 이미 앞의 과정으로 해당 간선이 선택되었다. 그래서 다음인 4번 정점에 연결된 최소 가중치인 2번 정점과 연결된 간선을 선택한다.

2(4, 2)

5번 정점에서 연결된 최소 가중치 간선은 2개가 있는데 이 중 정점의 크기가 작은 2번 정점과의 간선을 선택한다.

6(5, 2)

마지막으로 정점 6번에 대한 최소 간선을 선택한다.

5(6,4)

이렇게 최소 신장트리가 완성되었습니다. 위의 그래프이 경우 첫번째 단계를 통해 최소 신장 트리가 만들어졌다.

솔린 알고리즘의 시간 복잡도는 인접 행렬을 이용하는 경우 O(V^2)이 되고 인접 리스트를 활용하는 경우 O(E log V)가 된다.

2. 벨만-포드 알고리즘 (Bellman-Ford’s Algorithm)

 벨만-포드 알고리즘은 간선에 음의 가중치가 포함된 경우 사용하는 알고리즘입니다. 앞서 배운 Dijkstra 알고리즘과 유사하나, 음의 가중치가 포함된 경우에도 문제를 해결할 수 있도록 설계되었습니다.

 벨만-포드 알고리즘의 이동방향 결정 방법은 다음과 같습니다.

• 첫번째 정점을 0으로 하고, 모든 정점에 무한대 값이 있다고 가정한다.

• 다음 간선을 이동할 때, 간선에 적혀져 있는 만큼 다음값을 입력한다.

• 해당 간선에 있는 숫자가 작은경우 그대로 유지하고, 큰 경우 새로 간선의 숫자를 바뀐다.

 역시 글로 설명하면 다소 이해가 어려울 수 있으나 아래 그림을 이용해 더 자세히 알아보자. 벨만포드 알고리즘의 경우 기존의 알고리즘과는 조금 다르기 때문에 새로운 그래프로 진행하겠습니다.

벨만-포드 알고리즘의 설명을 돕기위해 방향성이 존재하고 음의 가중치가 있는 그래프로 바꿔 설명하도록 하겠습니다. 시작점을 0으로 설정하고 나머지 정점에는 무한대의 값을 넣습니다.

첫 번째 정점을 기준으로 다음 정점으로 이동할 때 가중치를 반영하여 다음 정점을 입력합니다. 따라서 위에 있는 정점은 14, 아래에 있는 정점은 25가 들어가게 됩니다.

  이제 연결된 정점으로 부터 다음에 이어진 정점들을 구합니다. 만약 두 정점으로 동시에 이동하는 경우 두 정점 중 너 낮은 값을 넣습니다.

 

  두 번쨰 연결된 정점을 기준으로 다음 정점으로 이동합니다. 앞의 방법과 동일하게 진행합니다. 

마지막으로 모든 정점에 대한 거리를 구하면 완성됩니다.

벨만-포드 알고리즘의 경우 음의 가중치가 포함되어있는 그래프에서 최단거리를 구하는데 매우 효과적입니다. 시간복잡도는 O(VE)입니다.

두 시간에 걸쳐 탐욕 알고리즘에 대해 배우게 되었습니다. 이제 알고리즘 이론에 대한 큰 설명들은 모두 끝났고 남은 시간에는 주요 알고리즘을 살펴보는 소개하도록하겠습니다.