기초 정렬 알고리즘: 버블·선택·삽입 정렬의 동작과 O(n²)인 이유
이 글의 핵심
기초 정렬은 실무에서 직접 쓸 일이 드물지만, 비교·교환 횟수를 세어 보면 복잡도 분석의 감각이 생깁니다. 버블 정렬 조기 종료 최적화 누락, 선택 정렬이 불안정한 이유, 역순 입력에서 삽입 정렬이 최악이 되는 경우, 오프바이원 실수를 트러블슈팅으로 다룹니다.
시리즈 안내
들어가며
버블·선택·삽입 정렬은 모두 O(n²) 시간 복잡도를 가지지만 구현이 간단하고, 비교·교환 횟수를 직접 세어 볼 수 있어 복잡도 분석을 연습하기에 좋습니다. 원소가 아주 적거나 거의 정렬된 입력에서는 지금도 실제 라이브러리 안에서 쓰입니다.
세 알고리즘이 모두 O(n²)인 이유는 한 문장으로 설명할 수 있습니다. 한 번의 비교나 교환이 해결하는 “순서가 틀린 쌍”이 최대 하나뿐이기 때문입니다. 배열에서 앞의 원소가 뒤의 원소보다 큰 쌍을 역전(inversion)이라고 하는데, 역순 배열에는 이런 쌍이 n(n-1)/2개 있습니다. 인접한 두 원소를 바꾸는 연산은 역전을 정확히 하나만 줄이므로, 버블 정렬과 삽입 정렬은 최악의 경우 이 개수만큼 일을 해야 합니다. 병합·퀵 정렬처럼 O(n log n) 알고리즘이 빠른 것은 멀리 떨어진 원소를 한 번에 옮겨 여러 역전을 동시에 해소하기 때문입니다. 이 관점을 가지고 아래 구현들을 보면, 각 알고리즘이 어떤 입력에서 빨라지고 느려지는지가 자연스럽게 설명됩니다.
버블 정렬 (Bubble Sort)
알고리즘 원리
인접한 두 요소를 비교하며 큰 값을 뒤로 보냅니다. 한 바퀴 돌 때마다 가장 큰 값이 “거품처럼” 맨 뒤로 올라갑니다. 시각화:
[5, 2, 4, 1, 3]
↓ 비교 & 교환
[2, 5, 4, 1, 3] (5 > 2 → 교환)
↓
[2, 4, 5, 1, 3] (5 > 4 → 교환)
↓
[2, 4, 1, 5, 3] (5 > 1 → 교환)
↓
[2, 4, 1, 3, 5] ← 5가 제자리
1회전 완료, 다음 회전은 [2, 4, 1, 3]만 정렬Python 구현
def bubble_sort(arr):
"""
버블 정렬
- 인접 요소 비교
- 최적화: 교환 없으면 조기 종료
"""
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(bubble_sort(arr)) # [1, 2, 3, 4, 5]
# 이미 정렬된 경우
arr = [1, 2, 3, 4, 5]
print(bubble_sort(arr)) # [1, 2, 3, 4, 5] (1회전만 실행)C++ 구현
#include <vector>
#include <iostream>
void bubbleSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
bool swapped = false;
for (int j = 0; j < n - 1 - i; ++j) {
if (arr[j] > arr[j + 1]) {
std::swap(arr[j], arr[j + 1]);
swapped = true;
}
}
if (!swapped) break;
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
bubbleSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n) — 이미 정렬됨 (최적화 버전)
- 평균: O(n²)
- 최악: O(n²) — 역순 정렬
- 공간: O(1) — in-place
- 안정: O — 같은 값의 순서 유지
버블 정렬이 안정적인 이유는 비교 조건이 >이기 때문입니다. 같은 값끼리는 교환하지 않으므로 먼저 나온 원소가 계속 앞에 남습니다. 이 조건을 >=로 바꾸면 결과는 여전히 정렬되지만 같은 값의 순서가 뒤집혀 불안정해지므로, 사소해 보이는 부등호 하나가 안정성을 결정한다는 점을 기억해 두세요. swapped 조기 종료가 있어도 평균이 O(n²)인 것은, 한 회전에 원소가 뒤쪽으로는 여러 칸 이동할 수 있지만 앞쪽으로는 한 칸밖에 못 가기 때문입니다. 작은 값이 배열 끝에 있으면(예: [2, 3, 4, 5, 1]) 그 값이 앞으로 오는 데 n-1회전이 필요하며, 이런 원소를 흔히 “거북이”라고 부릅니다. 양방향으로 번갈아 훑는 칵테일 정렬이 이 문제를 줄이려는 변형이지만, 점근적 복잡도는 같습니다.
선택 정렬 (Selection Sort)
알고리즘 원리
최솟값을 찾아 맨 앞과 교환합니다. 매 회전마다 정렬된 부분이 1개씩 증가합니다. 시각화:
[5, 2, 4, 1, 3]
↓ 최솟값 1 찾음
[1, 2, 4, 5, 3] ← 1 제자리
↓ 최솟값 2 찾음
[1, 2, 4, 5, 3] ← 2 제자리
↓ 최솟값 3 찾음
[1, 2, 3, 5, 4] ← 3 제자리
↓ 최솟값 4 찾음
[1, 2, 3, 4, 5] ← 완료Python 구현
def selection_sort(arr):
"""
선택 정렬
- 최솟값 선택
- 항상 O(n²)
"""
n = len(arr)
for i in range(n):
min_idx = i
for j in range(i + 1, n):
if arr[j] < arr[min_idx]:
min_idx = j
arr[i], arr[min_idx] = arr[min_idx], arr[i]
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(selection_sort(arr)) # [1, 2, 3, 4, 5]C++ 구현
#include <vector>
#include <algorithm>
#include <iostream>
void selectionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 0; i < n; ++i) {
int min_idx = i;
for (int j = i + 1; j < n; ++j) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
std::swap(arr[i], arr[min_idx]);
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
selectionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n²) — 이미 정렬되어도 최솟값 탐색 필요
- 평균: O(n²)
- 최악: O(n²)
- 공간: O(1)
- 안정: X — 교환 시 순서 바뀔 수 있음
선택 정렬은 입력과 관계없이 비교 횟수가 항상 n(n-1)/2로 똑같다는 점이 특징입니다. 이미 정렬된 배열이든 역순이든 남은 구간 전체를 훑어야 최솟값을 확신할 수 있기 때문입니다. 대신 교환은 최대 n-1번으로, 세 알고리즘 중 쓰기가 가장 적습니다. 그래서 비교는 싸고 쓰기는 비싼 환경(쓰기 횟수에 수명이 있는 플래시 메모리, 원소가 큰 구조체라 복사 비용이 큰 경우)에서는 이론적인 장점이 있습니다. 구현에서 흔한 실수는 min_idx == i일 때도 교환하는 것인데, 결과는 맞지만 쓰기를 줄인다는 장점을 살리려면 if min_idx != i: 조건을 두는 편이 좋습니다.
삽입 정렬 (Insertion Sort)
알고리즘 원리
정렬된 부분에 새 요소를 삽입합니다. 카드 정렬하듯이 왼쪽은 항상 정렬 상태를 유지합니다. 시각화:
[5, 2, 4, 1, 3]
[5] 2 4 1 3 ← 5는 정렬됨
[2, 5] 4 1 3 ← 2를 5 앞에 삽입
[2, 4, 5] 1 3 ← 4를 2와 5 사이에 삽입
[1, 2, 4, 5] 3 ← 1을 맨 앞에 삽입
[1, 2, 3, 4, 5] ← 3을 2와 4 사이에 삽입Python 구현
def insertion_sort(arr):
"""
삽입 정렬
- 정렬된 부분에 삽입
- 거의 정렬된 배열에 유리
"""
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j + 1] = arr[j]
j -= 1
arr[j + 1] = key
return arr
# 테스트
arr = [5, 2, 4, 1, 3]
print(insertion_sort(arr)) # [1, 2, 3, 4, 5]
# 거의 정렬된 경우
arr = [1, 2, 4, 3, 5]
print(insertion_sort(arr)) # [1, 2, 3, 4, 5] (빠름)C++ 구현
#include <vector>
#include <iostream>
void insertionSort(std::vector<int>& arr) {
int n = arr.size();
for (int i = 1; i < n; ++i) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
--j;
}
arr[j + 1] = key;
}
}
int main() {
std::vector<int> arr = {5, 2, 4, 1, 3};
insertionSort(arr);
for (int num : arr) {
std::cout << num << " ";
}
// 출력: 1 2 3 4 5
return 0;
}시간복잡도
- 최선: O(n) — 이미 정렬됨
- 평균: O(n²)
- 최악: O(n²) — 역순 정렬
- 공간: O(1)
- 안정: O — 같은 값은 순서 유지
삽입 정렬의 이동 횟수는 정확히 입력의 역전 개수와 같습니다. while 루프가 한 번 돌 때마다 key보다 큰 원소 하나를 오른쪽으로 밀어내는데, 그 원소와 key가 바로 하나의 역전 쌍이기 때문입니다. 그래서 복잡도를 O(n + 역전 수)로 쓰는 것이 더 정확하며, 원소마다 제자리에서 몇 칸 이내로만 벗어나 있는 “거의 정렬된” 데이터에서는 선형 시간에 가깝게 끝납니다. 또 새 원소가 들어올 때마다 정렬 상태를 유지하는 온라인 알고리즘이라, 데이터가 하나씩 도착하는 상황에서 매번 전체를 다시 정렬하지 않아도 된다는 장점이 있습니다.
구현에서 가장 흔한 버그는 while 조건의 순서입니다. arr[j] > key and j >= 0처럼 순서를 바꾸면 C++에서는 j가 -1일 때 arr[-1]을 읽는 범위 밖 접근(정의되지 않은 동작)이 됩니다. Python에서는 음수 인덱스가 마지막 원소를 가리키므로 예외 없이 넘어가 버리고, 그래서 Python으로 먼저 검증한 코드를 C++로 옮길 때에야 문제가 드러나곤 합니다. 경계 검사를 먼저 쓰는 단락 평가(short-circuit) 순서가 핵심입니다.
기본 정렬 비교표
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 | 특징 |
|---|---|---|---|---|---|---|
| 버블 | O(n) | O(n²) | O(n²) | O(1) | O | 구현 간단, 최적화 가능 |
| 선택 | O(n²) | O(n²) | O(n²) | O(1) | X | 항상 O(n²) |
| 삽입 | O(n) | O(n²) | O(n²) | O(1) | O | 거의 정렬된 배열에 유리 |
고급 정렬 비교
| 알고리즘 | 최선 | 평균 | 최악 | 공간 | 안정 |
|---|---|---|---|---|---|
| 퀵 | O(n log n) | O(n log n) | O(n²) | O(log n) | X |
| 병합 | O(n log n) | O(n log n) | O(n log n) | O(n) | O |
| 힙 | O(n log n) | O(n log n) | O(n log n) | O(1) | X |
선택 가이드
| 상황 | 추천 정렬 | 이유 |
|---|---|---|
| n < 10 | 삽입 정렬 | 오버헤드 적음 |
| 거의 정렬됨 | 삽입 정렬 | O(n)에 가까움 |
| 안정 정렬 필요 | 버블/삽입/병합 | 순서 유지 |
| 메모리 제약 | 선택/힙 | In-place |
| 일반 케이스 | 퀵/병합 | O(n log n) |
| 실무 | sort()/sorted() | 최적화됨 |
표의 “n < 10”은 절대적인 기준이 아니라 “아주 작은 배열”이라는 뜻입니다. 실제 라이브러리들이 삽입 정렬로 전환하는 경계값은 구현마다 다릅니다. GCC의 std::sort(introsort)는 구간이 16개 원소 이하로 작아지면 재귀를 멈추고 마지막에 삽입 정렬로 마무리하고, Python의 Timsort는 32~64개 사이에서 정하는 minrun 길이까지 이진 삽입 정렬로 run을 만듭니다. 이 정도 크기에서는 재귀 호출과 분할 비용이 O(n²)의 비교 비용보다 크고, 삽입 정렬의 연속 메모리 접근이 캐시에 유리하기 때문입니다. “메모리 제약”의 선택 정렬 추천도 쓰기 비용 때문이지 공간 복잡도 때문은 아닙니다. 버블·삽입 정렬도 똑같이 O(1) 추가 공간만 씁니다.
실무 사례
사례 1: 거의 정렬된 배열 - 삽입 정렬
대부분 정렬된 상태로 들어오는 데이터에서 삽입 정렬과 내장 정렬을 비교해 봅니다.
Python 구현
import time
def benchmark_sorting(arr):
"""
거의 정렬된 배열에서 삽입 정렬 vs 퀵 정렬
"""
arr_insertion = arr.copy()
arr_quick = arr.copy()
# 삽입 정렬
start = time.perf_counter()
insertion_sort(arr_insertion)
insertion_time = time.perf_counter() - start
# 퀵 정렬
start = time.perf_counter()
arr_quick.sort()
quick_time = time.perf_counter() - start
return insertion_time, quick_time
# 거의 정렬된 배열
arr = list(range(1000))
arr[100], arr[101] = arr[101], arr[100] # 2개만 교환
insertion_time, quick_time = benchmark_sorting(arr)
print(f"삽입 정렬: {insertion_time*1000:.2f}ms")
print(f"내장 정렬: {quick_time*1000:.2f}ms")
# 참고: list.sort()는 퀵 정렬이 아니라 Timsort이며,
# 결과 수치는 환경마다 다르므로 직접 실행해 비교할 것결론: 이 벤치마크는 “알고리즘”과 “구현 언어”의 차이가 섞여 있다는 점을 보여 줍니다. 삽입 정렬은 이 입력에서 역전이 하나뿐이라 약 n번의 비교로 끝나지만, 한 줄 한 줄이 Python 인터프리터에서 실행됩니다. list.sort()는 C로 구현된 Timsort라서, 이미 정렬된 긴 구간(run)을 감지하고 거의 그대로 통과시키므로 같은 입력에서 역시 선형에 가깝게 끝나며 상수 비용은 훨씬 작습니다. 그래서 Python에서는 거의 정렬된 데이터에도 내장 정렬이 대개 더 빠르고, 삽입 정렬이 실제로 유리한 것은 C/C++처럼 컴파일되는 언어에서 작은 구간을 처리할 때입니다. 한 가지 알아 둘 점은 benchmark_sorting 안의 insertion_sort가 1절에서 정의한 함수를 그대로 쓰며, 한 번씩만 측정하므로 결과가 실행마다 흔들린다는 것입니다. 비교가 목적이라면 timeit으로 여러 번 반복하세요.
사례 2: 작은 배열 - 삽입 정렬
Timsort와 introsort는 작은 구간을 삽입 정렬로 처리합니다. 그 아이디어만 단순하게 흉내 내 보면 다음과 같습니다.
Python 구현 (Timsort 스타일)
def timsort_style(arr, threshold=10):
"""
작은 구간은 삽입 정렬
큰 구간은 병합 정렬
"""
if len(arr) < threshold:
return insertion_sort(arr)
mid = len(arr) // 2
left = timsort_style(arr[:mid], threshold)
right = timsort_style(arr[mid:], threshold)
return merge(left, right)
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
result.extend(left[i:])
result.extend(right[j:])
return result
# 테스트
arr = [5, 2, 8, 1, 9, 3, 7, 4, 6]
print(timsort_style(arr))이 함수는 “작은 구간은 삽입 정렬, 큰 구간은 병합”이라는 아이디어만 보여 주는 단순화 버전이고, 진짜 Timsort와는 구조가 꽤 다릅니다. 실제 Timsort는 배열을 반으로 자르지 않고, 앞에서부터 훑으며 이미 오름차순이거나 엄격한 내림차순인 구간(run)을 찾습니다. 내림차순 run은 뒤집어서 쓰고, 너무 짧은 run은 이진 삽입 정렬로 minrun 길이까지 늘린 뒤, 스택에 쌓인 run들을 크기 규칙에 따라 병합합니다. 병합할 때는 한쪽에서 원소가 연속으로 이기면 지수 탐색으로 한꺼번에 건너뛰는 “galloping” 모드도 씁니다. 그래서 이미 정렬된 입력이나 역순 입력 모두 O(n)에 처리되며, 이 때문에 실제 데이터에서 강한 성능을 냅니다. 위 예제는 arr[:mid] 슬라이스가 매번 새 리스트를 만들므로 메모리도 더 많이 씁니다.
사례 3: 안정 정렬 - 다중 키 정렬
점수로 정렬하되 같은 점수끼리는 원래 순서를 유지해야 하는 경우입니다.
Python 구현
from dataclasses import dataclass
@dataclass
class Student:
name: str
score: int
students = [
Student("Alice", 90),
Student("Bob", 85),
Student("Charlie", 90),
Student("David", 85),
]
# 안정 정렬 (삽입 정렬)
def insertion_sort_students(students):
for i in range(1, len(students)):
key = students[i]
j = i - 1
while j >= 0 and students[j].score < key.score:
students[j + 1] = students[j]
j -= 1
students[j + 1] = key
return students
sorted_students = insertion_sort_students(students.copy())
for s in sorted_students:
print(f"{s.name}: {s.score}")
# 출력 (같은 점수는 원래 순서 유지):
# Alice: 90
# Charlie: 90
# Bob: 85
# David: 85안정 정렬이 실무에서 중요한 이유는 여러 기준으로 정렬할 때 드러납니다. “점수 내림차순, 같은 점수면 이름순”이 필요하다면, 먼저 이름으로 정렬한 뒤 점수로 안정 정렬하면 됩니다. 두 번째 정렬이 같은 점수의 원소들 사이에서는 첫 번째 정렬 결과(이름순)를 그대로 보존하기 때문입니다. Python의 sort()는 안정 정렬이 보장되므로 students.sort(key=lambda s: s.name) 다음 students.sort(key=lambda s: s.score, reverse=True)처럼 쓸 수 있고, 한 번에 하려면 key=lambda s: (-s.score, s.name)처럼 튜플 키를 씁니다. C++에서는 std::sort가 안정성을 보장하지 않으므로, 이런 경우 반드시 std::stable_sort를 써야 합니다. 테이블 UI에서 “열 머리글을 차례로 눌러 다중 정렬”하는 기능도 이 성질에 기대므로, 불안정 정렬을 쓰면 같은 값의 행이 클릭할 때마다 뒤섞여 사용자에게는 버그로 보입니다.
트러블슈팅
문제 1: 버블 정렬 최적화 누락
증상: 이미 정렬된 배열도 O(n²) 시간 소요
def bubble_sort_slow(arr):
n = len(arr)
for i in range(n):
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
return arr
# 이미 정렬된 배열도 n² 비교해결: swapped 플래그 추가
def bubble_sort_optimized(arr):
n = len(arr)
for i in range(n):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]
swapped = True
if not swapped:
break
return arr문제 2: 선택 정렬 안정성
증상: 같은 값의 순서가 바뀜
arr = [(3, 'a'), (1, 'b'), (3, 'c'), (2, 'd')]
# 선택 정렬 후: [(1, 'b'), (2, 'd'), (3, 'c'), (3, 'a')]
# (3, 'a')와 (3, 'c')의 순서가 바뀜해결: 안정 정렬 사용 (삽입/병합)
arr.sort(key=lambda x: x[0])
# [(1, 'b'), (2, 'd'), (3, 'a'), (3, 'c')] # 순서 유지문제 3: 삽입 정렬 역순 최악
증상: 역순 배열에서 O(n²) 비교 + 이동
arr = list(range(1000, 0, -1))
# 삽입 정렬: 매우 느림해결: 역순이 예상되면 O(n log n) 정렬을 쓰거나, 단순히 뒤집기
arr.sort() # Timsort: 엄격한 내림차순 run을 감지해 뒤집으므로 역순 입력은 O(n)
# 또는 역순인 것을 알고 있다면
arr.reverse()역순 입력은 삽입 정렬에게는 최악이지만, 이 경우를 미리 알고 있다면 정렬이 필요 없을 수도 있습니다. 로그를 최신순으로 받아 오는 API처럼 입력 순서가 예측 가능하다면 reverse()는 O(n)입니다. 반대로 퀵 정렬도 구현에 따라 최악의 경우가 있습니다. 첫 번째나 마지막 원소를 피벗으로 고르는 교과서식 퀵 정렬은 이미 정렬되었거나 역순인 입력에서 O(n²)으로 떨어지므로, 실제 라이브러리는 중앙값 피벗이나 무작위 피벗, 그리고 재귀가 깊어지면 힙 정렬로 전환하는 introsort로 이를 막습니다.
문제 4: 오프바이원 (Off-by-One)
증상: 인덱스 범위 실수
# 잘못된 예
for i in range(n):
for j in range(n - i): # 범위 초과
if arr[j] > arr[j + 1]: # j = n-1-i일 때 arr[j + 1]에서 IndexError
arr[j], arr[j + 1] = arr[j + 1], arr[j]해결:
for i in range(n):
for j in range(n - 1 - i): # 올바른 범위
if arr[j] > arr[j + 1]:
arr[j], arr[j + 1] = arr[j + 1], arr[j]오프바이원을 피하는 가장 확실한 방법은 루프 불변식을 말로 적어 보는 것입니다. 버블 정렬에서 i번째 회전이 끝나면 “마지막 i+1개 원소는 최종 위치에 있다”가 불변식이고, 안쪽 루프는 arr[j + 1]을 읽으므로 j의 최댓값은 n - 2 - i여야 합니다. range의 끝값은 포함되지 않으므로 range(n - 1 - i)가 정확히 이 범위입니다. C++로 옮길 때는 n을 int로 받은 이유도 중요합니다. arr.size()를 그대로 size_t로 쓰면 빈 벡터에서 arr.size() - 1이 음수가 아니라 아주 큰 양수가 되어 루프가 폭주합니다. 테스트할 때는 빈 배열, 원소 하나, 모두 같은 값, 이미 정렬됨, 역순을 기본 입력으로 넣어 보면 경계 실수 대부분이 드러납니다.
내장 정렬 사용법
실무에서는 직접 구현한 정렬 대신 언어 내장 정렬을 씁니다.
# sorted(): 새 리스트 반환
arr = [5, 2, 4, 1, 3]
sorted_arr = sorted(arr)
print(arr) # [5, 2, 4, 1, 3] (원본 유지)
print(sorted_arr) # [1, 2, 3, 4, 5]
# sort(): in-place 정렬
arr = [5, 2, 4, 1, 3]
arr.sort()
print(arr) # [1, 2, 3, 4, 5] (원본 변경)
# 역순
arr.sort(reverse=True)
print(arr) # [5, 4, 3, 2, 1]
# 커스텀 키
students = [('Alice', 85), ('Bob', 90), ('Charlie', 80)]
students.sort(key=lambda x: x[1], reverse=True)
print(students)
# [('Bob', 90), ('Alice', 85), ('Charlie', 80)]추천 문제
백준:
-
2751번: 수 정렬하기 2 프로그래머스:
다음 단계
- 고급 정렬: 퀵/병합/힙 정렬
- 정렬 문제: 정렬 문제 풀이
- 이진 탐색: 이진 탐색: 경계 조건, lower/upper bound, 결정 문제로 바꾸는 파라메트릭 서치
같이 보면 좋은 글
- 고급 정렬: 퀵·병합·힙 정렬이 O(n log n)인 이유와 선택 기준
- C++ 정렬 알고리즘 구현과 비교
- C++ 알고리즘 최적화 | 시간복잡도·공간복잡도·트레이드오프 [#54-10]