서로소 집합, 유니온 파인드 - Disjoint set, Union-Find
0) Introduction Disjoint-set 자료구조는 Union-find나 Merge-find set과 동의어이다. 서로소 집합 트리는 요소들을 서로소 집합으로 나누고, 찾을 수 있는 자료구조이다. → 최소 신장 트리(Minimum spanning tree)를 찾는 Kruskal Algorithm을 구현하는 데에 중요한 역할을 한다. 1) Operations of Union-find Union-find는 다음과 같은 연산들이 구현되어 있어야 한다. 제일 중요한것은 Find와 Union이긴 하지만,, 한번 알아보자. 1. MakeSet 단순히 서로소 집합 트리에 노드들을 집어넣는 연산이다. rank와 size를 초기화하는 것이 눈에 띄는데, 트리가 편중(skewed)되는 것을 Union 연산에서 ..
최단 경로 알고리즘 - algorithm for shortest path problem
최단 경로를 구하는 문제에서 적용할만한 알고리즘을 알아보자. 0) 모델링 그래프에 대한 정보는 인접 행렬이나 인접 리스트를 이용해 모델링할 수 있다. 1. Adjacency Matrix (인접 행렬) 노드 개수 V개가 있다면 V^2개의 배열에 간선의 정보를 저장하는 것이다. 구현이 쉽고 간편해 보이지만, 간선의 유무와 관계없이 전체를 탐색해 보아야 하기 때문에 전체 탐색시 O(V^2)이 걸린다. 그러나 배열의 특성상 특정 간선만 알고 싶을 때는 O(1) 밖에 소요되지 않는다는 장점이 있다. ex) i → j : edge[i][j] = true; 2. Adjacency List (인접 리스트) 간선의 정보를 배열에 저장하는 인접 행렬과 달리 벡터에 저장한다. 간선의 개수만큼의 메모리가 필요하므로 효율적이고..