봄이 왔다 엊그제 서울대학교내 컴퓨터연구소에 있는 기업에 방문했다가 내려오는 길에 찍은 사진이다. 색감이 아름답고, 확실히 봄이 왔다고 할 수 있을 것 같다. 하늘도 엄청 맑았다. Kruskal's Algorithm과 MST의 성질 어떤 가중치 있는 (연결) 그래프 $G = (V, E, w)$가 있을 때, 트리 $T$가 $G$의 스패닝 트리 임은 $T$가 $G$의 부분 그래프이고, $V(T) = G(T)$(정점 집합이 같음)으로 정의된다. 최소 스패닝 트리(Minimum Spanning Tree, MST)는 스패닝 트리 가운데 모든 간선의 가중치의 합($\sum_{e \in E(T)} w(e)$)이 최소인 것을 의미한다. (최소 스패닝 트리는 여러개가 있을 수도 있다.) 예를 들어, 7개의 정점으로 이루어진 그래프 $G$가 있다고 하자. 이 때, 이 그래프의 MST는 다음과 같다: MST는 다음과 같은 알고리즘을 통해 $O(E \log E)$ 시간에 구할 수 있으며, 이는 Kruskal 알고리즘이라 불린다. 편의상 모든 간선의 가중.. [UCPC 2018 예선 B] 카드 합체 놀이 보호되어 있는 글입니다. 이전 1 ··· 18 19 20 21 22 다음
