[JAVA] Quick Find

이 글은 개인의 학습을 목적으로 정리한 글입니다. 이점 참고하고 읽어주세요;)

---

Quick-Find는 위와 같이 하나의 배열이 존재할 때, 그 배열의 인덱스에 저장된 값들을 다른 인덱스에 저장된 값들과 연결시키고(union), 또 연결되었는지 확인하는(connected) 알고리즘의 한 유형입니다. 그 구조를 도식화한 것이 위의 그림입니다.

 

Union의 기본 구조는 위와 같습니다. union()에 두 인덱스 값을 줬을 때, 앞의 인덱스에 저장된 값을 뒤의 인덱스에 저장된 값으로 변경하는 방식입니다.

public class QuickFind {
    private int[] id;
    public QuickFind(int N){
        id = new int[N];
        for(int i=0; i<N; i++)
            id[i] = i;
    }

    public boolean conneced(int p, int q){
        return id[p] == id[q]; // 같으면 true, 다르면 fale
    }

    public void union(int p, int q){	// N^2의 연산 시간 발생(quadratic time).
        int pid = id[p];
        int qid = id[q];
        for(int i=0; i<id.length; i++){
            if(id[i]==pid) id[i]=qid;
        }
    }

    public static void main(String[] args){
        QuickFind quickf = new QuickFind(10);
        System.out.println(quickf.conneced(1, 5));

        quickf.union(1,5);
        System.out.println(quickf.conneced(1,5));
    }
}

이를 코드로 구현해보면 위와 같습니다.

그런데 이러한 QuickFind 알고리즘에서 union 연산은 for문을 통해 배열 전체를 훑는 연산을 실행하게 됩니다. 때문에 크기가 N개인 배열에 대해 N번의 union을 진행한다면 N^2번, 즉 N의 제곱만큼의 연산을 요하게 됩니다. 이런 제곱 연산은 처리해야 하는 데이터의 크기가 늘어날수록 필요로 하는 시간이 기하급수적으로 증가하기 때문에 시간적인 측면에서 그리 효율적인 방법은 아닙니다. 이러한 연산에 대해 너무 비싸다. 즉 too expensive 하다고 말합니다.