[코딩테스트 합격자 되기 10] 집합

집합

순서와 중복이 없는 원소들을 갖는 자료구조. 

 

 

상호배타적 집합의 특성을 활용하는 분야 

 

상호배타적이다 = 교집합이 없다.

코딩테스트에서 상호배타적 집합을 배워야 하는 가장 현실적인 이유는 그래프 알고리즘에서 많이 활용하기 때이다. 그래프 알고리즘에서는 흔히 사이클을 확인하는 일이 많은데, 그 작업에서 상호배타적 집합 개념을 활용한다. 이 외에도 상호배타적 집합 개념을 활용하는 알고리즘은 다양하다. 

• 이미지 분할 : 이미지를 서로 다른 부분으로 나누는 데 사용. 예를 들어 사람과 배경을 겹치지 않게 분할할 때 사용한다.
• 게임 개발 : 예를 들어 플레이어와 적군이 충돌할 때 이 두 캐릭터가 겹치지 않게 하는 데 사용
• 클러스터링 작업 : 각 작업이 서로 겹치지 않게 구성. 작업 간의 의존 관계가 없으면 동시에 여러 작업을 진행할 수 있다.

 

배열을 활용한 트리로 집합 표현하기 

잡합은 배열을 활용한 트리로 구현한다. 각 집합에는 대표 원소가 있어야 하므로 대표 원소가 무엇인지 알아보자. 

 

대표 원소란?  

대표 원소는 집합의 원소 중 집합을 대표하는 역할을 한다. 다만 여기서는 집합의 형태를 트리로 표현할 것이므로 이후 대표 원소는 루트 노드라고 부르겠다. (개념적으로 집합의 대표 원소와 트리의 루트 노드는 같다)

 

배열로 집합을 표현하는 것이란?

집합으로 배열을 표현하는 것은 하나의 배열로 상호 베타적 관계를 가지는 집합을 모두 표현한다는 것을 의미한다. 그리고 집합을 트리 형태로 표현할 때는 다음을 기억하면 된다. 

 

배열의 인덱스는 자신을, 배열값은 부모 노드를 의미한다.

 

예를 들어 disjoint_set[3] = 9면 노드 3의 부모 노드는 3임을 의미한다. 루트 노드는 말 그대로 집합의 대표이므로 부모가 없고, 부모 노드가 자기 자신이다. 다시 말해 루트 노드는 값 자체가 자기 자신과 동일하다.

 

그렇다면 집합을 표현할 때 사용하는 배열의 크기는 어때야 할까? 배열의 인덱스가 모든 집합의 원소를 표현할 수 있으면 된다. 예를 들어 가장 큰 원소가 9라면 배열의 크기는 10으로 잡아야 한다. 왜냐하면 보통 집합을 배열로 표현할 때 0은 사용하지 않기 때문이다. 

 

이렇게 되면 합집합이 없는 (상호배타적) 집합은 한 개의 배열에 표현할 수 있다. 

집합을 처음 표현할 때는 자기 자신을 부모노드로, 집합에 없는 인덱스의 값은 -1로 설정한다. 

그리고 부모노드의 값을 고려하여 인덱스 value 를 변경하면 완성이다. 

 

유니온-파인드 알고리즘

집합 알고리즘에 주로 쓰이는 연산은 합치기(union) 와 탐색(find) 이다. 

 

파인드 연산

파인드연산은 특정 노드의 루트 노드가 무엇인지 탐색하는 방법이다. 보통 파인드 연산은 특정 노드가 같은 집합에 있는지 확인할 때 사용한다. 예를 들어 A,B 루트 노드가 있는데, 루트 노드가 서로 같다면 같은 집합에 속한 것이다.

 

유니온 연산

서로 다른 두 개의 집합을 하나의 집합으로 병합하는 연산.