[BOJ] 2261 가장 가까운 두 점

이 문제 학부 때 알고리즘 시간에 들었던 문제이다. 들었지만 전혀 이해 안가는 문제였는데 이제서야 이게 분할정복이라는 것을 어렴풋이나마 이해했다.

2261번: 가장 가까운 두 점

첫째 줄에 자연수 n(2 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 차례로 각 점의 x, y좌표가 주어진다. 각각의 좌표는 절댓값이 10,000을 넘지 않는 정수이다. 여러 점이 같은 좌표를 가질 수도

www.acmicpc.net

BOJ 2261:: 가장 가까운 두 점 – 분할 정복 (Closest Pair Problem) – The Casterian

http://acmicpc.net/problem/2261 모든 쌍 다 고려하기 점 두 개를 고르는 방법은 $\frac{n(n-1)}{2}$가지니까, 각각에 대해 모두 거리를 재고 그 중에 최솟값을 구하면 $O(n^2)$입니다. 확실하지만 시간 복잡도가

casterian.net

Shovel