시작하기전에

알고리즘 문제를 풀다 보면 슬라이딩 윈도우(Sliding Window) 라는 표현을 정말 자주 접하게 된다.
특히 연속된 구간을 다루는 문제에서 압도적으로 자주 등장하는 핵심 테크닉이며, 실제 코딩 테스트에서도 빈출되는 알고리즘이다.

이번 글에서는 슬라이딩 윈도우의 기본 개념부터, 어떤 상황에서 활용되는지, 그리고 대표적인 문제 패턴까지 코드 예시와 함께 정리해보려고 한다.

슬라이딩 윈도우란?

1. 개념

슬라이딩 윈도우(Sliding Window)는 말 그대로 창문(window)을 좌우로 밀면서(slide) 탐색하는 기법이다.

보통 아래 두 가지 경우에 사용된다

• 부분 배열의 길이가 고정된 경우 (Fixed Window)

• 조건을 만족하는 가장 긴(혹은 가장 짧은) 구간을 찾아야 하는 경우 (Dynamic Window)

핵심 아이디어는 간단하다:

전체 배열을 매번 새로 계산하지 않고,
윈도우의 양 끝을 조절하며 “증가된 부분만 더하고, 빠진 부분만 빼서” 효율적으로 계산한다.

이 방식으로 많은 문제를 O(N) 으로 해결할 수 있다.

2. 왜 슬라이딩 윈도우를 쓰는가?

• 나이브 방식
  각 구간을 매번 일일이 계산 → O(N²)

• 슬라이딩 윈도우
  앞/뒤 포인터만 이동 → O(N) 중복된 계산을 줄임
  즉, 구간 문제의 시간 복잡도를 한 단계 확 줄여주는 기술이다.

예제로 살펴보기

1. 고정 길이 윈도우 (Fixed Window)

문제) “길이가 k인 subarray 중 가장 큰 합을 구하라.”

윈도우 크기가 고정되어 있으므로
오른쪽 값 추가,왼쪽 값 제거 만 반복하면 된다.

function maxSum(nums, k) {
  // 1. 먼저 길이가 k인 초기 윈도우의 합을 만든다.
  let sum = 0;
  for (let i = 0; i < k; i++) sum += nums[i];

  // 초기 윈도우의 합이 현재까지의 최대값
  let answer = sum;

  // 2. 윈도우를 오른쪽으로 한 칸씩 밀면서(update) 합을 갱신한다.
  for (let i = k; i < nums.length; i++) {
    sum += nums[i];        // 새로 들어온 값 추가
    sum -= nums[i - k];    // 왼쪽에서 빠져나가는 값 제거

    // 각 단계에서 최대 합을 갱신
    answer = Math.max(answer, sum);
  }

  // 3. 길이 k인 모든 연속 구간 중 최댓값 반환
  return answer;
}

2. 가변 길이 윈도우 (Dynamic Window)

문제) “합이 target 이하가 되는 가장 긴 subarray 길이를 구하라.”

윈도우 길이가 조건에 따라 늘었다 줄었다 하며 탐색한다.

function longestSubarray(nums, target) {
  let left = 0;      // 윈도우의 시작 포인터
  let sum = 0;       // 현재 윈도우의 합
  let answer = 0;    // 조건을 만족하는 가장 긴 구간 길이

  // right 포인터를 오른쪽으로 확장하며 윈도우를 키운다.
  for (let right = 0; right < nums.length; right++) {
    sum += nums[right];  // 새로 포함된 값 더하기

    // 현재 합이 target을 초과하면 조건을 만족할 때까지 left를 이동(윈도우 축소)
    while (sum > target) {
      sum -= nums[left];  // 빠져나가는 값 제거
      left++;             // 윈도우 시작점 이동
    }

    // 여기 도달했을 때 sum <= target을 만족하는 상태
    // 현재 윈도우 크기(right - left + 1)를 기준으로 최대 길이 갱신
    answer = Math.max(answer, right - left + 1);
  }

  return answer;
}

3. 빈도 기반 슬라이딩 윈도우

문제) “문자열 s에서 모든 문자가 최소 k번 등장하는 가장 긴 구간”

문자열 문제에서 자주 등장한다. 이 경우에는 윈도우 내부의 frequency map , count
distinct number 등을 관리하며 이동한다.

function countValidSubstrings(s, k) {
  let left = 0;          // 윈도우 시작 포인터
  let count = 0;         // 조건을 만족하는 substring 개수
  let freq = new Map();  // 윈도우 내부에서 문자 등장 횟수를 저장하는 Map

  // right 포인터를 확장하며 윈도우를 키움
  for (let right = 0; right < s.length; right++) {
    // 새로 들어온 문자 빈도 증가
    freq.set(s[right], (freq.get(s[right]) || 0) + 1);

    // 윈도우 내에서 서로 다른 문자 수가 k를 초과하면 조건 만족할 때까지 축소
    while (freq.size > k) {
      freq.set(s[left], freq.get(s[left]) - 1);  // 빠지는 문자 count 감소

      // 0이 되면 Map에서 제거 → distinct 문자 수 감소
      if (freq.get(s[left]) === 0) freq.delete(s[left]);

      left++;  // 윈도우 축소
    }

    // 현재 right 기준으로 가능한 모든 유효한 substring 개수를 더함
    // (left ~ right 구간 전체가 조건을 만족하기 때문)
    count += right - left + 1;
  }

  return count;
}

슬라이딩 윈도우를 언제 떠올려야 하는가?

다음 문구가 보이면 슬라이딩 윈도우 문제일 확률이 높다
(특히 연속이면서 ‘효율적으로’ 계산해야 한다 → 바로 이 기법이 떠올라야 함)

• “연속된 구간”

• “부분 배열(subarray)”

• “길이가 l ~ r”

• “최대/최소 합”

• “조건을 만족하는 가장 긴 문자열”

• “0과 1의 개수 제한”

슬라이딩 윈도우의 본질은
“중복 계산을 피하고, 진짜로 변하는 부분만 업데이트한다”
라는 발상이다.

마무리

슬라이딩 윈도우는 실제 코딩 테스트에서도 나 역시 여러 번 마주쳤던 알고리즘이다. 솔직히 많이 틀리기도 했고, 그래서 LeetCode 문제들을 풀면서 개념을 다시 차근차근 정리해보게 되었다.

아직 알고리즘은 어렵고 답답하게 느껴질 때가 많지만, 꾸준히 풀다 보면 분명 나아질 거라 믿는다. 그 과정의 일부로 이렇게 정리하며 포스팅하는 습관도 계속 이어가 보려고 한다.