Ch.8 정렬과 탐색
챕터8 종합퀴즈 — Sorting & Searching 총정리
챕터8의 모든 것을 한번에 점검합니다
O(n²) 정렬부터 Quick Sort, Binary Search 변형까지 — 챕터8에서 배운 정렬과 탐색의 핵심을 종합 퀴즈로 확인합니다.
개별 개념은 알겠는데, 섞여서 나오면 헷갈리지 않을까?
종합 퀴즈로 약점을 발견하고, 부족한 부분을 복습하세요.
핵심 내용
챕터8에서 배운 핵심 개념을 복습합니다
챕터8 키워드 정리: • 정렬: Bubble, Selection, Insertion, Merge, Quick • 탐색: Binary Search, lower/upper bound • 응용: Rotated Array, Merge Intervals • 핵심: 정렬은 전처리, 탐색은 O(log n)
다음 중 항상 O(n log n)을 보장하는 정렬 알고리즘은?
거의 정렬된 배열에서 가장 빠른 O(n²) 정렬은?
Linked List를 정렬할 때 가장 적합한 알고리즘은?
Quick Sort가 Merge Sort보다 실전에서 빠른 이유는?
lower_bound와 upper_bound의 코드 차이는?
회전 정렬 배열 [4,5,6,7,0,1,2]에서 최솟값의 인덱스는?
Merge Intervals의 시간 복잡도에서 정렬이 차지하는 비중은?
Quick Sort의 최악 O(n²)은 랜덤 피벗으로 완전히 제거할 수 있다
Merge Sort는 안정 정렬이고 Quick Sort는 불안정 정렬이다
Binary Search에서 mid = (lo + hi) // 2는 항상 안전한 계산이다
정렬된 배열에서 특정 값의 개수를 구하려면 upper_bound - lower_bound를 사용한다
Sorting & Searching 마스터!
정리 노트
Sorting & Searching 총정리
정렬 알고리즘
- O(n²)
- Bubble, Selection, Insertion(거의 정렬 시 O(n))
- O(n log n)
- Merge(안정, O(n) 공간), Quick(in-place, 캐시 친화)
- Python 내장
- Timsort = Merge + Insertion 하이브리드
탐색 알고리즘
- Binary Search
- 정렬 필수, O(log n), `lo + (hi - lo) // 2`
- lower/upper
- 경계 찾기 — 비교 연산자 `<` vs `<=` 차이
- Rotated Array
- 정렬된 쪽 판별 → 범위 좁히기
면접 필수 문제
- Merge Intervals
- 시작점 정렬 후 순회 — O(n log n)
- Search Rotated
- 정렬된 쪽에 target 있는지 판단
- Find Min Rotated
- `nums[mid]` vs `nums[hi]` 비교
정렬/탐색은 면접의 기본체력! 이 챕터를 확실히 마스터하세요.
시각 자료
핵심 정리
- 1O(n²) 정렬 3종과 O(n log n) 정렬 2종의 특성 비교
- 2Binary Search 기본 + lower/upper bound + rotated array
- 3면접 실전: Merge Intervals, Search Rotated, Find Min
- 4정렬은 전처리, 탐색은 O(log n) — 면접의 기본 체력
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작