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/17472 ✅ 문제 조건1. 다리의 방향은 가로 또는 세로로만 연결 가능하다2. 방향이 가로인 다리는 다리의 양 끝이 가로방향으로 섬과 인접, 세로도 마찬가지3. 다리의 길이는 2 이상4. 다리 교차 가능5. 모든 섬이 연결하는 다리 길이의 최솟값 구하기 ✅ 접근 방법 1. 섬 위치 체크BFS를 이용해 하나의 섬마다 고유 번호를 부여하고, 바다와 맞닿아 있는 가장자리 좌표를 따로 저장했다.여기까지는 다리만들기1이랑 거의 비슷하게 풀었다. 2. 섬의 가장자리만 모아둔 배열에서 다른 섬까지 한 방향으로 다리 만들어 나가기가장자리 좌표에서 상하좌우 한 방향으로 쭉 탐색하고, 다른 섬에 도달 가능한 경우 다리 후보로 저장한다.이때 다리 길이가 2 이상을..

최소 스패닝 트리 (MST)란?최소 스패닝 트리(MST, Minimum Spanning Tree)는 그래프 이론에서 중요한 개념 중 하나로, 주어진 그래프에서 모든 정점을 연결하는 트리 중에서 가중치의 합이 최소인 트리를 의미한다.간단히 말해, 각 정점들이 연결되어 있으며, 연결된 모든 간선들의 가중치 합이 최소가 되는 트리를 찾는 문제✅ 최소 스패닝 트리의 특징트리 구조:MST는 반드시 트리 형태 (트리 : 사이클이 없는 연결된 그래프)트리의 특성상, N개의 정점이 있을 경우, 간선의 수는 항상 N-1최소 가중치:MST는 모든 간선의 가중치 합이 최소가 되어야 한다. (ex. 가중치가 의미하는 것 : 도로의 비용, 네트워크 연결의 비용 등)그래프 연결:MST는 그래프에 있는 모든 정점들을 연결해야 하므..

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. 기본적인 유니온-파인드 구현유니온-파인드는 보통 배열을 사용하여 트리 형태로 집합을 표현합니다.각 원소는 부모 노드를 가리키며, 루트 노드는 자기 ..