슬라이딩 윈도: 연속 구간의 중복 계산과 단조성 경계를 분리하기

길이 $k$ 인 모든 연속 구간 합을 매번 처음부터 더하면 인접한 두 구간의 $k-1$ 개 원소를 중복 계산한다. 슬라이딩 윈도는 나가는 값과 들어오는 값만 반영해 이 중복을 제거한다. 다만 가변 길이 창은 값의 부호 같은 추가 단조성이 필요하다.

1. 두 문제의 계약을 섞지 않는다

maxFixedWindowSum(values,width): 정확히 width개인 연속 구간 중 최대 합을 반환한다. width가 0 이하이거나 배열보다 크면 계약 위반이다.
minLengthAtLeast(positive,target): 모든 값이 양수일 때 합이 target 이상인 가장 짧은 연속 구간 길이를 반환한다. 없으면 0이다.

고정 창은 음수도 허용한다. 가변 창은 음수가 있으면 left를 줄였을 때 합이 오히려 커질 수 있어 현재 이동 규칙이 무너진다. 이름이 같은 패턴이라고 전제를 공유하지 않는다.

2. 고정 창 상태 전이

[2,-1,3,5,-2], width 3을 본다.

창 index	원소	이전 합에서 제거/추가	현재 합	best
`[0,3)`	`2,-1,3`	초기 3개 합	4	4
`[1,4)`	`-1,3,5`	`-2 +5`	7	7
`[2,5)`	`3,5,-2`	`-(-1) -2`	6	7

불변식: right를 처리한 뒤 current는 정확히 마지막 width개 값의 합이고 best는 지금까지 완성된 모든 width 창의 최대 합이다. 이전 창에서 빠지는 values[right-width]를 빼고 새 값을 더하면 겹치는 원소를 다시 더하지 않아도 정확하다.

3. 양수 가변 창의 이동 증명

[2,3,1,2,4,3], target 7에서 right를 늘리며 합을 키운다. 합이 7 이상이면 left를 오른쪽으로 옮겨 가능한 한 줄인다. 모든 값이 양수이므로 right를 고정했을 때 left를 옮길수록 합은 단조 감소한다.

불변식: 내부 while 종료 후 현재 window 합은 target보다 작고, 그 직전에 제거한 left를 포함한 창들은 해당 right에서 가능한 target 이상 후보로 평가됐다. 각 left/right가 되돌아가지 않으므로 모든 최소 후보를 놓치지 않는다.

음수 반례 [2,-1,2], target 3에서는 합이 target 미만이라고 right만 늘리는 규칙의 의미가 흔들리고, left 제거가 합을 키울 수도 있다. 일반 정수 배열의 shortest subarray는 prefix sum과 monotonic deque 같은 다른 알고리즘이 필요하다.

실행 재현

아래 코드는 설명용 조각이 아니라 main에 정상·빈 입력·중복·경계·실패 계약을 함께 넣은 완전한 Java 21 프로그램이다.

public final class SlidingWindowDemo {
    static long maxFixedWindowSum(int[] values, int width) {
        if (values == null) throw new IllegalArgumentException("values must not be null");
        if (width <= 0 || width > values.length) throw new IllegalArgumentException("invalid width");
        long current = 0;
        for (int i = 0; i < width; i++) current += values[i];
        long best = current;
        for (int right = width; right < values.length; right++) {
            current += values[right];
            current -= values[right - width];
            best = Math.max(best, current);
        }
        return best;
    }

    static int minLengthAtLeast(int[] positive, long target) {
        if (positive == null) throw new IllegalArgumentException("positive must not be null");
        if (target <= 0) throw new IllegalArgumentException("target must be positive");
        long sum = 0;
        int left = 0;
        int best = Integer.MAX_VALUE;
        for (int right = 0; right < positive.length; right++) {
            if (positive[right] <= 0) throw new IllegalArgumentException("all values must be positive");
            sum += positive[right];
            while (sum >= target) {
                best = Math.min(best, right - left + 1);
                sum -= positive[left++];
            }
        }
        return best == Integer.MAX_VALUE ? 0 : best;
    }

    static void check(boolean condition, String message) {
        if (!condition) throw new AssertionError(message);
    }

    public static void main(String[] args) {
        check(maxFixedWindowSum(new int[] {2, -1, 3, 5, -2}, 3) == 7, "fixed");
        check(minLengthAtLeast(new int[] {2, 3, 1, 2, 4, 3}, 7) == 2, "variable");
        check(minLengthAtLeast(new int[0], 7) == 0, "empty");
        System.out.println("fixed max=7, variable minLength=2, missing=0");
    }
}

javac --release 21 SlidingWindowDemo.java
java SlidingWindowDemo

직접 실행한 출력은 다음과 같다.

fixed max=7, variable minLength=2, missing=0

컴파일러와 런타임은 javac 21.0.11, OpenJDK 21.0.11을 사용했다. assert 옵션에 의존하지 않고 실패 시 AssertionError를 던지므로 위 명령 그대로 검증된다.

4. 누적합 overflow와 실패 입력

width가 크면 int 원소의 합이 int 범위를 쉽게 넘는다. long current에 int를 더해 64-bit로 계산한다. 그래도 데이터 규모가 long 범위를 넘을 수 있는 도메인이면 Math.addExact나 더 큰 수 타입, overflow 정책이 필요하다.

가변 method는 non-positive 원소를 조용히 처리하지 않고 예외로 거절한다. 잘못된 전제에서 그럴듯한 답을 반환하는 것보다 failure를 계약으로 드러내는 편이 안전하다.

5. 복잡도 유도

고정 창은 초기 width개를 더하고 나머지 $n-width$ 개를 한 번 처리하므로 $\Theta(n)$ 이다. 가변 창은 right가 $n$ 번, left가 최대 $n$ 번 움직여 합계 최대 $2n$ 회이므로 $O(n)$ 이다. 중첩 while이 보여도 pointer가 되돌아가지 않아 $O(n^2)$ 가 아니다.

배열 batch 구현의 보조 공간은 $O(1)$ 이다. 실제 stream에서 나가는 값을 빼려면 최근 width개를 ring buffer에 보관해야 하므로 $O(width)$ 메모리가 필요하다. 입력 배열을 이미 가진 경우와 streaming state를 구분한다.

6. JVM과 allocation

예제 loop는 primitive long/int만 갱신하고 새 객체를 만들지 않는다. 입력 int[]는 heap에 있고 local references/index는 frame 관점이다. stream API로 매 원소를 boxing하거나 window subList를 매번 만들면 논리상 $O(n)$ 이어도 allocation과 GC pressure가 커질 수 있다. JFR로 allocation source를 확인한다.

7. prefix sum·two pointers·deque와 비교

선택	질의/전제	시간	상태
고정 sliding sum	한 번 전체 scan	$O(n)$	$O(1)$ batch
prefix sum	여러 range-sum 질의	build $O(n)$ , query $O(1)$	$O(n)$
양수 가변 window	합 단조성	$O(n)$	$O(1)$
monotonic deque	window min/max 또는 일반 prefix 조건	$O(n)$	$O(n)$ 최악

반복 range query라면 prefix sum 구축이 낫고, 모든 window의 최댓값 원소를 구하려면 합 한 개가 아니라 monotonic deque가 필요하다.

8. 실제 도메인 적용

rate-limit의 최근 60초 요청, telemetry moving aggregate, stream anomaly window에 쓸 수 있다. 그러나 processing-time과 event-time을 구분하고 late/out-of-order event, watermark, state TTL을 설계해야 한다. 관측 지표는 active windows, state bytes, late-event ratio, eviction lag, overflow/rejection이다.

9. 이건 피한다

음수 배열에 양수 전용 가변 window를 쓴다. 합의 단조성이 깨져 정답을 놓친다. prefix sum+deque 등 계약에 맞는 알고리즘을 쓴다.
매 창을 copyOfRange로 만든다. $O(nk)$ 복사와 allocation을 만든다. 나가는 값/들어오는 값만 갱신한다.
합을 int에 둔다. 큰 window에서 overflow가 최대 비교를 왜곡한다. long 또는 명시적 overflow 정책을 쓴다.
batch 보조 공간 $O(1)$ 을 stream에도 그대로 쓴다. 나가는 값을 기억할 buffer가 필요하다. window state와 TTL을 산정한다.
width 오류를 0으로 반환한다. 실제 최대합 0과 계약 위반이 섞인다. 예외나 명시적 result로 구분한다.

Reference

Oracle, The Java Language Specification, Java SE 21 — Integer Operations
Oracle, Arrays — Java SE 21 API
Oracle, ArrayDeque — Java SE 21 API
Oracle, The Java Virtual Machine Specification, Java SE 21 — Heap and Frames