투포인터
pair 후보
1
3
5
8
10
12
확인 버린 왼쪽 값은 어떤 오른쪽과도 답이 될 수 없는가?
반례 정렬이 깨지면 이 제거가 성립하지 않는다.
final compare
마지막 비교는 “남은 후보”가 설명해야 한다
경계를 움직인 뒤에도 답 후보가 어디에 남아 있는지 말할 수 있어야 종료 조건과 반환값이 안전하다.
남은 후보
현재 경계
mid
버린 후보
후보가 사라지는 위치를 먼저 확인한다
슬라이딩 윈도우
range 후보
2
1
3
2
4
1
확인 왼쪽을 빼도 놓치는 연속 구간이 없는가?
반례 음수가 있으면 합의 증감 방향이 흔들린다.
파라메트릭
answer 후보
1
2
3
4
5
6
확인
ok(mid) 뒤에도 답이 남은 구간에 포함되는가?반례 단조가 아니면 절반 제거가 안전하지 않다.
| 마지막 질문 | 통과 기준 | 실패 신호 |
|---|---|---|
| 무엇을 버렸나 | 버린 후보가 답이 아님을 전제에서 설명할 수 있음 | “그냥 포인터를 옮긴다”만 남음 |
| 무엇을 반환하나 | 종료 후 남은 경계가 답 후보를 가리킴 | lo, hi, mid 중 무엇을 반환할지 흔들림 |
| 반례가 있나 | 비정렬, 음수, 비단조 입력에서 사용 금지를 설명할 수 있음 | 경계가 움직이지만 후보 보존이 깨짐 |
핵심: 경계 이동 알고리즘의 정답성은 “어디로 움직였는가”보다 “그 이동으로 버린 후보가 왜 답이 아닌가”에 달려 있다.