목록2023/08/10 (1)
나의 개발일지
5주차 알고리즘 - 최소신장트리 (MST)
- MST : Minimum Spanning Tree - 그래프 상의 모든 노드들을 최소 비용으로 연결하는 방법 : 크루스칼, 프림 노드와 간선정보가 주어졌을 때 최소가 되게 노드들을 한 번만 연결하는 방법 MST 관련 문제들은 내부 알고리즘은 동일. 문제 파악한 후 MST 형태인 것만 떠올면 풀 수 있음 - 크루스칼 (Kruskal) 알고리즘 · 간선 중 최소 값을 가진 간선부터 연결 · 사이클 발생 시 다른 간선 선택 · 주로 간선 수가 적을 때 사용 · O(Elog E) - 간선 정보들을 오름차순 Sorting 작업 필요 - 사이클 발생 체크하는 Union-Find 테이블 초기 : 각 자기 자신으로 초기화 1. 처음에 가장 작은 가중치인 1을 선택해서 1 - 3 노드를 연결하면 3의 부모노드는 연결..
알고리즘/개념
2023. 8. 10. 21:49