[알고리즘] 집합의 처리

1. 연결 리스트를 이용한 집합의 처리

 연결 리스트

- 각 원소당 하나의 노드를 만들고 이들을 연결 리스트로 연결함.

- 각 노드에는 원소를 저장하는 필드와 다음 원소, 대표 원소를 가리키는 두 개의 포인터가 있음.

- 다음 원소를 가리키는 포인터를 이용해 집합의 모든 원소가 연결 리스트로 연결됨.

- 각 집합에는 마지막 원소를 가리키는 tail이라는 변수를 둠. 이것은 두 집합을 합칠 때 시간을 절약할 수 있게 해줌.

 

상호 배타적 집합의 관리를 위해 필요한 세 가지 연산

1. Make-Set(x) : 원소 x로만 구성된 집합을 만듦.

- 노드를 하나 만들어 해당 원소를 저장함. 대표 노드로는 자신을 가리키도록 하고, 다음 원소는 없으므로 포인터는 NIL로 해둠.

 

2. Find-Set(x) : 원소 x를 가진 집합을 알아냄.

- 원소 x가 가리키는 대표 노드를 리턴함.

 

3. Union(x,y) : 원소 x를 가진 집합과 원소 y를 가진 집합을 하나로 합침.

- 원소 x가 속한 집합과 원소 y가 속한 집합을 하나로 합치는 연산.

- 우선 Find-Set(x)와 Find-Set(y)를 이용하여 x와 y가 속한 집합의 대표 노드를 각각 알아낸 다음 두 집합 중 하나를 다른 집합 뒤에 붙임.

- 앞쪽에 있는 집합의 tail 노드의 다음 원소 포인터를 뒤에 오는 집합의 대표 노드를 가리킴.

- 뒤에 오는 집합의 모든 노드의 대표 원소 포인터는 앞쪽에 있는 집합의 대표 노드를 가리키도록 바꿈.

 

수행 시간

- Make-Set은 하나의 원소로 된 집합을 초기화하는 것이므로 상수 시간이 듦.

- Find-Set도 상수 시간이 듦. 해당 원소의 노드에 있는 대표 원소 포인터만 리턴하면 되기 때문.

- 상수 시간을 초과할 수 있는 것은 Union뿐.

- Union을 할 때 시간이 가장 많이 드는 작업은 대표 원소를 가리키는 포인터를 바꾸어주는 일.

 

무게를 고려한 Union

- 집합의 크기를 비교하여 두 집합을 합치는 것.

- 무게를 고려한 Union을 이용해 집합을 처리하면 다음과 같은 성질을 만족함.

- 상각 분석이라 하는 분석법의 한 종류

연결 리스트를 이용해 표현되는 배타적 집합에서 무게를 고려한 Union을 사용할 때, m번의 Make-Set, Union, Find-Set 중 n번이 Make-Set이라면 이들의 총 수행 시간은 O(m + n log n ).

 

2. 트리를 이용한 집합의 처리

기본 원리

- 연결 리스트를 이용하는 방법보다 효율적인 처리 방법은 각 집합을 하나의 트리로 표현하는 방법.

- 트리를 나타낼 때 보통은 부모 노드가 자식 노드를 가리키도록 하지만 여기서는 자식 노드가 부모 노드를 가리키도록 함.

- 임의의 노드에서 부모를 기리키는 포인터를 계속 따라가다 보면 자식이 속한 트리의 루트 노드를 만나게 됨.

- 이 루트 노드가 집합의 대표 노드.

- 트리를 이용한 표현에서 두 집합을 합치는 작업은 연결 리스트 방법보다 아주 간단함.

- 두 집합 중 한 집합의 루트가 다른 집합의 루트를 가리키도록 포인터 하나만 변경해주면 됨.

 

 

Make-Set(x)
{
    p[x] <- x;
}

Union(x,y)
{
    p[Find-Set(y)] <- Find-Set(x);
}

Find-Set(x)
{
    if (x = p[x]) then return x;
                      else return Find-Set(p[s]);
}

 

연산의 효율을 높이는 방법

랭크를 이용한 Union

- 각 노드는 자신을 루트로 하는 서브 트리의 높이의 상한을 랭크라는 이름으로 저장함.

- 단 하나의 노드로 된 트리의 높이는 0이라고 정의함.

- 루트 노드의 랭크가 해당 집합의 랭크가 됨.

- 랭크를 이용한 Union에서는 두 집합을 합칠 때 랭크가 낮은 집합을 랭크가 높은 집합에 붙임.

Make-Set(x)
{
    p[x] <- x;
    rank[x] <- 0 ;
}

Union(x,y)
{
    x' <- Find-Set(x);
    y' <- Find-Set(y);
    if (rank[x'] > rank[y']
        then p[y'] <- x';
        else {
            p[x'] <- y';
            if ( rank[x'] = rank[y'] ) then rank[y'] <- rank[y']+1;
        }
}

 

경로 압축

- Find-Set을 행하는 과정에 경로의 길이를 줄이는 아이디어를 넣은 것.

- Find-Set(x)를 수행하는 과정에서 만나는 모든 노드가 직접 루트를 가리키도록 포인터를 바꾸어줌. 이렇게 함으로써 트리의 랭크(높이)를 줄일 가능성이 높음.

Find-Set(x)
{
    if (p[x] ≠ ) then p[x] <- Find-Set(p[x]);
    return p[x];
}

 

효율성

- 우리가 현실적으로 다룰 수 있는 모든 경우에 대해 log*n은 사실상 O(1).

- m번의 연산을 할 경우에 최악의 경우 O(m)의 시간이 들게 됨.

- 전체적으로 보면 각 연산에 평균 상수 시간이 소요됨.

- 경로 압축 시에 영향을 받는 노드의 랭크 값을 수정해주는 것이 바람직하나 거의 불가능함.

- 그래서 랭크값이 실제로 바뀌어도 그대로 둠.