[알고리즘]분할 정복 알고리즘2

3)선택 문제 알고리즘

 

k번째 작은 수를 찾는 문제로서, 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k 번째 작은 수가 들어있는 부분을 재귀적으로 탐색한다. 평균 경우 시간복잡도는 O(n)이다.

 

#유사코드

 

Selection(A, left, right, k) 입력: A[left]~A[right]와 k, 단, 1≤k≤|A|, |A|=right-left+1 출력: A[left]~A[right]에서 k 번째 작은 원소 1. 피봇을 A[left]~A[right]에서 랜덤하게 선택하고, 피봇과 A[left]의 자리를 바꾼 후, 피봇과 배열의 각 원소를 비교하여 피봇보다 작은 숫자는 A[left]~A[p-1]로 옮기고, 피봇보다 큰 숫자는 A[p+1]~A[right]로 옮기며, 피봇은 A[p]에 놓는다. 2. S = (p-1)-left+1 // S = Small group의 크기 3. if ( k ≤ S ) Selection(A, left, p-1, k) // Small group에서 찾기 4. else if ( k = S +1) return A[p] // 피봇 = k번째 작은 숫자 5. else Selection(A, p+1 right, k-S-1) // large group에서 찾기

 

#파이썬 소스

 

*퀵 정렬 참고해서 작성해주시기 바랍니다!!

주의 : 피봇을 왼쪽으로 옮겼다가 중앙으로 옮길 때 (1~p)인덱스를 하나씩 앞으로 땡겨주고 p자리에 피봇을 넣어줘야 합니다

 

 

 

4)최근접 점의 쌍 문제

 

n개의 점들을 1/2로 분할하여 각각의 부분 문제에서 최근접 점의 쌍을 찾고, 2개의 부분해 중에서 짧은 거리를 가진 점의 쌍을 일단 찾는다. 그리고 2개의 부분해를 취합할 때, 반드시 중간 영역 안에 있는 점들 중에 최근접 점의 쌍이 있는지도 확인해보아야 한다. 시간복잡도는 O(nlogn)이다.

 

 

#유사코드

 

ClosestPair(S) 입력: x-좌표의 오름차순으로 정렬된 배열 S에는 i개의 점 (단, 각 점은 (x,y)로 표현된다.) 출력: S에 있는 점들 중 최근접 점의 쌍의 거리 1. if (i ≤ 3) return (2 또는 3개의 점들 사이의 최근접 쌍) 2. 정렬된 S를 같은 크기의 SL과 SR로 분할한다. |S|가 홀수이면, |SL| = |SR|+1이 되도록 분할한다. 3. CPL = ClosestPair(SL) // CPL은 SL에서의 최근접 점의 쌍 4. CPR = ClosestPair(SR) // CPR은 SR에서의 최근접 점의 쌍 5. d = min{dist(CPL), dist(CPR)}일 때, 중간 영역에 속하는 점들 중에서 최근접 점의 쌍을 찾아서 이를 CPC라고 하자. 단, dist()는 두 점 사이의 거리이다. 6. return (CPL, CPC, CPR 중에서 거리가 가장 짧은 쌍)

 

#파이썬 소스

 

이건 파이썬 2차원 배열 좀더 배우고 올리겠습니다 스미마셍...