안녕하세요! 이번 시간에는 코딩테스트에서 자주 등장하는 알고리즘 중 하나인 유니온 파인드(Union-Find)에 대해서 알아보겠습니다. 이 알고리즘은 그래프의 연결 성분을 찾거나, 집합을 관리하는 데 유용하며, 다양한 문제 해결에 활용됩니다. 시작하기 전에 유니온 파인드의 기본 개념을 이해하고, 실제 문제풀이 과정을 통해 구체적인 활용 방법을 배워보겠습니다.
유니온 파인드란?
유니온 파인드는 주어진 원소들이 어떤 연결된 집합들로 나누어져 있는지를 추적할 수 있는 데이터 구조입니다. 다음의 두 가지 연산을 제공합니다:
- Find: 주어진 원소가 어떤 집합에 속하는지를 찾는 연산.
- Union: 두 개의 집합을 합치는 연산.
이 자료구조는 그래프의 연결 성분을 찾는 데 유용하며, 사이클 여부를 판단할 때도 자주 사용됩니다. 유니온 파인드는 최적화 기법을 사용하여 매우 빠른 수행 시간을 자랑합니다.
문제 설명
이제 유니온 파인드를 적용해볼 수 있는 문제를 소개하겠습니다. 다음과 같은 문제가 있습니다:
문제: 친구 찾기
n명의 사람들이 있다. 각 사람은 친구를 사귈 수 있으며, 친구 관계는 서로에게 연결되어 있다. 주어진 친구 관계의 목록에서 서로 친구인지 여부를 판단할 수 있는 알고리즘을 작성하시오. 친구 관계는 다음 형식으로 주어진다:
[[1, 2], [2, 3], [4, 5]]위 예시에서는 1과 2가 친구이고, 2와 3이 친구이므로, 1과 3은 간접적으로 친구입니다. 4와 5는 별개의 친구 관계이니 1과 4는 친구가 아닙니다. 각 쿼리에 대해 두 사람이 친구인지 확인하시오.
유니온 파인드 알고리즘 구현
이제 이 문제를 유니온 파인드 알고리즘으로 해결하는 방법을 살펴보겠습니다. 먼저, 유니온 파인드 구조체를 정의하고 그 안에 필요한 함수를 구현하겠습니다.
class UnionFind {
constructor(size) {
this.parent = new Array(size);
this.rank = new Array(size).fill(1);
for (let i = 0; i < size; i++) {
this.parent[i] = i;
}
}
find(x) {
if (this.parent[x] !== x) {
this.parent[x] = this.find(this.parent[x]); // Path compression
}
return this.parent[x];
}
union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (rootX !== rootY) {
// Union by rank
if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}
}
areConnected(x, y) {
return this.find(x) === this.find(y);
}
}
문제 해결 과정
1. 문제의 입력을 처리합니다. 친구 관계를 입력받고, 약속된 쿼리를 수행할 대상을 가져옵니다.
function processFriendships(friendships, queries, numberOfPeople) {
const uf = new UnionFind(numberOfPeople + 1); // +1 to accommodate 1-indexed people
friendships.forEach(([a, b]) => {
uf.union(a, b);
});
return queries.map(([x, y]) => uf.areConnected(x, y));
}
2. 친구 관계 목록을 반복하여 각 쌍에 대해 유니온 연산을 수행합니다.
3. 각 쿼리에 대해 두 사람이 같은 집합에 속하는지 여부를 판단합니다.
최종 코드
const friendships = [[1, 2], [2, 3], [4, 5]];
const queries = [[1, 3], [1, 4], [4, 5]];
const numberOfPeople = 5;
const results = processFriendships(friendships, queries, numberOfPeople);
console.log(results); // [true, false, true]
결과 해석
최종적으로 쿼리 결과는 다음과 같습니다:
- 1과 3은 친구이다: true
- 1과 4는 친구가 아니다: false
- 4와 5는 친구이다: true
위 코드는 유니온 파인드를 통해 효율적으로 친구 관계를 처리했습니다. 유니온 파인드는 특히 많은 수의 집합이 있을 때 그 유용성을 발휘하며, 시간 복잡도는 거의 상수 시간입니다.
마무리
이번 강좌에서는 유니온 파인드 알고리즘을 통해 친구 찾기 문제를 해결했습니다. 유니온 파인드는 다양한 문제에 활용될 수 있으며, 알고리즘 문제를 해결하는 데 매우 유용한 도구입니다. 계속해서 다양한 알고리즘들을 학습하고 연습하여 코딩 테스트에서 좋은 결과를 얻으시길 바랍니다!
감사합니다!