one Book a Day

최소 신장 트리(MST, 크루스칼, 프림 알고리즘) 최소 신장 트리(Minnimum Spanning Tree) spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리. 신장 트리(Spanning Tree)란 그래프 내의 모든 정점을 포함하는 트리 최소 연결 : 간선의 수가 가장 적다. n개의 정점을 가지는 그래프의 최소 간선의 수는 (n-1)개 이고, (n-1)개의 간선으로 연결 되어이으면 필연적으로 트리형태가 되고 이게 신장 트리이다. 즉 그래프에서 일부 간선을 선택해서 만든 트리. DFS, BFS을 이용하여 그래프에서 신장 트리를 찾을 수 있다. 탐색 도중에 사용된 간선만 모으면 만들 수 있다. 하나의 그래프에는 많은 신장 트리가 존재할 수 있다. Spanning Tree는 트리의 ..

유니온 파인드 = 디스조인트 셋(disjoint set) = 머지 파인드 셋(merge find set) 디스 조인트 셋은 서로소 집합(교집합이 공집합인 집합) 많은 상호 배타적 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조이다. A와 B 사건 중 둘이 동시에 일어날 수 없고 둘 중 하나만 일어나야 한다. = 두 사건 중 하나의 사건이 일어날 확률이 두 사건이 각각 일어날 단순 확률의 합 과 같다. (P(A)가 일어날때 P(B)가 0이기 때문) P(A or B) = P(A) + P(B) //상호배타적이 아닌 독립적 관계는 A,B의 교집합이 없는 것은 동일하나 A,B동시에 일어나도 상관없음. 구현에는 Union, Find가 존재. 부분 집합들은 트리로 표현 할 수 있고, 파인드를 통..