분할정복2 [알고리즘] Divide & Conquer (3) - Quick sort [3. Quick sort, 쾌속 정렬] ● 방식 → 집합 A의 원소들을 오름차순으로 정렬하고자 할 때(또는 내림차순) → 집합 내의 원소 중 하나를 무작위로 골라 (주로 A[0]=pivot) → pivot을 기준으로 pivot보다 작은 원소는 pivot의 앞에 → pivot보다 큰 원소는 pivot의 뒤에 배치한다. → 이 때, pivot을 제외한 맨 앞과 맨 뒤의 값들을 서로 비교하여 → 앞의 값이 뒤의 값보다 클 경우, 자리를 서로 바꾼다. → 배열을 두 개로 분할한다는 점에서 합병정렬과 비슷하지만, 결합하지 않으므로 합병정렬의 발전형이라 할 수 있다. ● 알고리즘 → Divide : m=Partition() → Conquer : Quick_sort(s, m-1, A), Quick_sort(m+1,.. 2022. 11. 8. [알고리즘] Divide & Conquer (1) - Binary search [1. Binary search, 이진탐색] ● 방식 → A를 오름차순으로 정렬된 n개 요소들의 리스트라고 할 때, → 찾으려는 값 x가 A내에 몇 번째에 존재하는지 확인하는 알고리즘이다. → x를 A내의 요소들의 중앙값(A[m])과 비교하여 → x = A[m]이면 m을 반환, → x A[m]이면 다시 x를 A[m+1 ~ e]에서 탐색하는 방식이다. (* A내에 n개의 원소가 있다면 s=0, e=n-1) ● 알고리즘 → Divide : m = (s+e)/2를 기준으로 배열을 분할 → Conquer : A[s, m-1] 또는 A[m+1, e] → Degenerate case : A 또는 분할된 A 내에 원소가 하나인 경우 (s==e) ● .. 2022. 11. 5. 이전 1 다음
