SelectionAlgorithm (1) 썸네일형 리스트형 [Algorithm] 선택 문제 Selection Problem - C언어 분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 선택 문제(Selection Problem) : k번째 작은 수를 찾는 문제 입력에서 퀵 정렬에서와 같이 피봇을 선택하여 피봇보다 작은 부분과 큰 부분으로 분할한 후에 k번째 작은 수가 들어 있는 부분을 순환적으로 탐색한다. unsorted array : 최소 숫자를 k번 찾는다. -> 최악 시간복잡도 : O(kn) ** 단, 최소 숫자를 찾은 뒤에는 입력에서 최소 숫자를 제거한다. sorted array : 숫자들을 정렬한 후, k번째 숫자를 찾는다. -> 최악 시간복잡도 : O(nlogn) pseudo code Selection(A, left, rig.. 이전 1 다음
