패스트캠퍼스 챌린지 15일차

신장트리(Spanning Tree)

 -  그래프의 모든 노드가 연결되어 있으면서 트리의 속성을 만족하는 그래프

  - 사이클이 존재하지 않는다

최소 신장 트리(Minimum Spanning Tree, MST)

 - Spanning Tree 중에서, 간선의 가중치 합이 최소인 신장트리

 - 대표 최소 신장 알고리즘 : Kruskal's algorithm, Prim's algorithm

 

• 크루스칼 알고리즘(Kruskal's algorithm)

 - 탐욕 알고리즘 사용

 - 간선을 가장 작은 순서대로 정렬하여 선택, 사이클이 발생하면 탈락!

  

•  Union-Find 알고리즘

 - 노드들 중에 연결된 노드를 찾거나, 노드들을 서로 연결할 떄 사용

 - 각 개별의 집합을 묶어서 하나의 그래프로 만든다

 - 여러 노드가 존재할 떄, 두 개의 노드를 선택해서, 두 노드가 서로 같은 그래프에 속하는지 판별하기위해

   최상단 원소를 비교한다

 - 사이클 체크 확인에 사용된다.

 - 기법 : union-by-rank path compression => 시간 복잡도 O(1) 상수에 수렴

 

⁕ 개념을 한번 더 보고 나서 다시 코드로 실제 구현해보도록 하자

크루스칼 알고리즘 구현

 - 간선의 정보를 가지고 있는 Edge(값,노드1,노드2) 클래스 이용

 - 노드리스트와 간선 리스트를 가지고 크루스칼 알고리즘을 구현 

 - union-by-rank 기법으로 rank 정보를 사용 

 - path compression 기법으로 부모 노드를 찾아 리턴

 

 

시간 복잡도

 O(V) + O(ElogE) + O(E) => O(ElogE)

 

 

 

내용과 코드 둘다 잘 이해가 가지 않는 알고리즘이다..

탐욕알고리즘을 한번 더 본 후 union-by-rank, path compression 개념을 한번 더 찾아 정리한 후 

다시 알고리즘을 봐야 할듯 하다.

 

 

 

15일차 인증

 

 

 

 

 

 

본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.

https://bit.ly/37BpXiC

패스트캠퍼스 [직장인 실무교육]