백준 2261 가장 가까운 두 점 Java
2019. 5. 23.
정답률 15퍼센트의 가장 가까운 두 점 문제이다. 정답률에서도 알 수 있듯이 굉장히 어려운 문제인 것 같다.. n의 최댓값이 100000, 십만으로 O(n^2)으로 비교하는 간단한 알고리즘으로는 절대 풀 수 없다. 당연히 나도 풀 수 없었고, 백준님의 강의를 토대로 '분할 정복'으로 푼 가장 가까운 두 점 문제를 정리하려고 한다. 푸는 방법은 이렇다. x좌표 순으로 정렬을 한다. 그리고 중간 인덱스를 기준으로 왼쪽에서 가장 가까운 두점 사이의 거리를 찾고 오른쪽에서 가장 가까운 두점 사이의 거리를 찾는다. 왼쪽에서 구한 값과 오른쪽에서 구한 값 중 더 작은 값을 저장한다. 중간값을 기준으로 왼쪽, 오른쪽에서 가장 가까운 두점 사이의 거리는 찾았다. 남은 것은 중간값을 지나는 왼쪽 점과 오른쪽 점 사이의 ..
