Lesson 204. 정렬과 탐색
정렬, 이분 탐색, 투 포인터, 스윕 라인, 그리디 스케줄링
- key=lambda 다중 정렬 이관
- 투 포인터를 활용한 매칭 최적화
- bisect를 이용한 이분 탐색 및 BST 우회
- 탐욕법과 오프라인 쿼리 응용
수업 목표 및 핵심 역량
- 다중 조건 람다 정렬과 안정 정렬의 원리를 이해합니다.
- 투 포인터 기법을 리스트 병합과 그리디 매칭에 응용합니다.
- multiset의 부재를 Disjoint Set 경로 압축으로 극복합니다.
- 타워 스케줄링 및 오프라인 신호등 제거 병합을 구현합니다.
- 8013번 ~ 8022번 실습 문제를 해결합니다.
C++ 정렬의 파이썬 이관
# C++: sort(pts.begin(), pts.end(), cmp);
# 파이썬 다중 조건 정렬:
pts.sort(key=lambda p: (p[0], -p[1]))
투 포인터 & 이분 탐색
# bisect_right(a, x) 는 C++ upper_bound와 1:1 매칭
from bisect import bisect_left, bisect_right
idx = bisect_right(a, x) - 1
그리디 & 오프라인 쿼리
- 타워 스케줄링: 크기가 큰 타워 중 최솟값에 할당
- 오프라인 쿼리: 역순 신호등 제거를 구간 결합으로 전환
# 8021번: 타워 bisect_right 최적 타워 갱신
idx = bisect.bisect_right(towers, val)
if idx < len(towers):
towers[idx] = val
else:
towers.append(val)
오류 예방 및 작성 요령
- **IndexError 예방**: bisect_right 인덱스 유효 범위($0 \le idx < len$) 반드시 사전 검사
- **pop(index) 금지**: 정렬 리스트 중간 삭제 $O(N)$ 병목 방지
- **// 연산자**: mid 계산 시 반드시 정수 나눗셈 사용
- **오프라인 쿼리**: 쿼리를 모았다가 거꾸로 돌리며 합병하여 TLE 극복