정렬 없는 투포인터
1
8
3
6
1 + 6 < 9라서 left를 밀면, 실제 답 3 + 6을 지나친다.
precondition audit
전제가 깨지면 포인터는 후보를 잘못 버린다
투포인터, 윈도우, 파라메트릭 서치는 포인터 모양이 아니라 “버린 후보가 다시 답이 될 수 없는가”로 검증한다.
보존
의심
오답 후보
음수 있는 윈도우
4
-5
7
2
오른쪽을 늘려도 합이 항상 증가하지 않아 “sum이 크면 left++” 근거가 약해진다.
비단조 판정 함수
F
T
F
T
false/true가 다시 섞이면 mid 한 번으로 답 공간 절반을 버릴 수 없다.
| 기법 | 버려도 되는 근거 | 제출 전 반례 |
|---|---|---|
| 투포인터 | 정렬 때문에 합이 작으면 왼쪽 이하 후보가 모두 탈락한다. | 정렬되지 않은 배열, 중복 경계 |
| 슬라이딩 윈도우 | 양수 배열이라 확장하면 합이 늘고 축소하면 줄어든다. | 음수 포함, 길이 0 윈도우 |
| 파라메트릭 | ok(x)가 false 구간 뒤 true 구간으로 한 번만 바뀐다. | T/F가 섞이는 판정 함수 |