Union-Find(2) : Quick Find

Quick-find [eager approach]

• 지난 시간부터 이어지는 개념을 생각해봅시다.
  주어진 7개의 union에 따라 10개의 숫자들은 위와 같은 연결 구조를 띕니다.
• id라는 배열에서 같은 값을 지닌 인덱스들이 동일한 connected component에 속하는 것입니다.
  예를 들어 0, 5, 6은 모두 값이 0이므로 같은 곳에 속하죠.
• 만약 두 개의 component를 union하면 어떻게 될까요?
  기존의 값들을 모두 바꿔줘야 하기 때문에 번거롭습니다.
  지금 예시에서는 1과 6을 연결하는데, 0, 5, 6 모두 값을 변경해야 하죠.
• 그렇기 때문에 두 object를 union할 때 진즉에 관련된 모든 값을 변경하는 방식을 취할 수도 있습니다.
  관련된 코드는 자바로 작성되는데, 저는 자바를 잘 모르기 때문에 파이썬으로 번역한 식을 쓰겠습니다.

class Qucik_Find_UF(n):
    id = [x for x in range(n)]
    
    def connected(p, q):
        return id[p] == id[q]
    
    def union(p, q):
        pid, qid = id[p], id[q]
        for i in range(n):
            if id[i] == pid:
                id[i] = qid

• 뭐 실제로 이 알고리즘을 파이썬으로 구현할 때는 클래스가 아니라 함수로 구현하겠지만 강의의 내용을 따라 최대한 유사하게 작성해보았습니다.
• connected라는 함수는 p와 q가 연결되어 있는지를 반환합니다.
  id에 저장된 값이 같다면 연결되어 있다는 뜻입니다.
• union은 id에 저장된 값을 먼저 불러옵니다.
  그리고 id를 다시 처음부터 살펴보면서 p의 값과 동일한 값이 있다면 전부 q의 값으로 바꿔줍니다.
  이렇게하면 connectec componnents를 전부 새로 연결할 수 있습니다.
  (딱 봐도 비효율적이죠?)

 

Quick-find is too slow

• 이와 같은 Quick-find 방식은 이름값을 못하는, 상당히 느린 알고리즘입니다.
  매번 모든 원소를 확인해가는 방식이 효율적일리가 없죠.
  만약 n개의 object에 대해 n번의 union을 수행한다면 그 시간 복잡도는 O(N^2)이 될 것입니다.
• 뭐 우스갯소리로 10^9 = 10억 개에 대해서 union을 계산하면 당시 컴퓨터 속도로 30년은 더 걸린다고 하네요.
  따라서 효율적인 알고리즘이 필요한 것은 두말 할 필요가 없겠습니다.

 

출처: Coursera, Algorithms, Part 1, Princeton University