Coursera https://www.coursera.org/learn/algorithms-part1 강의 정리
[엮인 글 링크]
1-2 첫번째 방법: Quick-Find [Eager Approach]
1-3 더 나은 방법: Quick-Union [Lazy Approach]
dynamic connectivity. 우리말로 번역하면 '동적 연결성' 쯤이 될 듯 하다. 여기서 다루는 것은 아주 간단하다. N개의 object가 주어져 있고, 각각의 object에는 번호가 매겨져 있다. (0, 1, ... , N-1)
각각의 오브젝트들을 연결시킬 수 있다. 연결된 선을 edge라고 부른다. 이 때 여러 차례 오브젝트들을 연결시켰을 때 어떤 두 오브젝트가 연결되어 있는지를 알아내는 방법들(비효율적인 것부터 효율적인 것까지)에 대해 알아볼 것이다. (두 오브젝트의 '거리', '최단거리'에는 관심이 없다)
"연결되어 있다"는 말에 대해, 다음과 같은 equivalence relation을 가정하자.
Reflexive : p는 p와 연결되어 있다.
Symmetric : 만약 p가 q에 연결되어 있다면, q도 p에 연결되어 있다.
Transitive: 만약 p가 q에 연결되어 있고 q가 r에 연결되어 있다면, p는 r에 연결되어 있다.
우리는 이 모델에 대해 다음과 같은 두 가지 동작을 주로 수행할 것이다.
1. union command : 두 개의 오브젝트를 연결한다.
union(0, 1) 수행시, 아래와 같이 object 0과 object 1이 연결된다.
2. find query : 하나의 오브젝트가 어떤 connected component에 연결되었는지 확인한다. (또는, 뒤에서 설명하겠지만 오브젝트의 root가 어떤 오브젝트인지 확인한다)
두 오브젝트에 대해 각각 find query를 수행하면, 두 오브젝트가 연결되어 있는지도 알 수 있다. 이것을 connected query라고 부르자. connected query는 find query와 매우 밀접하게 연관되어 있다.
connected(0, 1) = true
위에서 0과 1을 연결했기 때문에, connected(0, 1)은 참이다.
connected(a, b)의 값은 두 object a와 b가 직접적으로 연결되어 있지 않더라도, 다른 object를 통해 연결될 수 있다면 참이다.
connected(0, 2) = true
connected(0, 4) = false
모든 원소가 서로 연결되어 있는 최대한의 집합을 connected component라고 부른다.
위와 같이 오브젝트들이 연결되어 있는 경우, 총 4개의 connected component가 존재한다.
{ 0 1 2 } , { 3 4 8 9 } , { 5 6 } , { 7 }
이 상태에서 find query, union command를 각각 어떻게 구현할까?
find query의 경우, 오브젝트가 속한 집합을 확인한다.
union command의 경우, 두 오브젝트가 속한 각각의 집합을 두 집합의 합집합으로 대체한다.
위 그림에서 union(2, 3)을 수행한다면,
2가 속한 connected component {0 1 2}와, 3이 속한 connected component { 3 4 8 9 }의 합집합이 두 집합을 대체하고,
3개의 connected component만 남게 된다.
{ 0 1 2 3 4 8 9 } , { 5 6 } , { 7 }
dynamic connectivity를 응용하면 네트워크 상에 연결된 컴퓨터들, SNS상에서 연결된 친구들, 주어진 미로가 풀 수 있는 것인지를 인하는 것 등에 활용할 수 있다.
이제 다음과 같은 상황 아래 union-find를 위한 효율적인 알고리즘을 디자인해 볼 것이다.
- 오브젝트의 개수 N이 매우 커질 수 있다.
- 연산의 개수 M이 매우 커질 수 있다.
- find/command query와 union command들이 뒤섞일 수 있다.