정렬을 언제 쓰나: 전처리·이분·그리디

정렬의 비용

비교 정렬은 보통 O(n log n)입니다.
n이 10^5면 허용되는 경우가 많고, n이 10^7이면 상수·언어에 따라 아슬아슬합니다.

정렬이 열어 주는 패턴

1. 투포인터: 정렬된 배열에서 합/차에 맞춰 양끝 이동
2. 이분 탐색: 정렬된 키에서 lower_bound
3. 그리디: “가장 작은/큰 것부터” 고르기 전에 정렬
4. 구간 병합: 시작점 기준 정렬 후 한 번 스캔

언제 정렬하면 안 되나

• 원래 인덱스가 필요하면 (value, index) 쌍으로 정렬하거나, 정렬 전 복사본을 두세요.
• 안정 정렬이 필요한지 확인하세요 (같은 키의 상대 순서).
• 이미 O(n) 해시로 되는 문제를 O(n log n)으로 굳이 바꾸지 마세요.

언어별

• JS: arr.sort((a,b)=>a-b) (비교 함수 없으면 문자열 정렬!)
• Python: sorted(xs), xs.sort()
• 부분 정렬·상위 k만 필요하면 힙을 고려

손추적

[3,1,4,1,5]를 정렬하면 [1,1,3,4,5].
“두 수의 합이 6”이면 투포인터로 (1,5), (1,5), (3,?)…를 추적해 보세요.

연습

관련 태그 정렬 / two-pointer 문제 하나를, 정렬 전/후 상태를 표로 적어 가며 푸세요.

체크리스트

1. 원래 순서가 필요한가?
2. 정렬 키가 한 개인가, 여러 개인가?
3. 정렬 후 한 번 스캔으로 끝나는가?
4. n log n이 제약에 들어가는가?

한 줄

> 정렬은 답이 아니라 다음 패턴을 싸게 만드는 전처리다.

예: 두 수의 합 (정렬+투포인터)

입력 배열을 복사해 정렬한 뒤 L/R을 움직입니다.
원본 인덱스가 필요하면 값과 인덱스를 같이 정렬하세요.

JS에서 숫자 정렬을 잊으면 [10,2]가 [10,2]가 아니라 문자열 순이 됩니다.

관련

이어서 투포인터·이분 탐색 레슨을 보면 정렬의 쓰임이 연결됩니다.