유니온 파인드 썸네일형 리스트형 유니온 파인드 트리(분리 집합) 소개 유니온 파인드 트리는 교집합이 없는 여러 집합들을 나타내는 자료구조입니다. 집합을 합치는 연산과 원소가 속해 있는 집합을 구하는 연산을 상수 시간에 처리할 수 있습니다. 구조 유니온 파인드 트리는 여러 개의 트리가 모여 있는 구조입니다. 각각의 트리는 집합 하나를 나타내며, 트리의 루트 노드의 번호가 해당 집합을 대표합니다. 배열에서 각 노드의 부모 노드 번호를 저장하고 있으며, 배열에서 재귀함수를 통해 부모 노드를 타고 올라가 루트 노드를 찾는 방식으로 구현합니다. 구현 i번 노드가 속해 있는 집합의 루트 노드를 구하는 find(i) 연산과 i, j번 노드가 속해 있는 두 집합을 합치는 union(i, j) 연산을 구현해야 합니다. find 연산 1 2 3 4 5 6 int par[100005];.. 더보기 백준 4195번 친구 네트워크 http://icpc.me/4195 4195번: 친구 네트워크 첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 친구 관계의 수 F가 주어지며, 이 값은 100,000을 넘지 않는다. 다음 F개의 줄에는 친구 관계가 생긴 순서대로 주어진 www.acmicpc.net 풀이 Union-find와 map STL을 사용해 풀었습니다. 사용자가 문자열 이름이 아닌 번호로 주어졌다고 가정합시다. 이러한 경우에는 Union-find로 각 사용자와 친구 네트워크의 크기를 관리하며 쉽게 풀 수 있습니다. union-find 트리를 나타낼 배열과 각 사용자의 친구 네트워크의 크기를 나타낼 배열이 필요합니다. 두 사용자가 친구 관계를 맺으면 union연산을 통해 두 사용자가 속해 있는 친구 네트워.. 더보기 백준 13306번 트리 https://www.acmicpc.net/problem/13306 13306번: 트리 표준 입력으로 다음 정보가 주어진다. 첫 번째 줄에는 트리의 정점의 개수와 질의의 개수를 나타내는 두 정수 N과 Q (1 ≤ N, Q ≤ 200,000)가 주어진다. 다음 N-1개의 줄의 i번째 줄에는 정점 i+1의 부 www.acmicpc.net 풀이 마지막에 받은 쿼리부터 역순으로 실행하는 것이 풀이의 핵심입니다. 트리의 간선을 끊는 동작은 처리하기 어렵지만, 두 정점을 잇는 연산은 유니온 파인드를 통해 쉽게 할 수 있기 때문입니다. 따라서 트리에서 간선을 하나씩 끊는 것이 아니라 모든 정점이 연결되지 않은 상태에서 쿼리를 역순으로 보며 각 쿼리에 대해 다음과 같이 실행합니다. 쿼리 1 : 0 b 원래 명령과 반대.. 더보기 백준 20052번 괄호 문자열? https://www.acmicpc.net/problem/20052 20052번: 괄호 문자열 ? 괄호 문자열은 '('와 ')'로 이루어진 문자열이고, 올바른 괄호 문자열은 다음과 같이 정의된다. 빈 문자열은 올바른 괄호 문자열이다. S가 올바른 괄호 문자열일 때, (S)도 올바른 괄호 문자열이 www.acmicpc.net 풀이 유니온 파인드를 이용한 풀이와 세그먼트 트리를 이용한 풀이가 있습니다. 유니온 파인드 풀이는 제가 구상했고, 세그먼트 트리 풀이는 다른 분의 도움을 받았습니다. 풀이 1(유니온 파인드 이용) 이 풀이의 핵심은 유니온 파인드를 이용해 이어져 있는 괄호쌍을 하나로 묶어 관리하는 것입니다. 입력받은 괄호 문자열을 탐색하며 이어져 있는 괄호쌍을 묶는 작업을 마치면 아래 그림처럼 괄호 문.. 더보기 이전 1 다음
