[패스트캠퍼스 :: 코딩테스트 인강] 11주차 ① 크루스칼 알고리즘

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

 

최소 신장 트리의 이해 1 - Union_Find 알고리즘

최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 1. Path

최소 신장 트리의 이해 1 - 크루스칼 알고리즘 코드 작성 - 2. Union_by_rank

 

---

 

 

 

 union-by-rank 기법

• 각 트리에 대해 높이(rank)를 기억해 두고,
• Union시 두 트리의 높이(rank)가 다르면, 높이가 작은 트리를 높이가 큰 트리에 붙임 (즉, 높이가 큰 트리의 루트 노드가 합친 집합의 루트 노드가 되게 함)

 

 

높이가 h - 1 인 두 개의 트리를 합칠 때는 한 쪽의 트리 높이를 1 증가시켜주고, 다른 쪽의 트리를 해당 트리에 붙여줌

 

 

 

• 초기화시, 모든 원소는 높이(rank) 가 0 인 개별 집합인 상태에서, 하나씩 원소를 합칠 때, union-by-rank 기법을 사용한다면,
  • 높이가 h 인 트리가 만들어지려면, 높이가 h - 1 인 두 개의 트리가 합쳐져야 함
  • 높이가 h - 1 인 트리를 만들기 위해 최소 n개의 원소가 필요하다면, 높이가 h 인 트리가 만들어지기 위해서는 최소 2n개의 원소가 필요함
  • 따라서 union-by-rank 기법을 사용하면, union/find 연산의 시간복잡도는 O(N) 이 아닌, 𝑂(𝑙𝑜𝑔𝑁)O(logN) 로 낮출 수 있음

 

path compression

• Find를 실행한 노드에서 거쳐간 노드를 루트에 다이렉트로 연결하는 기법
• Find를 실행한 노드는 이후부터는 루트 노드를 한번에 알 수 있음

 

 

 

 

• union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음
  • 𝑂(𝑀𝑙𝑜𝑔∗𝑁)O(Mlog∗N)
  • 𝑙𝑜𝑔∗𝑁log∗N 은 다음 값을 가짐이 증명되었음
    • N이 265536265536 값을 가지더라도, 𝑙𝑜𝑔∗𝑁log∗N 의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음

 

 

크루스칼 알고리즘 (Kruskal's algorithm) 코드 작성

 

 

parent = dict()
rank = dict()


def find(node):
    # path compression 기법
    if parent[node] != node:
        parent[node] = find(parent[node])
    return parent[node]


def union(node_v, node_u):
    root1 = find(node_v)
    root2 = find(node_u)
    
    # union-by-rank 기법
    if rank[root1] > rank[root2]:
        parent[root2] = root1
    else:
        parent[root1] = root2
        if rank[root1] == rank[root2]:
            rank[root2] += 1
    
    
def make_set(node):
    parent[node] = node
    rank[node] = 0

def kruskal(graph):
    mst = list()
    
    # 1. 초기화
    for node in graph['vertices']:
        make_set(node)
    
    # 2. 간선 weight 기반 sorting
    edges = graph['edges']
    edges.sort()
    
    # 3. 간선 연결 (사이클 없는)
    for edge in edges:
        weight, node_v, node_u = edge
        if find(node_v) != find(node_u):
            union(node_v, node_u)
            mst.append(edge)
    
    return mst

 

시간 복잡도

• 크루스컬 알고리즘의 시간 복잡도는 O(E log E)
  • 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨 (즉 간선을 비용 기준으로 정렬하는 시간이 가장 큼)
  • 모든 정점을 독립적인 집합으로 만든다.
  • 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.
    • 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)
  • 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)
    • union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

 

 

 

 

 

 

 

---

 

 

 

 

 

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

 

 

 

 

 

 

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