슬라이딩 윈도우: 고정 길이 합과 양수 배열의 가변 구간

슬라이딩 윈도우는 연속 구간의 합을 어떻게 갱신하나요?

슬라이딩 윈도우는 연속된 구간의 상태를 유지하며 양끝을 옮기는 방법입니다. 들어오는 값은 더하고 빠지는 값은 빼면 구간 전체를 다시 계산할 필요가 없습니다.

[2,1,5]의 합은 8입니다. 창을 한 칸 옮긴 [1,5,1]의 합은 8 - 2 + 1 = 7입니다.

적용 조건·범위: 두 합 예제는 입력값과 목표값뿐 아니라 모든 중간 덧셈·뺄셈 결과도 JavaScript Number의 안전한 정수 범위 안이라고 가정합니다. 각 원소가 안전한 정수여도 합이나 차가 범위를 넘으면 정확한 비교를 보장할 수 없습니다.

본문 근거: Competitive Programmer’s Handbook — Antti Laaksonen · ECMAScript 2025 — Number.MAX_SAFE_INTEGER

이 글에서 할 일: 고정 길이 창을 갱신하고 가변 창에 양수 조건이 필요한 이유를 확인합니다. 선수 지식: 배열·반복문·누적 합.

고정 길이 K의 합을 갱신하기

두 합 예제는 입력값과 목표값뿐 아니라 모든 중간 덧셈·뺄셈 결과도 JavaScript Number의 안전한 정수 범위 안이라고 가정합니다. 각 원소가 안전한 정수여도 합이나 차가 범위를 넘으면 정확한 비교를 보장할 수 없습니다.

아래 JavaScript 예제는 길이가 같은 연속 구간의 합을 구하고 가장 큰 값을 찾습니다. 코드 아래의 결과와 표를 보면서 창이 이동할 때 어떤 값을 빼고 더하는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function maxWindowSum(values, k) {
  // 계약: 입력값과 모든 중간 덧셈·뺄셈 결과는 Number의 안전한 정수
  if (!Number.isInteger(k) || k < 1 || k > values.length) {
    return null;
  }
  let sum = 0;
  for (let i = 0; i < k; i++) sum += values[i];
  let best = sum;
  for (let right = k; right < values.length; right++) {
    sum += values[right] - values[right - k];
    best = Math.max(best, sum);
  }
  return best;
}

console.log(maxWindowSum([2, 1, 5, 1, 3], 3));
console.log(maxWindowSum([-4, -2, -7], 2));

실행 결과

9
-6

불변식은 sum이 현재 길이 K 구간의 합이라는 것입니다. 최댓값을 0에서 시작하면 전부 음수인 입력에서 틀리므로 첫 구간의 합으로 시작합니다. K가 1보다 작거나 배열보다 크면 이 함수는 null을 반환합니다.

node --version

node fixed-window.js

양수 배열에서는 합이 크면 왼쪽을 줄입니다

아래 JavaScript 예제는 양수 배열에서 합이 목표값과 같은 연속 구간의 개수를 셉니다. 코드 아래의 결과와 설명을 보면서 합에 따라 구간의 양끝이 어떻게 움직이는지 살펴보세요. 직접 실행하지 않아도 설명을 따라갈 수 있습니다.

function countPositiveWindows(values, target) {
  // 계약: 모든 원소와 target은 양의 안전한 정수
  // 모든 중간 덧셈·뺄셈 결과도 Number의 안전한 정수 범위
  let left = 0;
  let sum = 0;
  let count = 0;
  for (let right = 0; right < values.length; right++) {
    sum += values[right];
    while (sum > target) sum -= values[left++];
    if (sum === target) count++;
  }
  return count;
}

console.log(countPositiveWindows([1, 2, 1, 1, 3], 3));

실행 결과

3

양수 배열에서 오른쪽 값을 추가하면 합은 커지고, 왼쪽 값을 빼면 작아집니다. 따라서 목표보다 커진 구간은 왼쪽을 줄여도 됩니다. 합이 목표가 되는 시작 위치는 같은 오른쪽 끝에 대해 최대 하나이므로 한 번만 셉니다. 예제의 세 구간은 인덱스 [0..1], [1..2], [4..4]입니다.

여기서 구간은 연속 부분수열입니다. 떨어진 원소를 골라 합을 만드는 부분집합 문제에 이 코드를 적용할 수는 없습니다.

node --version

node positive-window.js

0·음수·빈도표에서 달라지는 점

0을 허용하면 같은 오른쪽 끝에 정답 시작 위치가 여러 개 생길 수 있습니다. [0,0,3]에서 목표가 3인 구간은 세 개지만 위 함수는 하나만 셉니다. 음수가 있으면 합의 증가·감소 방향도 보장되지 않습니다. [4,-1]의 목표 3은 앞의 4를 미리 버리면 놓칩니다.

고정 길이 합 갱신은 음수가 있어도 성립합니다. 제약이 필요한 것은 여기서 제시한 양수 가변 창의 개수 세기 규칙입니다. 음수를 허용하는 합 문제는 누적 합과 빈도표 등 다른 방법을 검토합니다.

아나그램은 고정 길이 창의 상태를 합 대신 문자별 개수로 둡니다. 새 문자는 +1, 빠지는 문자는 -1로 갱신합니다. 0개인 키를 지울지 유지할지 통일하고, 비교에 사용하는 문자 범위도 같게 정하세요.

두 합 예제는 O(N) 시간과 O(1) 추가 공간입니다. 가변 창의 while이 중첩되어도 left는 전체 실행 동안 N번 이하 움직입니다. 빈도표를 매 창마다 D종 전체 비교하면 O(ND)이며, 문자 종류가 고정되어 있거나 불일치 개수를 따로 유지할 때 O(N)으로 줄일 수 있습니다.

직접 확인하고 문제에 적용하기

[-4,-2,-7]에서 K=2의 최댓값을 0으로 초기화하면 왜 틀릴까요? [0,0,3]의 정답 구간도 직접 적어 보세요.

• 최대 매출 구간 합 풀이
• 합이 M인 연속 부분수열 개수 풀이
• 모든 아나그램 찾기 풀이

참고 자료

자료 확인일: 2026년 10월 19일.

• Competitive Programmer’s Handbook — Antti Laaksonen — 8.1절의 양수 부분수열과 포인터 이동 수.
• ECMAScript 2025 — Number.MAX_SAFE_INTEGER — 안전한 정수 범위와 큰 정수의 정밀도 한계.