승코딩당당당

그래프 문제를 풀다 보면 노드 간의 연결 여부를 빠르게 판단해야 하는 상황이 자주 등장한다.이때 사용하는 대표적인 알고리즘이 바로 유니온 파인드(Union-Find) 이다. 유니온 파인드는 노드들을 여러 개의 집합으로 관리하면서집합을 합치고, 같은 집합인지 확인하는 연산을 빠르게 수행할 수 있는 자료구조이다. 이번 글에서는 유니온 파인드의 개념과 핵심 연산,그리고 성능을 향상시키는 경로 압축까지 정리해보려고 한다. ✍️ 유니온 파인드란?유니온 파인드(Union-Find)는여러 노드를 집합으로 묶고 관리하는 알고리즘이다. 이 알고리즘은 다음 두 가지 연산으로 구성된다.union 연산: 두 집합을 하나로 합치는 연산find 연산: 특정 노드가 속한 집합의 대표 노드를 찾는 연산즉,노드 a, b가 있을 ..

문제[C++] 백준 1976: 여행 가자 GOLD 4https://www.acmicpc.net/problem/1976 접근 방법백준 1976번은 여행 계획이 가능한지 판단하는 문제다.여러 도시가 있고, 도시 간 연결 정보가 주어질 때 주어진 여행 계획대로 모든 도시를 이동할 수 있는지 확인해야 한다. 핵심 아이디어는 다음과 같다.여행 계획에 포함된 모든 도시가하나의 연결된 그룹(같은 집합) 에 속해 있는지 확인하면 된다. 이 문제는 도시 간 연결 여부를 계속 확인해야 하므로Union-Find(Disjoint Set) 자료구조를 사용하는 것이 가장 효율적이다. 상세 아이디어부모 배열 초기화 parent.resize(N + 1, 0);for (int i = 1; i 각 도시는 처음에 자기 자신을 부모로 가..

문제[C++] 백준 1717: 집합의 표현 GOLD 5https://www.acmicpc.net/problem/1707 접근 방법백준 1717번은 집합의 합집합과 포함 여부를 처리하는 문제로,대표적인 Union-Find(Disjoint Set) 자료구조를 사용하는 문제다. 문제에서 수행하는 연산은 두 가지다.0 a b → a와 b를 같은 집합으로 합치기 (Union)1 a b → a와 b가 같은 집합인지 확인 (Find)따라서 핵심은 각 원소가 어떤 집합에 속해 있는지를 효율적으로 관리하는 것이다. 이를 위해 parent 배열을 사용한다.vector parent; parent[i] : i의 부모 노드초기에는 모든 원소가 자기 자신을 부모로 가진다.for (int i = 1; i Find (대표 노드 ..