통합 요약노트
Ch.8 정렬과 탐색
Merge Sort, Quick Sort, Binary Search — 정렬과 탐색의 정석
이 챕터의 내용
왜 정렬을 배우는가? — 정렬이 모든 것을 바꾼다
정렬은 검색, 중복 제거, 병합, 통계 등 거의 모든 알고리즘의 기반입니다.
도서관의 책이 아무 순서 없이 꽂혀 있다면?
100만 권의 책에서 원하는 책을 찾으려면 평균 50만 번 확인해야 합니다
하지만 가나다순으로 정렬되어 있다면? 20번 만에 찾을 수 있습니다
- 정렬은 검색·중복 제거 등 모든 알고리즘의 기반
- 정렬 후 검색은 O(n) → O(log n)으로 개선
- 면접에서 정렬/탐색은 가장 빈출 주제
O(n²) 정렬 — Bubble, Selection, Insertion
O(n²) 정렬을 이해해야 O(n log n) 정렬이 왜 빠른지 비교 설명할 수 있습니다.
거품이 수면 위로 올라오듯 큰 값이 뒤로 밀려납니다
`swapped` 플래그로 이미 정렬된 경우 조기 종료할 수 있습니다 — 최선 O(n)
Bubble Sort가 배열을 어떻게 정렬하는지 추적합니다
- Bubble Sort — 인접 교환, 조기 종료 최적화
- Selection Sort — swap 최소, 불안정
- Insertion Sort — 거의 정렬 시 O(n), Timsort의 핵심
Merge Sort — 분할 정복의 정석
분할의 깊이는 log n, 각 층에서 n번 비교 — 합하면 O(n log n)입니다.
큰 문제를 반으로 나누고 작은 문제부터 해결합니다
배열 [5, 3, 8, 1]을 예시로 Merge Sort 과정을 봅시다
핵심은 merge 함수입니다. 두 정렬된 배열을 합치는 로직
- Merge Sort = Divide + Conquer + Merge
- 항상 O(n log n), 공간 O(n)
- 안정 정렬, Linked List에 최적
Quick Sort — 피벗과 파티셔닝
좋은 피벗을 고르면 매번 절반으로 나뉘어 O(n log n) — 이것이 Quick Sort의 핵심입니다.
Quick Sort의 핵심은 파티셔닝 한 단계입니다
간결한 Python 구현과 In-place 구현을 비교합니다
면접에서는 in-place partition을 직접 구현할 수 있어야 합니다
- Quick Sort = 피벗 선택 + 파티셔닝 + 재귀
- 평균 O(n log n), 최악 O(n²) — 랜덤 피벗으로 방지
- Array 정렬의 실전 표준 (캐시 친화적)
Binary Search — 반씩 줄이는 탐색
불변식(invariant)을 유지하면 off-by-one 에러 없이 깔끔하게 구현할 수 있습니다.
정렬된 배열이라면 절반씩 줄일 수 있습니다
n = 1,000,000일 때 log₂(1,000,000) ≈ 20번 비교면 충분합니다
불변식: **target이 있다면 arr[lo..hi] 범위 안에 있다**
- 정렬된 배열 + 절반씩 줄이기 = O(log n)
- 불변식 유지로 경계값 실수 방지
- Python bisect 모듈로 간결하게 구현 가능
Binary Search 변형 — lower bound, upper bound, rotated array
lower bound와 upper bound 패턴을 익히면 거의 모든 Binary Search 변형을 풀 수 있습니다.
lower_bound: target 이상인 첫 번째 위치를 찾습니다
기본 Binary Search와 차이: `while lo < hi` + `hi = mid` (mid - 1이 아님!)
upper_bound: target 초과인 첫 번째 위치를 찾습니다
- lower/upper bound — 경계 찾기 패턴
- Rotated array — 정렬된 쪽 판별이 핵심
- 3가지 패턴으로 모든 Binary Search 변형 대응
면접실전 — Merge Intervals, Search Rotated, Find Min Rotated
패턴 인식 → 자료구조 선택 → 구현의 3단계로 체계적으로 접근합니다.
LeetCode #56 — Merge Intervals 면접 빈출도 최상위
핵심 아이디어: 시작점 기준 정렬 후 순차적으로 겹침 여부 확인
정렬이 핵심! 정렬 없이는 모든 쌍을 비교해야 O(n²). 정렬하면 한 번 순회로 해결
- Merge Intervals — 정렬 후 한 번 순회
- Search Rotated — 정렬된 쪽 판별이 핵심
- Find Min Rotated — nums[hi]와 비교
챕터8 종합퀴즈 — Sorting & Searching 총정리
종합 퀴즈로 약점을 발견하고, 부족한 부분을 복습하세요.
챕터8에서 배운 핵심 개념을 복습합니다
다음 중 항상 O(n log n)을 보장하는 정렬 알고리즘은?
거의 정렬된 배열에서 가장 빠른 O(n²) 정렬은?
- O(n²) 정렬 3종과 O(n log n) 정렬 2종의 특성 비교
- Binary Search 기본 + lower/upper bound + rotated array
- 면접 실전: Merge Intervals, Search Rotated, Find Min
- 정렬은 전처리, 탐색은 O(log n) — 면접의 기본 체력
핵심 용어 모음
정렬(Sorting)
데이터를 특정 기준에 따라 순서대로 배열하는 작업
전처리
본 작업 전에 데이터를 효율적으로 가공하는 단계
시간 복잡도
최선 O(n), 평균/최악 O(n²)
공간 복잡도
O(1) — in-place
안정 정렬
같은 값의 순서 유지
Divide
배열을 반으로 나눈다
Conquer
각 반쪽을 재귀적으로 정렬한다
Merge
정렬된 두 배열을 합친다
피벗 선택
기준 원소를 하나 고른다
파티셔닝
피벗 기준 좌/우로 분리
재귀
좌/우 각각에 같은 작업 반복
전제 조건
배열이 **정렬**되어 있어야 함
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 코스 시작하기