[패스트캠퍼스 :: 코딩테스트 인강] 12주차 ① 프림 알고리즘 개선 사항

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

 

최소 신장 트리의 이해 2 - 참고_개선된 프림 알고리즘

최소 신장 트리의 이해 2 - 개선된 프림 알고리즘의 시간 복잡도

백트래킹 - 백트래킹 기법의 이해

---

 

 

 

 

시간 복잡도

• 최악의 경우, while 구문에서 모든 간선에 대해 반복하고, 최소 힙 구조를 사용하므로 O(𝐸𝑙𝑜𝑔𝐸ElogE) 시간 복잡도를 가짐

 

 

개선된 프림 알고리즘

• 간선이 아닌 노드를 중심으로 우선순위 큐를 적용하는 방식
  • 초기화 - 정점:key 구조를 만들어놓고, 특정 정점의 key값은 0, 이외의 정점들의 key값은 무한대로 놓음. 모든 정점:key 값은 우선순위 큐에 넣음
  • 가장 key값이 적은 정점:key를 추출한 후(pop 하므로 해당 정점:key 정보는 우선순위 큐에서 삭제됨), (extract min 로직이라고 부름)
  • 해당 정점의 인접한 정점들에 대해 key 값과 연결된 가중치 값을 비교하여 key값이 작으면 해당 정점:key 값을 갱신
    • 정점:key 값 갱신시, 우선순위 큐는 최소 key값을 가지는 정점:key 를 루트노드로 올려놓도록 재구성함 (decrease key 로직이라고 부름)

• 개선된 프림 알고리즘 구현시 고려 사항
  • 우선순위 큐(최소힙) 구조에서, 이미 들어가 있는 데이터의 값 변경시, 최소값을 가지는 데이터를 루트노드로 올려놓도록 재구성하는 기능이 필요함
  • 구현 복잡도를 줄이기 위해, heapdict 라이브러리를 통해, 해당 기능을 간단히 구현

 

 

from heapdict import heapdict

def prim(graph, start):
    mst, keys, pi, total_weight = list(), heapdict(), dict(), 0
    for node in graph.keys():
        keys[node] = float('inf')
        pi[node] = None
    keys[start], pi[start] = 0, start

    while keys:
        current_node, current_key = keys.popitem()
        mst.append([pi[current_node], current_node, current_key])
        total_weight += current_key
        for adjacent, weight in mygraph[current_node].items():
            if adjacent in keys and weight < keys[adjacent]:
                keys[adjacent] = weight
                pi[adjacent] = current_node
    return mst, total_weight

mygraph = {
    'A': {'B': 7, 'D': 5},
    'B': {'A': 7, 'D': 9, 'C': 8, 'E': 7},
    'C': {'B': 8, 'E': 5},
    'D': {'A': 5, 'B': 9, 'E': 7, 'F': 6},
    'E': {'B': 7, 'C': 5, 'D': 7, 'F': 8, 'G': 9},
    'F': {'D': 6, 'E': 8, 'G': 11},
    'G': {'E': 9, 'F': 11}    
}
mst, total_weight = prim(mygraph, 'A')
print ('MST:', mst)
print ('Total Weight:', total_weight)

 

개선된 프림 알고리즘의 시간 복잡도: 𝑂(𝐸𝑙𝑜𝑔𝑉)O(ElogV)

• 최초 key 생성 시간 복잡도: 𝑂(𝑉)O(V)
• while 구문과 keys.popitem() 의 시간 복잡도는 𝑂(𝑉𝑙𝑜𝑔𝑉)O(VlogV)
  • while 구문은 V(노드 갯수) 번 실행됨
  • heap 에서 최소 key 값을 가지는 노드 정보 추출 시(pop)의 시간 복잡도: 𝑂(𝑙𝑜𝑔𝑉)O(logV)
• for 구문의 총 시간 복잡도는 𝑂(𝐸𝑙𝑜𝑔𝑉)O(ElogV)
  • for 구문은 while 구문 반복시에 결과적으로 총 최대 간선의 수 E만큼 실행 가능 𝑂(𝐸)O(E)
  • for 구문 안에서 key값 변경시마다 heap 구조를 변경해야 하며, heap 에는 최대 V 개의 정보가 있으므로 𝑂(𝑙𝑜𝑔𝑉)O(logV)일반적인 heap 자료 구조 자체에는 본래 heap 내부의 데이터 우선순위 변경시, 최소 우선순위 데이터를 루트노드로 만들어주는 로직은 없음. 이를 decrease key 로직이라고 부름, 해당 로직은 heapdict 라이브러리를 활용해서 간단히 적용가능

• 따라서 총 시간 복잡도는 𝑂(𝑉+𝑉𝑙𝑜𝑔𝑉+𝐸𝑙𝑜𝑔𝑉)O(V+VlogV+ElogV) 이며,
  • O(V)는 전체 시간 복잡도에 큰 영향을 미치지 않으므로 삭제,
  • E > V 이므로 (최대 𝑉2=𝐸V2=E 가 될 수 있음), 𝑂((𝑉+𝐸)𝑙𝑜𝑔𝑉)O((V+E)logV) 는 간단하게 𝑂(𝐸𝑙𝑜𝑔𝑉)O(ElogV) 로 나타낼 수 있음

 

 

 

 

 

 

---

 

 

 

 

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

 

 

 

 

 

 

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