ayeongjin 님의 블로그

https://www.acmicpc.net/problem/7511 💡 리팩토링 이유알고리즘 문제를 풀면서 여러 테스트 케이스가 반복되는 문제를 풀 때 특히 가독성과 유지보수 측면, 재사용성 관점에서 코드를 클래스화하면 더 깔끔하고 독립적인 코드가 될 수 있다고 생각했다.그래서 이번에는 유니온파인드 문제를 풀이하면서 클래스로 변경해봤다. ✅ 1. 초기 구현 – 전역 변수와 함수 기반 처음에는 단순히 문제를 푸는 데 집중해서 parent, rank, find, union 전부 전역에 두고 구현했다.import sysinput = sys.stdin.readlineT = int(input())for t in range(T): print(f'Scenario {t+1}:') n = int(input(..

https://www.acmicpc.net/problem/24542  스터디에 유니온 파인드로 풀어야 시간초과 안나는 문제가 나와서 유니온파인드 공부했다.https://ayeongjin.tistory.com/45 유니온-파인드(Union-Find) 알고리즘1. 유니온-파인드란?유니온-파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set) 을 관리하는 자료구조로, 대표적으로 그래프에서 사이클 판별, 네트워크 연결성 검사, 최소 신장 트리(MST) Kruskalayeongjin.tistory.com  일단 이론대로 문제 설계를 해보면1. 필요한 값어떤 집합인지 알아볼 수 있는 parent배열 (parent배열의 값이 같으면 같은 집합)집합의 크기를 나타내는 size배열랭크 기반 유니온을..

1. 유니온-파인드란?유니온-파인드(Union-Find) 알고리즘은 서로소 집합(Disjoint Set) 을 관리하는 자료구조로, 대표적으로 그래프에서 사이클 판별, 네트워크 연결성 검사, 최소 신장 트리(MST) Kruskal 알고리즘 등에 활용됩니다. 이 알고리즘은 다음 두 가지 핵심 연산을 수행합니다.Find 연산: 특정 원소가 속한 집합(루트 노드)을 찾는 연산Union 연산: 두 개의 집합을 하나로 합치는 연산최적화 기법을 적용하면 매우 효율적으로 동작하여 거의 상수 시간(α(n), 아커만 함수의 역함수 수준) 에 연산을 수행할 수 있습니다.  2. 기본적인 유니온-파인드 구현유니온-파인드는 보통 배열을 사용하여 트리 형태로 집합을 표현합니다.각 원소는 부모 노드를 가리키며, 루트 노드는 자기 ..