3)선택 문제 알고리즘

 

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

 


#유사코드

 

 

#파이썬 소스

 

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

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

 

 

 

4)최근접 점의 쌍 문제

 

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

 

 

#유사코드

 

 

#파이썬 소스

 

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

 

+ Recent posts