CodeAngie

이제 알고리즘의 허리 역할을 하는 정렬과 탐색로 넘어가보자. 공무원 시험에서는 이 정렬 알고리즘이 얼마나 빠른지(시간 복잡도), 메모리는 얼마나 쓰는지(공간 복잡도), 그리고 데이터가 어떻게 변하는지를 묻는다. 1. 정렬의 양대 산맥: 퀵(Quick) vs 병합(Merge)이 둘은 모두 분할 정복(Divide & Conquer)을 사용하고 평균 $O(n \log n)$으로 매우 빠르지만, 성격이 완전 다르다.(1) 퀵 정렬 (Quick Sort) - "불안정하지만 빠른 천재"원리: **피벗(Pivot)**이라는 기준점을 하나 잡는다. 피벗보다 작은 놈은 왼쪽, 큰 놈은 오른쪽으로 몰아넣고(Partition) 양쪽을 각각 다시 재귀 호출한다.장점: 추가 메모리가 거의 필요 없고(In-place), 캐시 효..