슬라이딩 윈도우 기법 — 전체 가이드 (DSA)

Source: Dev.to

슬라이딩 윈도우 기법이란?

슬라이딩 윈도우는 배열이나 문자열 내에서 연속된 부분 배열 또는 부분 문자열을 고정 크기 또는 가변 크기로 효율적으로 처리하기 위해 사용되는 알고리즘 기법입니다.
각 부분 배열에 대해 값을 처음부터 다시 계산하는 대신, 윈도우가 앞으로 이동하면서 이전에 수행한 계산을 재사용합니다.

• 윈도우 크기 (k) – 한 번에 검사하는 요소의 개수.
• 윈도우 – 현재 처리 중인 요소들의 집합.

고정 크기 윈도우 예시

배열: [1, 3, -1, -3, 5, 3, 6, 7] k = 3

[1, 3, -1]
   [3, -1, -3]
      [-1, -3, 5]
         [-3, 5, 3]
            [5, 3, 6]
               [3, 6, 7]

각 윈도우마다 전체 윈도우를 다시 스캔하지 않고도 속성(예: 최대값)을 계산할 수 있습니다.

결과 (각 윈도우의 최대값): [3, 3, 5, 5, 6, 7]

슬라이딩 윈도우 작동 방식

1. 첫 번째 윈도우 처리 (인덱스 0 … k‑1).
2. 이후 각 인덱스 i = k … n‑1에 대해
   • 윈도우를 떠나는 요소 제거 (i‑k).
   • 새로운 요소 추가 (i).
   • 변경된 요소만을 사용해 답 업데이트.

이렇게 하면 순수 O(n·k) 작업을 O(n)으로 줄일 수 있다.

예시: 크기 k인 최대 합 부분 배열

// Time: O(n)   Space: O(1)
function maxSumSubarray(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  // first window
  for (let i = 0; i = k - 1) {
      result.push(nums[deque[0]]);
    }
  }

  return result;
}

가변 크기 윈도우 (두 포인터) 기법

윈도우 크기를 미리 알 수 없을 때는, 조건이 깨질 때까지 오른쪽 포인터를 확장하고, 이후 왼쪽에서부터 축소합니다.

// Example: Length of the longest substring without repeating characters
function longestUnique(s) {
  const set = new Set();
  let left = 0;
  let maxLen = 0;

  for (let right = 0; right < s.length; right++) {
    while (set.has(s[right])) {
      set.delete(s[left]);
      left++;
    }
    set.add(s[right]);
    maxLen = Math.max(maxLen, right - left + 1);
  }
  return maxLen;
}

일반적인 패턴

left = 0
for right in range(0, n):
    expand window (include element at right)

    while window does not satisfy condition:
        shrink window (exclude element at left)
        left += 1

    update answer based on current window

일반적인 응용

전형적인 실제 시나리오:

• 지난 5 분 동안의 최고 대역폭 사용량.
• 지난 30 일 동안의 최고 가격.
• 최근 10 번 측정값의 평균 온도.
• 최근 N 개의 요청에서 이상 징후 감지.

슬라이딩 윈도우가 O(n)을 보이는 이유

이 기법은 본질적으로 특수화된 두 포인터 방법이다:

• 오른쪽 포인터는 항상 앞으로 이동하며 윈도우를 확장한다.
• 왼쪽 포인터는 현재 윈도우가 조건을 위반할 때만 앞으로 이동한다.

각 요소가 윈도우에 추가되고 제거되는 횟수가 최대 한 번이므로, 전체 작업량은 입력 크기에 대해 선형이다.

Common Pitfalls

• 윈도우가 슬라이드될 때 가장 왼쪽 요소를 제거하는 것을 잊는 경우.
• 매번 전체 윈도우를 다시 계산하는 순진한 중첩 루프를 사용하는 경우 (O(n·k)).
• 고정‑크기 솔루션(deque)이 가변‑크기 문제에 적용된다고 가정하는 경우; 이러한 문제는 two‑pointer shrink‑expand 접근법이 필요합니다.

Summary

슬라이딩 윈도우 기법은 많은 부분 배열/부분 수열 문제를 이차 시간에서 선형 시간으로 변환합니다. 이는 이전 계산을 재사용하고 윈도우가 데이터 전체를 이동하면서 필요한 상태만 유지함으로써 가능합니다. 윈도우 크기가 고정된 경우(덱 사용)든 가변인 경우(두 포인터 사용)든 핵심 아이디어는 동일합니다: 각 요소를 최대 두 번만 처리합니다—윈도우에 들어올 때 한 번, 나갈 때 한 번.