분할정복 방법
우리는 평면에서 n개의 점들의 한 배열이 주오지고, 문제는 그 배열에서 가장 가까운 점들의 쌍을 찾는 것이다. 이 문제는 많은 적용에서 발생한다. 예를들어, 항공 교통 제어에서, 너는 서로 너무 가까이 있는 비행기들을 감시하길 원ㅇ할 지도 모른다. 왜냐하면 이것이 가능한 충돌을 알려주기 때문이다. 두 점 사이 p와 q사이의 거리 공식은 다음의 공식을 떠올려라.
Brute force 방법은 O(n^2)이고, 각 쌍 사이의 거리를 연산하고, 가장 작은 것을 반환한다. 우리는 분할정복 전략을 사용하여 O(nlgn) 시간에 가장 작은 거리를 계산할 수 있다. 이 글에서, O(n x (lgn)^2) 접근법이 다루어진다. 우리는 별도의 글에서 O(nlgn) 접근법을 다룰 것이다.
Algorithm
다음은 O(n * (lgn)^2) 알고리즘의 세부 단계들이다.
Input : n개의 점들을 가진 한 배열 P[]
Output : 주어진 배열에서 두 점 사이의 가장 작은 거리
전처리 단계로서, input array는 x 좌표에 따라 정렬된다.
1) 정렬된 배열에서 중간 점을 찾아라, 우리는 P[n/2]를 중간점으로 취할 수 있다.
2) 주어진 배열을 두 개의 절반으로 나누어라. 첫 번째 부분배열은 P[0] ~ P[n/2]까지의 점들을 포함한다. 두 번째 배열은 P[n/2+1] ~ P[n-1]까지의 배열을 포함한다.
3) 재귀적으로 두 배열에서 가장 작은 거리들을 발견해라. 그 거리들이 dl과 dr이 디ㅗ도록 해라. dl과 dr중에 최소를 찾아라. 가장 작은 것이 d가 되도록 해라.
4) 위의 단계 3으로부터, 우리는 최소 거리의 상한을 가지게 된다. 이제 우리는 쌍에 있는 한 점이 왼쪽 반에 있는지 그리고 다른 것이 오른쪽 절반에 있는 그러한 쌍인지를 고려할 필요가 있다. P[n/2]를 관통하는 수직선을 고려하고, x좌표가 중간 수직선에 d보다 가까운 모든 점들을 찾아라. 모든 그러한 점들의 배열을 strip[]를 구성해라.
5) array strip[]을 y좌표에 따라 정렬해라. 이 단계는 O(nlgn)이다. 그것은 재귀적으로 정렬하고 합쳐서 O(n)으로 최적화 될 수 있다.
6) strip[]에서 가장 작은 거리를 찾아라. 이것은 까다롭다. 처음에 보기에, 그것은 O(n^2) 단계처럼 보이는 것 같지만, 그것은 실제로는 O(n)이다. strip에 있는 모든 점에 대해, 우리는 오직 그렇게 한 후에 대부분 7개의 점들만을 체크할 필요가 있따는 것이 기하학적으로 증명될 수 있다. (strip이 Y좌표에 따라 정렬된 것을 주목해라)
7) 마지막으로 d의 최소값과 위의 단계에서 계산된 거리를 반환해라.
Time Complexity : T(n) = T(n * lgn * lgn)
Notes
1) 시간 복잡도는 위의 알고리즘에서 단계 5를 최적화하여 O(nlgn)으로 개선되어질 수 있다. 우리는 곧 별개의 글에서 최적화된 솔루션을 다룰 것이다.
2) 그 코드는 가장 작은 거리를 찾는다. 가장 작은 거리를 가진 두 점을 찾도록 쉽게 수정될 수 있다.
3) 그 코드는 최악의 경우에 O(n^2)인 퀵정렬을 사용한다. upper bound가 O(n * (lgn)^2)을 갖기위해, merge sort 또는 heap sort같은 O(nlgn) 정렬 알고리즘이 사용될 수 있다.
=========================================
이 링크에 있는 코드로 따라서 구현했는데, 백준 문제에서 틀렸다고 나왔다.
댓글을 살펴보니 이 코드에는 문제가 많다고 한다 자연스럽게 잊어버리자.
그래서 확실한 자료인 Introduction to Algorithms 책을 통해서 구현하려고 한다.
놀랍게도, 가장 가까운 점들의 쌍을 찾는 부분은 이 책의 마지막 챕터 Computational Geometry에 있다.
=========================================
33.4 Finding the closest pair of points
우리는 이제 n >= 2인 점들의 집합 Q에서 가장 가까운 점들의 쌍을 찾는 문제를 고려한다. "가장 가까운"이라는 것은 보통 유클리드 거리를 말한다 : 두 점 p1과 p2사이의 거리는 root((x_1 - x_2)^2 + (y_1 - y_2)^2). 집합 Q에 있는 두 점들은 동일할지도 모른다. 그러한 경우에 그들 사이의 거리는 0이다. 이 문제는 실제로 교통-제어 시스템에 적용된다. 공중 또는 해상 교통을 제어하는 시스템은 잠재적인 충돌을 탐지하기 위해서 두 개의 가장 가까운 차량을 확인할 필요가 있을지도 모른다.
brute-force 방법의 가장 가까운 쌍 찾는 알고리즘은 간단히 (n 2) = Ө(n^2)의 쌍의 점들을 보는 것이다. 이 부분에서, 우리는 이 문제를 위해 분할정복을 묘사할 것이다. 이것의 작동 시간은 친밀한 재귀인 T(n) = 2T(n/2) + O(n)이다. 따라서 이 알고리즘은 오직 O(nlgn)의 시간을 사용한다.
The divide-and-conquer algorithm
그 알고리즘의 각 재귀 호출은 P ⊆ Q 인 한 부분집합과 배열 X, Y를 입력으로 받아들인다. 그리고 그 각각은 입력 부분집합 P의 모든 점들을 포함한다. 배열 X에 있는 점들은 그것들의 x좌표에 따라서 단조 증가로 정렬된다. 유사하게, 배열 Y는 단조 y-좌표 증가로 정렬된다. O(nlgn)의 시간 제한을 달성하기 위해서, 우리는 각 재귀 호출에서 정렬할 여유가 없다는 것에 유의해라; 만약 우리가 그렇게 했다면, 그 재귀의 작동시간은 T(n) = 2T(n/2) + O(nlgn)이 되고, 이것의 솔루션은 T(n) = O(n * (lgn)^2)이다. 우리는 나중에 각 재귀 호출에서 실제로 정렬하는 것 없이 어떻게 이 정렬된 property를 유지하기 위해 "presorting"을 사용하는지를 볼 것이다.
입력 P, X, Y와 함께 주어진 재귀 호출은 처음에 |P| <= 3인지를 확인한다. 만약 그렇다면, 그 호출은 간단히 위에서 언급된 brute-force 방법을 수행한다 : 점들의 모든 (|p| 2)의 쌍을 시도하고 가장 가까운 쌍을 반환해라. 만약 |P| > 3이라면, 그 재귀 호출은 다음의 분할정복 패러다임을 수행한다.
Divide : 점의 집합 P를 두 개의 집합 P_l과 P_r로 분할하는 수직선 l을 찾아라. 그 때 |P_l| = ceiling(|P|/2), |P_r| = floor(|P|/2)가 되도록 해라. P_l에 있는 모든 점들은 line l 왼쪽 또는 위에 있고, P_r에 있는 모든 점들은 l의 오른쪽 또는 위에 있다. 배열 X를 배열 X_L과 X_R로 나누어라. 그리고 그 배열들은 각각 P_L과 P_R의 점들을 포함한다. 이것들은 x좌표가 단조 증가로 정렬되어 있다. 유사하게, 그 배열 Y를 Y_L과 Y_R로 나누고, 그것들은 각각 P_L과 P_R의 점들을 포함하고 있는데 단조 y좌표 증가로 정렬되어 있다.
Conquer : P를 P_L과 P_R로 나눈 후에, 두 개의 재귀 호출을 만들어라. 하나는 P_L에서 가장 가까운 점들의 쌍을 찾는 것이고, 다른 하나는 P_R에서 가장 가까운 점들의 쌍을 찾는 것이다. 첫 번째 호출에 대한 입력은 subset P_L이고 배열 X_L과 Y_L이다; 두 번째 호출은 입력 P_R, X_R, 그리고 Y_R을 받는다. P_L과 P_R에 대해 가장 가까운 거리가 각각 &_L, &_R이 되도록 해라. 그리고 & = min(&_L, &_R)이 되도록 해라.
Combine : 가장 가까운 쌍은 그 재귀 호출들 중의 하나로 발견된 거리 &이거나 또는 P_L에 있는 한 점과 P_R에 있는 점이 있는 점들이ㅡ 한 쌍이다. 그 알고리즘은 P_L에 있는 한 점과 P_R을 한 점으로 하는 한 쌍이 있는 지를 검사하고, 그것의 거리가 &보다 작은 지를 검사한다. 만약 한 점들의 쌍이 &보다 더 작은 거리를 갖는다면, 그 쌍의 두 점들은 직선 l의 & 단위 내에 있어먄 한다. 따라서, 그림 33.11(a)가 보여주듯이, 그것들은 line l을 중심으로 2&-길이의 수직 strip내에 있어야만 한다. 그러한 쌍을 찾기위해서, 만약 존재한다면, 우리는 다음의 것을 한다:
- 배열 Y'를 만들어라. 그 배열은 2& 너비의 수직 strip에서 제거되지 않은 점들이 있는 배열이다. 그 배열 Y'는 y좌표로 정렬된다. Y가 그렇듯이.
- Y' 배열에 있는 각 점에 대해, p의 &단위 내에 있는 Y"에 있는 점들을 찾으려고 해라. 우리가 곧 보게 되듯이, p를 따르는 오직 Y'에 있는 7개의 점들이 고려될 필요가 있다. p에서 이러한 7개의 점들 가각까지의 거리를 계산하고, Y'에 있는 점들의 모든 쌍에 대해 발견된 가장 가까운 쌍의 거리 &'를 추적해라.
- 만약 &' < &라면, 그러면 수직 strip은 정말로 재귀호출이 발견한 것보다 더 가까운 쌍을 포함한다. 이 쌍과 그것의 거리 &'를 반환해라. 만약 그렇지 않으면, 재귀 호출에서 발견된 가장 가까운 쌍과 그것의 거리 &를 반환해라.
위의 묘사는 O(nlgn) 작동시간은 성취하는데 필요한 몇몇 세부 구현을 빠드렸다. 그 알고리즘의 정당성을 증명한 후에, 우리는 요구되는 시간 제한을 얻기 위해 그 알고리즘을 어떻게 구현할지를 보여줄 것이다.
Correctness
이 가장 가까운 쌍 알고리즘의 정당성은 두 가지 측면을 제외하고 명백하다. 첫 번째, |P| <= 3일 때 그 재귀의 바닥에 들어가서, 우리는 결코 오직 한 점으로 구성된 하위문제를 해결하려고 하지 않는 것을 보장한다. 두 번째 측면은 우리가 배열 Y'에 있는 각 점 p를 따르는 7개의 점들만을 체크할 필요가 있다는 것이다; 우리는 이제 이 특징을 증명할 것이다.
재귀의 어떤 level에서, 점들이ㅡ 가장 가까운 쌍이 p_L in P_L이고 p_R in P_R이라고 가정해보자. 따라서 p_L과 p_R 사이의 거리 &'는 &보다 엄격히 더 작다. 점 p_L은 직선 l의 왼쪽 또는 위에 있어야 하고, & 단위보다 더 작아야 한다. 유사하게 p_R은 직선 l의 오른쪽에 있거나 위에 있어야 하고 &단위보다 작아야 한다. 게다가 p_L과 p_R은 서로 수직으로 & units 내에 있어야만 한다. 따라서, 그림 33.11(a)가 보여주듯이, p_L과 p_R은 직선 l을 중심으로 & x 2& 사각형 내에 있다. (이 사각형내에 또다른 점이 있을지도 모른다.)
우리는 다음에 P의 많아봐야 8개의 점이 이 & x 2& 사각형 내에 있을 수 있다는 것을 보여준다. 이 사각형의 왼쪽 절반을 형성하는 & x & 사각형을 고려해라. P_L에 있는 모든 점들은 적어도 & units으로 떨어져있기 때문에, 최대 4개의 점들이 이 사각형에 있을 수 있다; 그림 33.11(b)가 어떻게 그러는지를 보여준다. 유사하게, P_R에 최대 4개의 점이 그 사각형의 오른쪽 절반을 구성하는 &x& square에 있을 수 있다. (직선 l에 있는 점들은 P_L 또는 P_R이기 때문에, l에 4개의 점까지 있을지도 모른다. 이 제한은 동일한 점 들의 두 쌍이 있다면 성취된다. 이 때 P_L의 한 점과 P_R의 한 점으로 각 쌍을 구성한다. 한 쌍은 l의 교차점과 그 사각형의 꼭대기에, 다른 쌍은 l이 사각형의 바닥을 교차하는 곳에 있다.)
P의 최대 8개의 점들이 그 사각형 내에 있다는 것을 보여준 후에, 우리는 쉽게 왜 우리가 Y' 배열에 있는 각 점을 따르는 7개의 점만을 체크할 필요가 있는지를 볼 수 있다. 여전히 가장 가까운 쌍이 p_L과 p_R이라고 가정하고, 일반성의 손실 없이 p_L이 Y'배열에서 p_R보다 더 앞에 있다고 가정하자. 그러고나서, 비록 p_L이 Y'에서 가능한한 일찍 발생하고, p_R이 가능한한 늦게 발생할지라도, p_R은 p_L을 따르는 7개의 위치중 하나에 있다. 따라서, 우리는 가장 가까운 쌍 알고리즘의 정당성을 보여줬다.
====================================
여기까지 번역해놓고 보니, geeksforgeeks 의 내용과 똑같다. 그 코드를 조금 수정하면 될 것 같다.
백준의 문제 질문을 찾아보니 해결책을 찾았다.
int divide_and_conquer(int start, int end) { int Size = end - start + 1; if (Size <= 3) return bruteForceDist(start, end); int mid = (start + end) / 2; int dl = divide_and_conquer(start, mid); int dr = divide_and_conquer(mid + 1, end); int min_d = min(dl, dr); vector<pii> strip; FOR(i, start, end + 1) if (pow(coordinates[i].first - coordinates[mid].first, 2) < min_d) strip.push_back(coordinates[i]); return min(min_d , stripClosest(strip, min_d)); }
밑의 FOR문의 if문에서 geeksforgeek는 제곱값이 아닌, 그냥 x좌표의 차이로 조건을 걸었다. 그런데 min_d는 거리의 제곱값이므로, min_d와 비교할려면 그와 똑같이 square를 해줘야한다. 만약 min_d를 (그러니까 bruteForceDist 값) square root값으로 했다면 그 if 문도 square root값으로 바꾸어 비교해야 한다.
https://www.acmicpc.net/blog/view/25
백준이 정리해놓은 line sweeping 알고리즘. 분할정복말고 이걸로 하는게 좀 더 깔끔하다.
확실히 더 영리한 방법이다.
https://www.acmicpc.net/problem/7574
가장 가까운 두 점을 쌍을 찾는 알고리즘을 활용한 문제라고 한다.
나중에 다시 풀어보자.
댓글 없음:
댓글 쓰기