컴공생의 발자취

분할 정복 알고리즘(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..

분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 퀵 정렬(QuickSort) 피봇(pivot)이라 일컫는 배열의 원소(숫자)를 기준 피봇보다 작은 숫자들은 왼쪽, 큰 숫자들은 오른쪽으로 위치하도록 분할 분할된 부분문제들에 대해서도 위와 동일한 과정으로 재귀적으로 수행 개념 설명 ** 해당 설명에서 pivot은 무작위로 정해짐 ** pseudo code QuickSort(A, left, right) 입력 : 배열A[left] ~ A[right] 출력 : 정렬된 배열A[left] ~ A[right] if(left < right){ 피봇을 A[left] ~ A[right] 중에서 선택하고 피봇을 A[left..

분할 정복 알고리즘(Divide-and-Conquer) 합병정렬 MergeSort 퀵 정렬 QuickSort 선택 문제 Selection Problem 합병정렬(MergeSort) : 입력이 2개의 부분문제로 분할되고, 부분문제의 크기가 1/2로 감소하는 분할 n개의 숫자들을 n/2개의 부분문제로 분할(Divide) 각각의 부분문제들을 해결(Conquer) 재귀적으로 합병 정렬(Merge) 개념 설명 Pseudo code MergeSort(A, p, q) 입력 : A[p] ~ A[q] 출력 : 정렬된 A[p] ~ A[q] if(p < q){ // 배열의 원소의 수가 2개 이상이면 k = [(p+q)/2] // k : 반으로 나누기 위한 중간 원소의 인덱스(내림으로) MergeSort() // 앞부분 재귀..