자바로 구현하는 서로소 집합(Union-Find) 자료구조와 경로 존재 여부 판별
서로소 집합(Union-Find) 자료구조의 이해
서로소 집합(Disjoint Set) 또는 유니온-파인드(Union-Find)는 그래프 이론에서 두 원소가 동일한 집합에 속하는지 판별하거나, 동적 연결 상태를 관리하는 데 특화된 자료구조입니다.
핵심 원리 및 동작 방식
1차원 배열을 사용하여 트리 구조를 표현하며, 각 인덱스는 노드를 의미하고 저장된 값은 해당 노드의 부모를 나타냅 ...
7월 7일 05:14에 게시됨
확장된 범위의 유니온-파인드 구조 및 BOI2003 팀 문제 해설
이 문제는 확장된 범위의 유니온-파인드(Union-Find) 데이터 구조를 활용한 알고리즘 문제입니다. 일반적인 유니온-파인드는 요소 간 연결 관계를 표현하지만, 이 문제에서는 추가적인 속성(친구/적 등)을 고려해야 합니다.
확장된 범위 유니온-파인드는 복수의 속성을 다루기 위해 여러 영역(domain)을 생성합니다. 예를 들어, 인물 x의 친구 관계는 x, 적은 x+n으로 매 ...
7월 4일 19:14에 게시됨
2025-10-21 XQQ 라운드 후기 및 문제 분석
대회 흐름 요약
T1을 먼저 시작, 고민 후 즉시 해결. 대양에서 한 번에 통과.
T2도 비슷한 방식으로 빠르게 해결. 역시 대양에서 통과.
15:48 T3에 접근, 그러나 잘못된 접근으로 실패. 다만
7월 1일 07:06에 게시됨
최소 스패닝 트리 알고리즘 비교: Kruskal, Prim, Boruvka
Kruskal 알고리즘
희소 그래프(Sparse Graph)에 적합한 크루스칼 알고리즘은 간선 기반의 탐욕적 접근 방식을 사용한다. 모든 간선을 가중치 기준으로 오름차순 정렬한 후, 사이클을 만들지 않는 한도 내에서 순차적으로 선택한다. 이때 연결 여부는 유니온-파인드(Union-Find) 자료구조로 관리한다.
n개의 정점이 주어졌을 때, 최소 스패닝 트리는 정확히 n-1개의 간선으 ...
6월 17일 18:25에 게시됨
AtCoder Beginner Contest 399 풀이
A - Hamming Distance
문제 설명
두 문자열 S와 T가 주어졌을 때, 서로 다른 문자의 개수를 구한다.
풀이 방법
문자열을 순회하며 각 위치의 문자가 다를 때마다 카운트를 증가시킨다.
코드
코드 보기
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
string s, t;
...
5월 25일 08:20에 게시됨