Quick sort
·
📚 STUDY/📈 알고리즘
Divide-and-conquer를 기반으로 하는 정렬 알고리즘으로, 방식은 아래와 같다.1. Pivot 선택 : 배열에서 하나의 원소를 pivot으로 선택한다. 2. 분할 : pivot을 기준으로 pivot보다 작은 원소는 왼쪽, 큰 원소는 오른쪽으로 배열한다.3. 재귀 호출 : 왼/오른쪽 부분 배열에 quick sort를 재귀적으로 수행한다. 💡 이상적인 경우 pivot이 항상 배열을 거의 절반으로 나누는 경우, T(n) = 2T(n/2)+O(n) 재귀식을 따른다.마스터 정리를 이용하면, T(n)=O(nlogn)이 된다. 💡 최악의 경우pivot이 항상 가장 작거나 or 큰 원소를 선택하는 경우이다.(= 배열이 거의 정렬되어 있거나 역순일 때 잘못된 pivot을 선택한다는 말)이때, partit..
Divide-and-Conquer Algorithm
·
📚 STUDY/📈 알고리즘
📌 Divide-and-Conquer Algorithm이란문제를 여러 부분으로 나눈 뒤, 각 부분을 재귀적으로 해결한다.그 후, 각 부분의 해답을 결합해 전체 문제의 해답을 도출한다.분할(Divide): 문제를 더 작은 하위 문제로 나눈다.정복(Conquer): 하위 문제를 재귀적으로 해결한다.결합(Combine): 하위 문제의 해를 결합하여 전체 문제를 해결한다.📌 Merge Sortdivide-and-conquer 방식 기반으로 동작문제를 나눠 해결하고, 통합하는 방식 시간 복잡도분할단순히 배열을 반으로 자르는 작업으로, 한 번 나눌 때 걸리는 시간은 상수 시간 O(1)전체 분할은 트리 구조로 log₂n 단계까지 진행됨.✅ O(log₂n)정복두 배열을 순회하면서 합치는 과정 O(n)병합은 트리 구..