[패스트캠퍼스 수강 후기] {코딩테스트인강} 100% 환급 챌린지 33회차 미션

- union-by-rank 와 path compression 기법 사용시 시간 복잡도는 다음 계산식을 만족함이 증명되었음

  -  O(M log^*{N})

  -  log^*{N}  은 다음 값을 가짐이 증명되었음

    - N이 2^{65536}  값을 가지더라도, log^*{N}  의 값이 5의 값을 가지므로, 거의 O(1), 즉 상수값에 가깝다고 볼 수 있음

 

 

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

mygraph = {

    'vertices': ['A', 'B', 'C', 'D', 'E', 'F', 'G'],

    'edges': [

        (7, 'A', 'B'),

        (5, 'A', 'D'),

        (7, 'B', 'A'),

        (8, 'B', 'C'),

        (9, 'B', 'D'),

        (7, 'B', 'E'),

        (8, 'C', 'B'),

        (5, 'C', 'E'),

        (5, 'D', 'A'),

        (9, 'D', 'B'),

        (7, 'D', 'E'),

        (6, 'D', 'F'),

        (7, 'E', 'B'),

        (5, 'E', 'C'),

        (7, 'E', 'D'),

        (8, 'E', 'F'),

        (9, 'E', 'G'),

        (6, 'F', 'D'),

        (8, 'F', 'E'),

        (11, 'F', 'G'),

        (9, 'G', 'E'),

        (11, 'G', 'F')

    ]

}

 

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

 

kruskal(mygraph)

[ (5, ‘ A ‘, ‘D’ ) , ( 5, ‘C’, ‘E’ ) , ( 6, ‘D’, ‘F’ ), ( 7, ‘A’, ‘B’) , (7, ‘B’, ‘E’), (9, ‘E’, ‘G) ]

 

 

7. 시간 복잡도

- 크루스컬 알고리즘의 시간 복잡도는 O(E log E)

  - 다음 단계에서 2번, 간선을 비용 기준으로 정렬하는 시간에 좌우됨 (즉 간선을 비용 기준으로 정렬하는 시간이 가장 큼)

  1. 모든 정점을 독립적인 집합으로 만든다.

  2. 모든 간선을 비용을 기준으로 정렬하고, 비용이 작은 간선부터 양 끝의 두 정점을 비교한다.

     - 퀵소트를 사용한다면 시간 복잡도는 O(n log n) 이며, 간선이 n 이므로 O(E log E)

  3. 두 정점의 최상위 정점을 확인하고, 서로 다를 경우 두 정점을 연결한다. (최소 신장 트리는 사이클이 없으므로, 사이클이 생기지 않도록 하는 것임)

     - union-by-rank 와 path compression 기법 사용시 시간 복잡도가 결국 상수값에 가까움, O(1)

 

 

강의에 대해 정확하게 알고 싶다면 

https://bit.ly/2FgOONG