[패스트캠퍼스 :: 코딩테스트 인강] 11주차 ② 프림 알고리즘

알고리즘/기술면접 완전 정복 올인원 패키지 Online

 

최소 신장 트리의 이해 2 - 프림 알고리즘이란

최소 신장 트리의 이해 2 - 프림 알고리즘 코드 작성

최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 1

최소 신장 트리의 이해 2 - 프림 알고리즘 파이썬 코드 - 2

 

---

 

 

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

• 대표적인 최소 신장 트리 알고리즘
  • Kruskal’s algorithm (크루스칼 알고리즘), Prim's algorithm (프림 알고리즘)
• 프림 알고리즘
  • 시작 정점을 선택한 후, 정점에 인접한 간선중 최소 간선으로 연결된 정점을 선택하고, 해당 정점에서 다시 최소 간선으로 연결된 정점을 선택하는 방식으로 최소 신장 트리를 확장해가는 방식
• Kruskal's algorithm 과 Prim's algorithm 비교
  • 둘다, 탐욕 알고리즘을 기초로 하고 있음 (당장 눈 앞의 최소 비용을 선택해서, 결과적으로 최적의 솔루션을 찾음)
  • Kruskal's algorithm은 가장 가중치가 작은 간선부터 선택하면서 MST를 구함
  • Prim's algorithm은 특정 정점에서 시작, 해당 정점에 연결된 가장 가중치가 작은 간선을 선택, 간선으로 연결된 정점들에 연결된 간선 중에서 가장 가중치가 작은 간선을 택하는 방식으로 MST를 구함

 

 

1. 임의의 정점을 선택, '연결된 노드 집합'에 삽입
2. 선택된 정점에 연결된 간선들을 간선 리스트에 삽입
3. 간선 리스트에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리'에 삽입
4. 추출한 간선은 간선 리스트에서 제거
5. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

 

 

 

 

 

 

heapq 라이브러리 활용을 통해 우선순위 큐 사용하기

• heapq.heappush를 통해 데이터를 heap 형태로 넣을 수 있음 (0번 인덱스를 우선순위로 인지함)

 

import heapq

queue = []
graph_data = [[2, 'A'], [5, 'B'], [3, 'C']]

for edge in graph_data:
    heapq.heappush(queue, edge)
    
for index in range(len(queue)):
    print (heapq.heappop(queue))

print (queue)

 

collections 라이브러리의 defaultdict 함수 활용하기

• defaultdict 함수를 사용해서, key에 대한 value를 지정하지 않았을 시, 빈 리스트로 초기화하기

 

 

from collections import defaultdict

list_dict = defaultdict(list)
print (list_dict['key1'])

 

 

프림 알고리즘 파이썬 코드

1. 모든 간선 정보를 저장 (adjacent_edges)
2. 임의의 정점을 선택, '연결된 노드 집합(connected_nodes)'에 삽입
3. 선택된 정점에 연결된 간선들을 간선 리스트(candidate_edge_list)에 삽입
4. 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출해서,
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 이미 들어 있다면, 스킵함(cycle 발생을 막기 위함)
   • 해당 간선에 연결된 인접 정점이 '연결된 노드 집합'에 들어 있지 않으면, 해당 간선을 선택하고, 해당 간선 정보를 '최소 신장 트리(mst)'에 삽입
     • 해당 간선에 연결된 인접 정점의 간선들 중, '연결된 노드 집합(connected_nodes)' 에 없는 노드와 연결된 간선들만 간선 리스트(candidate_edge_list) 에 삽입
       • '연결된 노드 집합(connected_nodes)' 에 있는 노드와 연결된 간선들을 간선 리스트에 삽입해도, 해당 간선은 스킵될 것이기 때문임
       • 어차피 스킵될 간선을 간선 리스트(candidate_edge_list)에 넣지 않으므로 해서, 간선 리스트(candidate_edge_list)에서 최소 가중치를 가지는 간선부터 추출하기 위한 자료구조 유지를 위한 effort를 줄일 수 있음 (예, 최소힙 구조 사용)

1. 선택된 간선은 간선 리스트에서 제거
2. 간선 리스트에 더 이상의 간선이 없을 때까지 3-4번을 반복

 

 

 

from collections import defaultdict
from heapq import *

def prim(start_node, edges):
    mst = list()
    adjacent_edges = defaultdict(list)
    for weight, n1, n2 in edges:
        adjacent_edges[n1].append((weight, n1, n2))
        adjacent_edges[n2].append((weight, n2, n1))

    connected_nodes = set(start_node)
    candidate_edge_list = adjacent_edges[start_node]
    heapify(candidate_edge_list)
    
    while candidate_edge_list:
        weight, n1, n2 = heappop(candidate_edge_list)
        if n2 not in connected_nodes:
            connected_nodes.add(n2)
            mst.append((weight, n1, n2))
            
            for edge in adjacent_edges[n2]:
                if edge[2] not in connected_nodes:
                    heappush(candidate_edge_list, edge)

    return mst

 

 

 

 

---

 

 

 

이제 챌린지도 마지막 한주가 남았다..!

 

아직 강의는 많이 남았지만, 

자격증 시험, 상반기 공채와 함께 5월까지 달려왔다.

 

 

아직은 좋은 소식이 없지만,

계속 열심히 하다보면 때가 오겠지.

 

 

 

[패스트캠퍼스 100% 환급 챌린지 미션 중입니다.]

 

 

 

 

 

 

 

알고리즘 / 기술면접 완전 정복 올인원 패키지 Online. | 패스트캠퍼스