코딩 테스트 합격자 되기 - 집합

스터디 : 코딩테스트 합격자 되기 - 5주 차
강의 출처 : 인프런 코딩 테스트 합격자 되기 - 집합

 

 

집합

상호배타적 집합이란 교집합이 없는 관계를 말한다. 각 집합에는 공통 원소가 존재하지 않는다.

 

 

집합 표현

상호배타적 집합은 트리 자료구조로 표현할 수 있다. 각 집합에서 가장 작은 원소를 대표원소(루트노드)로 만든다.

대표 원소는 현재 노드와 부모 노드가 같다. 

 

---

 

집합의 연산

find

특정 노드의 루트 노드를 확인하는 연산이다. 특정 노드에서 루트 노드가 나올 때까지 거슬러 올라간다. 

루트 노드를 찾는데 필요한 경로가 깊어져서 연산 횟수가 증가할 경우 경로 압축 알고리즘을 활용한다.

int find(int x) {
	if (parent[node] != x) {
    	parent[x] = find(parent[x])
    }
    return paraent[x]
}

 

경로 압축 과정

find 연산을 하는 노드가 루트 노드 일 경우 루트 노드를 반환한다.

find 연산을 하는 노드가 루트 노드가 아닐 경우에는 자신의 부모 노드를 find(해당 노드의 부모 노드)로 설정한다.

 

Union

 

두개의 집합을 하나의 집합으로 합치는 연산이다.

find 연산을 통해 각 집합의 대표 원소를 구하고 루트 노드를 하나로 통일한다. 

이미지 출처 - 코딩 테스트 합격자 되기

 

 

Union - 랭크기반 알고리즘

 

union 연산 이후 깊이를 최소화하는 방법

1. 집합에 랭크를 도입한다.

2. 랭크가 더 큰쪽으로 합쳐서 랭크의 증가를 최소화한다.

void unionSets(int x, int y) {
	int rootX = find(x);
    int rootY = find(y);
    
    if(rootX != rootY) {
    	if(rank[rootX] > rank[rootY]) {
        	parent[rootY] = rootX;
        } else if(rank[rootX] < rank[rootY]) {
        	parent[rootX] = rootY;
        } else {
        	parent[rootY] = rootX;
            ++rank[rootX];
        }
    }
}

 

---

 

집합의 구현

• 노드의 최댓값이 크지 않은 경우 -> 배열
• 노드의 최대값이 큰 경우 -> unordered_map으로 구현

void unionSets(int x, int y) {
	int rootx = find(x);
    int rooty = find(y);
    
    if(rootx != rooty) {
    	parent[rooty] = rootx
    }
}