목록선택문제 구현 (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..
📖 이론/컴퓨터 알고리즘 2023. 6. 11. 14:04
이전 Prev 1 Next 다음