[알고리즘] CHAP 4. The Greedy Approach (탐욕알고리즘) - Prim's alg (프림알고리즘)

이번 챕터에서는 탐욕알고리즘과 이를 이용하는 프림, 크루스칼, 다익스트라 알고리즘을 정리해보려고 한다. 한 게시물에 정리하기에는 내용이 너무 많아서 나눠서 정리할 예정이다. 목차는 다음과 같다.

 

• Greedy Approach (GA, 탐욕 알고리즘)
• Minimum Spanning Tree (MST, 최소 신장 트리)
• GA - 1. Prim's algorithm (프림 알고리즘)

---

1. Greedy Approach (탐욕 알고리즘)

동적 프로그래밍이 작게 쪼개고 재귀를 통해 작은 것들부터 해결해나가는 기법이었다면, 탐욕 알고리즘은 작게 나누지 않고 그때그때 탐욕스러운 (가장 이익이 되는) 선택을 해나가는 알고리즘이다.  접근 방식은 다음과 같다.

 

선택 과정

가장 가까운 노드들 중에서 현재 고려사항을 최고로 만족시키는 탐욕스러운 기준으로 선택한다

 

타당성 확인 (feasible)

실행가능여부를 체크한다 (해결하는 문제마다 다를 것)

 

솔루션 체크

선택한 것이 타당성 여부도 통과되었다면 결정한다

 

이해가 어렵다면 예시를 한 개 들어보자

 

Ex ) Coin Change problem -> 동전 개수를 최소화 하여 원하는 금액을 만드는 문제이다

우리에게 25센트 동전 1개, 10센트 2개, 5센트 1개, 1센트 2개가 있다고 가정하자. 이 동전으로 36센트를 만들려고 한다. 동전개수를 최소화 하려면 액수가 큰 동전을 먼저 선택하는게 유리할 것이다.

 

step 1. 25c 1개 선택 - 남은 금액 : 11

step 2. 10c 1개 선택 - 남은 금액 : 1

step 3. 10c 1개 선택 - > not feasible (액수를 넘어가므로 타당하지 않다)

step 4. 5c 1개 선택 - > not feasible (step 3과 같은 이유로 타당하지 않다)

step 5. 1c 1개 선택 - > 남은 금액 : 0 

 

따라서 최적의 선택은 동전 3개를 선택하는 것이다

 

탐욕 알고리즘은 이 자체로 최적의 솔루션인 것은 아니다. 따라서 이 알고리즘을 설계할 때 최적화 증명은 필수적이다.

 

Greedy Approach 종류

탐욕 알고리즘의 종류에는 프림, 크루스칼, 다익스트라 등의 알고리즘이 있다. 

 

---

2. Minimum Spanning tree problem (최소 신장 트리)

최소신장트리는 앞서 설명한 탐욕알고리즘을 이용해 찾아낼 수 있다. 그럼 최소신장트리는 무엇일까?

 

최소신장트리는 그래프의 일종으로 다음과 같은 특징을 갖는 그래프이다.

• Undirected graph (무방향그래프)
• Connected graph (연결그래프) - 모든 노드들이 서로 연결되어있어야 한다.
• Weighted graph (가중치그래프) 
• Acycle graph (순환이 존재하지 않는 그래프)

여기서 Subgraph가 등장하는데 이는 원래 그래프의 일부 노드와 간선으로 이루어진 그래프라고 보면 된다. 

G' = (V', E'), V' ⊆ V, E' ⊆ E

 

왼 : 원래 그래프 / 오 : 최소신장트리

 

순환이 없을 뿐이지 모든 노드가 연결되어야 한다는 것에 주의하자

---

3. Prim's algorithm (프림 알고리즘)

프림 알고리즘은 임의의 시작 정점에서 가장 가까운 정점을 하나씩 추가하여 최소신장트리(MST)를 만들어가는 알고리즘이다. 

 

가장 가까운 정점 중에서 가중치가 작은 것을 선택하되, 순환이 되지 않도록 하면 된다!

 

# Code

import sys

N = 7 // 노드개수
s = 0 // 스타트노드의 인덱스
visited = [False] * N // 방문여부 확인
D = [sys.maxsize] * N  // 처음에 리스트를 무한대로 세팅
D[s] = 0
previous = [None] * N   // 트리 간선 추출 위함
previous[s] = s

g = [None] * N

for k in range(N) :
	m = -1
    min_val = sys.maxsize
    
    for j in range(N) :
    	if not visited[j] and D[j] < min_val :
        	min_val = D[j]
            m = j
    visited[m] = True
    
    for w, wt in list(g[m]) :
    	if not visited[w] :
        	if wt < D[w] :
            	D[w]=  wt
                previous[w] = m

 

여기서 g에 배열을 넣는데, g[0] = [(1,9), (2,10)] 이런식으로 넣게 된다. 의미는 0번 노드에 연결된 노드는 가중치가 9인 1번노드, 가중치가 10인 2번노드 라는 의미이다.

---

 

# 실행예시

 

 

---

이렇게 탐욕알고리즘과 프림에 대한 정리 끝! 😊