728x90 유니온파인드7 [python] 백준 4386 별자리 만들기 https://www.acmicpc.net/problem/4386 4386번: 별자리 만들기 도현이는 우주의 신이다. 이제 도현이는 아무렇게나 널브러져 있는 n개의 별들을 이어서 별자리를 하나 만들 것이다. 별자리의 조건은 다음과 같다. 별자리를 이루는 선은 서로 다른 두 별을 일 www.acmicpc.net 문제 해결 전형적인 유니온 파인드 문제 단 리스트 안에 두 별자리 간의 거리를 오름차순으로 정렬하고 연결 되어있는지 아닌지 유니온 파인드를 통해 확인하고 해결한다. CODE import sys input = sys.stdin.readline import math def find(x): if x != parents[x]: return find(parents[x]) return parents[x] de.. 2024. 3. 7. [python] 백준 16566 카드 게임 https://www.acmicpc.net/problem/16566 16566번: 카드 게임 첫째 줄에 세 개의 자연수 N, M, K가 주어진다. (1 ≤ M ≤ N ≤ 4,000,000, 1 ≤ K ≤ min(M, 10,000)) 다음 줄에 카드의 번호를 나타내는 M개의 자연수가 주어진다. 각각의 수들은 1 이상이고 N 이하이며 서로 www.acmicpc.net 문제 해결 이진 분류로 bisect_right를 사용할 수 있는가의 문제 가장 최소의 값을 구할 때 만약 사용했다면 그 다음 수를 찾아야 하는데 여기서도 union-find를 사용하는가에 따라서 시간 단축이 될 수 있다. 만약 이전에 어떤 수를 사용했으면 그 수에 접근 했을 때 다음수로 넘어가도록 union-find를 설계할 수 있기 때문이다... 2024. 3. 5. [python] 백준 20955 민서의 응급 수술 https://www.acmicpc.net/problem/20955 20955번: 민서의 응급 수술 민서는 강원대학교 컴퓨터공학과의 신임 교수이다. 그녀가 저술한 효율적인 택배 배달을 위한 최적 경로 설계에 관한 연구 논문은 아직도 널리 인용되고 있다. 오늘도 열심히 강의를 하던 민서 www.acmicpc.net 문제 해결 먼저 분리되어 있는 그룹이 몇개인지 알아야 한다. 그것을 유니온-파인드를 통해 알 수 있다. 만약 시냅스로 연결된 두 뉴런의 번호 u,v를 받았을 때 이미 같은 그룹에 있으면 더 연결 될 필요가 없으므로 잘라내는데에 연산을 한 번 쓰게 된다. 만약 다른 그룹이면 유니온-파인드를 통해 서로 연결 시킨다. 그룹이 다른 개수 + 이미 연결되어 연결 될 필요가 없는 개수를 합친다음 하나의 중.. 2023. 9. 25. [python] 백준 20040 사이클 게임 https://www.acmicpc.net/problem/20040 20040번: 사이클 게임 사이클 게임은 두 명의 플레이어가 차례대로 돌아가며 진행하는 게임으로, 선 플레이어가 홀수 번째 차례를, 후 플레이어가 짝수 번째 차례를 진행한다. 게임 시작 시 0 부터 n − 1 까지 고유한 www.acmicpc.net 문제 해결 1~m 번호까지 차례대로 원하는 두 점을 연결한다.(중복 불가) 어 때 몇 번째 번호에서 사이클이 만들어지는지 구하는 문제이다. 처음에는 하나의 선분이 그어질 때마다 사이클이 존재하는지 직접 돌려야되나 생각했다. 하지만 유니온 파인드(union find)를 이용하면 계산양을 줄이고 쉽게 사이클이 만들어지는지 확인할 수 있음을 알 수 있었다. 그림으로 이해하면 너무 쉽다. CODE .. 2023. 9. 11. 이전 1 2 다음 728x90
