이숭간 공부기록

https://www.acmicpc.net/problem/1922 1922번: 네트워크 연결 이 경우에 1-3, 2-3, 3-4, 4-5, 4-6을 연결하면 주어진 output이 나오게 된다. www.acmicpc.net 문제유형 : 최소스패닝트리 (MST) 문제풀이 : 변형없는 전형적인 최소스패닝트리 문제이다. 프림과 크루스칼 알고리즘을 쓸 수 있는데 구현이 좀더 쉬운 크루스칼 알고리즘을 이용했다. 크루스칼 알고리즘에서는 서로소집합개념인 유니온파인드 개념을 알고있어야한다. 정답코드 : import sys input = sys.stdin.readline #크루스칼알고리즘 # 비용을 오름차순으로 정렬하고 # 사이클이 발생하면 추가하지않고, 사이클이 발생하지 않으면 추가한다. # 특정 원소가 속한 집합을 찾..

본 글은 동빈나 2021 이코테 _ 8. 기타그래프 이론을 정리한 글입니다! 서로소 집합 자료구조 _ Union-Find 서로소 집합이란 공통원소가 없는 두 집합을 의미한다. 서로소 부분집합들로 나누어진 원소들의 데이터를 처리하기 위한 자료구조 서로소 집합 자료구조(=합치기 찾기 자료구조)는 두종류의 연산을 지원한다. 합집합(Union) : 두개의 원소가 포함된 집합을 하나의 집합으로 합치는 연산 찾기(find) : 특정 원소가 속한 집합이 어떤 집합인지 알려주는 연산 - Union의 인자값으로 각 노드가 들어감 - 초기에는 각각이 하나의 집합으로 여겨지며 자기자신이 곧 부모가 된다. - 합치기 연산에서, 일반적으로 두 노드중 값이 더 큰 노드의 부모값을 더 작은노드의 부모로 갱신한다. 단, 여기서 부모..