Algorithm/응용

[그래프/트리 - 응용] Union-Find / 서로소 집합

Union-Find란? 백준 문제를 풀 때 DFS로 풀었던 문제를 다른 사람들은 Union-Find로 풀었길래 정리. 11724번: 연결 요소의 개수 첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주 www.acmicpc.net Union-Find 알고리즘 대표적 그래프/트리 알고리즘으로 '합집합 찾기'라는 의미를 가지고 있다. 상호 배타적 집합(Disjoint-set)이라고도 하며 서로소 집합으로 불린다. 서로소인 부분 집합의 표현 여러 노드가 존재할 때, 두 개의 노드를 선택해서, 현재 두 노드가 서로 같은..

[이분탐색 - 응용] parametric search 개념 및 문제 풀이

백준 1654 - 랜선 자르기 문제본문 1654번: 랜선 자르기 첫째 줄에는 오영식이 이미 가지고 있는 랜선의 개수 K, 그리고 필요한 랜선의 개수 N이 입력된다. K는 1이상 10,000이하의 정수이고, N은 1이상 1,000,000이하의 정수이다. 그리고 항상 K ≦ N 이다. 그 www.acmicpc.net 개요 parametric search는 이진 탐색의 원리를 이용해서 최적의 해를 구하는 방법이다. 최적화 문제를 결정 문제로 바꾸어 푸는 것이다. 정렬된 어떠한 리스트에서 탐색 기준을 결정해 놓고 특정 위치에서 기준에 만족하지 않는 다면 그 아래있는 위치들도 모두 기준에 통과하지 못할 것이라는 확신으로 문제를 해결하는 것이다. O(logN + a)의 시간 복잡도를 가진 parametric sea..