경계 이동 알고리즘 비교

단조성 확인

파라메트릭 서치는 x가 가능하면 그보다 큰 값도 가능하다는 식의 방향이 있어야 한다.

슬라이딩 윈도우는 오른쪽을 늘린 뒤 조건이 깨지면 왼쪽을 줄여 다시 맞춘다.

[lo, hi)인지 [lo, hi]인지 정하지 않으면 무한 루프와 off-by-one이 생긴다.

Two pointers

정렬 또는 방향성 합, 거리, 구간 조건이 포인터 이동 방향을 결정한다.

근거 없는 이동은 후보를 버린다.

Sliding window

연속 구간 구간의 합, 빈도, unique 조건을 유지하며 이동한다.

음수 포함 여부가 중요하다.

Binary answer

가능성 판정 답 자체를 이분하고 check(x)가 단조인지 확인한다.

check 비용까지 곱해 본다.

Off-by-one

경계 실수 lo, mid, hi 갱신이 같은 후보를 반복하지 않아야 한다.

작은 범위로 시뮬레이션한다.

후보 보존 포인터를 움직일 때 버리는 후보가 절대 답이 아님을 설명할 수 있는가.

음수 윈도우 합 문제에서 음수가 있어도 조건 유지가 가능한가.

단조 판정 check(mid)의 참/거짓이 한 방향으로만 바뀌는가.

while (lo < hi) {
    int mid = lo + (hi - lo) / 2;
    if (can(mid)) hi = mid;
    else lo = mid + 1;
}