투포인터
sorted
L 1
3
5
8
10
R 12
버림 합이 크면 오른쪽 큰 값이 포함된 조합 묶음
전제 배열이 정렬되어 있어야 한다.
pointer entry
세 기법은 움직이는 축이 다르다
포인터 변수의 개수보다, 어떤 후보 집합을 안전하게 버릴 수 있는지가 기법을 나눈다.
정렬 양끝
연속 구간
답 후보
같은 입력처럼 보여도 버리는 후보가 다르다
슬라이딩 윈도우
positive
2
1
3
2
4
1
버림 조건을 넘긴 현재 창의 왼쪽 prefix
전제 양수라서 확장/축소의 방향이 유지된다.
파라메트릭 서치
monotone
1
2
3
4
5
6
버림
ok(mid)로 증명된 불가능/충분 범위전제 답 후보 판정이 한 방향으로만 바뀐다.
| 기법 | 움직이는 축 | 먼저 말해야 할 문장 |
|---|---|---|
| 투포인터 | 정렬 배열의 양끝 인덱스 | 이 값을 버려도 답 조합을 잃지 않는 이유 |
| 윈도우 | 연속 구간의 왼쪽과 오른쪽 | 창을 늘리거나 줄이면 상태가 어떻게 변하는지 |
| 파라메트릭 | 데이터 인덱스가 아니라 답 후보 값 | 가능/불가능 경계가 단조인지 |