카테고리 없음
[삼성SDS] 24년 하반기 대학생 알고리즘 특강(Day8) : MST(크루스칼 알고리즘, 프림 알고리즘), LCA(최소 공통 조상)
MST (최소 신장 트리)Minimum Spanning Tree가중치가 있는 연결 그래프에서 모든 정점을 포함하면서, 간선의 가중치 합이 최소가 되는 트리이를 찾기 위한 대표적인 알고리즘으로 크루스칼 알고리즘과 프림 알고리즘이 있다. 크루스칼 알고리즘(Kruskal's Algorithm)그래프의 모든 간선을 가중치 순으로 정렬한 후, 가중치가 가장 작은 간선부터 선택하여 트리를 구성하는 방법이다.이 과정에서 사이클을 형성하는 간선은 선택하지 않는다.간선 위주, union-find 사용 순서간선 정렬: 그래프의 모든 간선을 가중치 기준으로 오름차순 정렬한다.간선 선택: 정렬된 간선 리스트에서 순차적으로 간선을 선택한다. 이때, 선택된 간선이 사이클을 형성하지 않는다면 해당 간선을 최소 신장 트리에 추가한다..
