투포인터
1
2
3
4
6
8
11
sum이 작으면 left++, 크면 right--. 정렬 덕분에 후보를 안전하게 버린다.
pattern map
세 기법은 “무엇을 버려도 되는가”로 갈린다
후보를 버리는 근거가 정렬 관계인지, 구간 상태인지, 판정 함수의 단조성인지 구분하면 구현 규칙도 같이 정해진다.
pair search
range state
answer space
대표 입력과 이동 규칙
슬라이딩 윈도우
2
3
1
2
4
3
1
합이 부족하면 right++, 충분하면 left++. 양수라 구간 합 변화가 예측된다.
파라메트릭 서치
1
2
3
4
5
6
7
불가능/가능 경계가 한 번만 바뀌면 answer space를 이분한다.
| 기법 | 버리는 후보 | 검증해야 할 전제 | 대표 오답 |
|---|---|---|---|
| 투포인터 | 현재 합으로 불가능해진 한쪽 끝 후보 | 정렬, 단조 비교 | 정렬 없이 left/right 이동 |
| 윈도우 | 조건을 만족한 뒤 더 긴 구간 | 양수, 증분 갱신 가능 | 음수 포함인데 합 단조로 가정 |
| 파라메트릭 | ok(mid) 결과로 사라지는 답 후보 절반 | 판정 단조성 | 가능/불가능이 뒤섞인 check |