Ch.8 정렬과 탐색
왜 정렬을 배우는가? — 정렬이 모든 것을 바꾼다
정렬 하나로 검색이 100배 빨라진다?
100만 명의 회원 데이터에서 특정 이름을 찾아야 합니다. 정렬되지 않은 데이터에서는 하나씩 봐야 하지만, 정렬되어 있으면 20번이면 끝납니다.
정렬은 비용이 드는데, 왜 거의 모든 시스템이 정렬을 사용할까?
정렬은 검색, 중복 제거, 병합, 통계 등 거의 모든 알고리즘의 기반입니다.
핵심 개념
정렬(Sorting)
데이터를 특정 기준에 따라 순서대로 배열하는 작업
전처리(Preprocessing)
본 작업 전에 데이터를 효율적으로 가공하는 단계
핵심 내용
도서관의 책이 아무 순서 없이 꽂혀 있다면?
100만 권의 책에서 원하는 책을 찾으려면 평균 50만 번 확인해야 합니다
하지만 가나다순으로 정렬되어 있다면? 20번 만에 찾을 수 있습니다
이것이 정렬의 힘입니다. O(n) 검색이 O(log n)으로 바뀝니다
정렬 전후의 차이를 시각적으로 비교해봅시다
정렬 전 — 검색 O(n), 중복 제거 O(n²), 최솟값 O(n) 정렬 후 — 검색 O(log n), 중복 제거 O(n), 최솟값 O(1)
정렬 비용은 O(n log n)이지만 이후 모든 연산이 극적으로 빨라집니다
코딩 면접에서 정렬 문제는 가장 자주 출제됩니다
정렬/탐색 문제가 나오는 이유: 1. 기본기 확인 — 정렬 알고리즘의 동작 원리 2. 최적화 능력 — O(n²) → O(n log n) 개선 3. 응용력 — 정렬을 활용한 문제 해결
# 면접 빈출: 두 배열의 교집합
def intersection_brute(a, b):
# O(n * m) — 느린 방법
return [x for x in a if x in b]
def intersection_sort(a, b):
# O(n log n) — 정렬 활용
a.sort()
b.sort()
result, i, j = [], 0, 0
while i < len(a) and j < len(b):
if a[i] == b[j]:
result.append(a[i])
i += 1; j += 1
elif a[i] < b[j]:
i += 1
else:
j += 1
return result정렬을 전처리로 활용하면 Brute Force보다 훨씬 효율적인 풀이가 가능합니다
정렬 알고리즘은 크게 두 그룹으로 나뉩니다
느린 정렬 O(n²): Bubble Sort, Selection Sort, Insertion Sort → 구현 쉬움, 소규모 데이터에 적합 빠른 정렬 O(n log n): Merge Sort, Quick Sort, Heap Sort → 대규모 데이터에 필수
면접에서는 O(n log n) 정렬의 원리를 설명할 수 있어야 합니다
Python의 `sorted()`는 Timsort — Merge + Insertion의 하이브리드, 평균 O(n log n)입니다
정렬된 배열에서 원소를 검색할 때 최적의 시간 복잡도는?
정렬의 시간 복잡도가 O(n log n)이므로 항상 정렬 후 검색하는 것이 유리하다
정렬의 세계로 출발!
핵심 용어
정렬(Sorting)
데이터를 특정 기준에 따라 순서대로 배열하는 작업
전처리
본 작업 전에 데이터를 효율적으로 가공하는 단계
정리 노트
왜 정렬을 배우는가?
핵심 개념
- 정렬의 역할
- 검색·중복 제거·병합 등의 전처리 단계
- O(n²) 정렬
- Bubble, Selection, Insertion — 소규모용
- O(n log n) 정렬
- Merge, Quick, Heap — 대규모 필수
면접 팁
- 정렬 활용
- Brute Force O(n²) → 정렬 후 투포인터 O(n log n)
- Python 내장
- `sorted()` = Timsort O(n log n)
면접에서 '정렬하면 더 빠를 수 있을까?'를 항상 고려하세요!
시각 자료
핵심 정리
- 1정렬은 검색·중복 제거 등 모든 알고리즘의 기반
- 2정렬 후 검색은 O(n) → O(log n)으로 개선
- 3면접에서 정렬/탐색은 가장 빈출 주제
퀴즈와 인터랙션으로 더 깊이 학습하세요
play_circle인터랙티브 레슨 시작