구간 탐색 선택 기준

구간 탐색 패턴 선택 기준

투포인터, 슬라이딩 윈도우, 파라메트릭 서치는 모두 경계를 움직이지만 버리는 근거가 서로 다릅니다.

양끝 이동

정렬된 배열에서 후보 제거

합이 작으면 왼쪽을 올리고 크면 오른쪽을 내려 한 번에 한 구간을 버립니다.

연속 창

누적 조건을 유지하며 축소

오른쪽으로 확장하고 조건을 만족하면 왼쪽을 줄여 최소 또는 최대 길이를 찾습니다.

답 공간

가능 여부를 이분 탐색

값 자체가 아니라 속도, 용량, 날짜처럼 답 후보의 단조성을 탐색합니다.

구간 탐색 전제 최종 기록

투포인터 정렬과 단조 이동이 가능한지 먼저 확인합니다.
윈도우 구간 합이나 빈도처럼 들어오고 나가는 값만 갱신 가능한지 봅니다.
파라메트릭 후보 x가 가능하면 그보다 큰 값도 가능한지 같은 방향성을 검증합니다.