# disjoint set
2/4 (Sat): 코딩테스트 알고리즘 공부
Binary Sarch, Dinamic Programming, Kruskal Algorithm, Topology Sort, Cycle, Dijkstra, Floyd Warshall, Parametric Search, Disjoint Set
Union Find와 경로 압축
간단하게 union find 알고리즘과 경로 압축 알고리즘에 대해서 적어본다.disjoint Set이라고도 하며 트리나 그래프의 연결 유무를 확인하기 위한 알고리즘이다.find 와 union 의 2가지 메서드를 가진다. find 는 트리의 루트를 확인하며, union는
Disjoint Set
고오급 알고리즘을 공부하는 이유?선구자들의 지혜를 배우고, 내가 보는 시야를 넓힌다.최소 스패닝 트리 (Minimum Spanning Tree)를 공부를 할 것인데,Minimum Spanning Tree => 그래프/트리의 활용정도가 된다.이것을 알기전에 알고가야할 부
[알고리즘] union find
공통 원소가 없는 두 집합e.g. {1,2} {3,4} -> 서로소 관계임 {1,2} {2,3} -> 서로소 관계가 아님서로소 부분 집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조\-> 연산 : union + find2개 원소로 이루어진 집합을 하나의 집합으
[백준] 2162번: 선분 그룹 with Python
BOJ 2162Disjoint setGeometryN개의 선분들이 2차원 평면상에 주어져 있다. 선분은 양 끝점의 x, y 좌표로 표현이 된다.두 선분이 서로 만나는 경우에, 두 선분은 같은 그룹에 속한다고 정의하며, 그룹의 크기는 그 그룹에 속한 선분의 개수로 정의한
[Algorithm] DSU, Disjoint Set Union&Find
Disjoint Set(서로소 집합)은 서로 배타적인 원소를 가진 두 집합. 공통되는 원소를 가지지않은 두 집합을 말한다. 여기서 해당 알고리즘은 Disjoint Set 자료구조를 사용하여, 서로 다른 두 원소가 같은 집합에 속해있는지를 판별하는데 유용하게 사용된다.
[baekjoon] #10216: Count Circle Groups
문제링크Brute-ForceIf the distance between enemies is smaller than the sum of each enemy's range, union each parent.Then, find the number of group using m
.png)
Union-Find
서로소 집합 (Disjoint-set) 서로 중복 포함된 원소가 없는 집합들. 집합에 속한 하나의 특정 멤버를 통해 각 집합들을 구분한다.
백준 알고리즘 18116번 : 로봇 조립
https://www.acmicpc.net/problem/18116성규는 로봇을 조립해야 한다. 상자 안에는 여러 로봇의 부품들이 섞여 있다. 그런데 어떤 부품이 어느 로봇의 부품인지 표시가 되어있지 않다. 호재는 전자과라서 두 부품을 보면 같은 로봇의 부품인
백준 알고리즘 20040번 : 사이클게임
https://www.acmicpc.net/problem/20040사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한
[프로그래머스/C++] 호텔 방 배정
본 문제는 정확성과 효율성 테스트 각각 점수가 있는 문제입니다."스노우타운"에서 호텔을 운영하고 있는 "스카피"는 호텔에 투숙하려는 고객들에게 방을 배정하려 합니다. 호텔에는 방이 총 k개 있으며, 각각의 방은 1번부터 k번까지 번호로 구분하고 있습니다. 처음에는 모든
[백준/C++] 20040번. 사이클 게임
사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 번호가 부여된 평면 상의 점 n 개가 주어지며, 이 중 어느 세 점도 일직