Closet Pair Problem
step1.
- 주어진 점들을 두 부분 집합 SL, SR로 수직선 x = c로 나눔
- 점의 반은 왼쪽이나 선에 있고 반은 오른쪽이나 선에 있음
- x좌표 기준으로 모든 점을 정렬하면 쉽게 중심 c를 구할 수 있음 -> O(NlogN)
step2.
- 왼쪽 및 오른쪽 부분 집합에 대해 가장 가까운 쌍을 재귀적으로 찾음
- 만약 |Si| <= 3, 브루트포스로 가장 가까운 쌍 찾기 -> O(1)
step3.
- d = min(dL, dR), CL과 CR을 각각 이 수직 스트립에 있는 오른쪽 부분 집합 SL과 왼쪽 부분 집합 SR의 점 부분 집합으로 둠
- CL 및 CR의 점은 x및 y 좌표의 오름차순으로 저장됨
- y에 대한 정렬로 다음 단계에서 merge에 의한 최소 거리 탐색
step4.
- CL의 모든 점 P(x,y)에 대해 d보다 p에 가까울 수 있는 CR의 점을 검사함
- d <= d2이기 때문에 이러한 점은 8개를 초과할 수 없음
효율성
- 점을 2개의 배열에서 x-좌표값과 y-좌표값으로 정렬하여 점을 2개의 집합으로 균등하게 나누고 계산을 최소화하며 하위 문제의 솔루션을 쉽게 결합한다고 가정함
- T(n) = 2T(n/2) + M(n), where M(n) ∈ O(n)
- 마스터 정리에 의해 (a = 2, b = 2, d = 1) T(n) ∈ O(n log n)
Quickhull Algorithm
- n차원 공간에서 유한한 점 집합의 볼록 선체를 계산하는 방법임
- 이름이 파생된 퀵 정렬과 유사함 분할 및 정복 접근 방식을 사용함
- 최악의 시간 복잡도: O(n^2)
- 평균 시간 복잡도: O(nlogn)
- 주어진 점의 분포에 대한 합리적인 가정하에 O(n)
- 처음에 x좌표 값으로 정렬되지 않은 경우, O(nlogn)시간 내에 수행할 수 있음
- 점 두 개를 하위 집합으로 나눔
- 거리가 최대인 점을 찾고 삼각형 내부의 점을 무시하고 재귀함
- 점이 더 이상 남아있지 않을 때까지 반복함
출처: https://en.wikipedia.org/wiki/Quickhull
결론
-
매우 효율적인 알고리즘
-
재귀적으로 설명 가능될 수 있음
- 같은 문제의 작은 사례들의 관점에서
-
문제 해결 과정은 재귀적으로 설명될 수 있음
- 즉, 작은 인스턴스의 솔루션을 결합해 원래 문제의 솔루션을 얻을 수 있음
-
문제가 적어도 같은 크기의 두 부분으로 나누어져 있다고 가정함. 단순히 상수 계수에 의해 감소하는 것이 아님
분할 정복이 부적절한 경우
-
입력이 분할될 때마다 분할된 부분 문제의 입력 크기의 합이 분할되기 전의 입력 크기보다 매우 커질 때
- n번째의 피보나치 수를 구하기
- F(n) = F(n-1) + F(n-2)로 정의되므로 순환 호출을 사용하는 것이 자연스러워 보이나, 이 경우의 입력은 1개이지만, 사실상 n의 값 자체가 입력 크기임
- 2개의 부분 문제인 F(n-1)과 F(n-2)의 입력크기는 (n-1) + (n+2) = (2n- 3)이 되어서, 분할 후 입력 크기는 거의 2배로 증가함
- n번째의 피보나치 수를 구하기
-
취합(정복) 과정에 주의
- 입력 분할로 항상 효율적인 알고리즘이 만들어지는 것은 아님
- 기하(geometry)에 관련된 다수의 문제들이 효율적인 분할 정복 알고리즘으로 해결되는데, 이는 기하 문제들의 특성상 취합 과정이 문제 해결에 잘 부합되기 때문임
Transform Conquer
Basic idea
- 같은 문제의 더 간단한/더 편리한 예로 (간소화)
- 동일한 인스턴스의 다른 표현(표현 변경)으로
- 알고리즘을 이미 사용할 수 있는 다른 문제로 (문제 감소)
- 문제 인스턴스를 동일한 문제의 소규모 인스턴스로 축소하고 솔루션 확장
Presorting
- 목록을 정렬하면 목록과 관련된 많은 문제가 더 쉬워짐
•
검색
• 중위수 계산(중위수 문제)
• 모든 요소가 고유한지 확인(단일성 포함)
