슬라이딩 윈도우

[3, 1, 4, 1, 5]에서 연속한 3개의 합이 가장 큰 구간을 손으로 찾아봅니다.

정직하게 계산하면 구간마다 3번씩 더해 총 9번이지만, 밀면서 계산하면 첫 창 3번 + 이후 한 칸당 2번뿐입니다. 원소가 10만 개이고 구간 길이가 1000이면 이 차이가 그대로 시간 초과와 통과를 가릅니다.

고정 크기 창의 골격은 "첫 창을 만들고 → 한 칸씩 밀고 → 기록한다"입니다.

1. 첫 창만 정직하게 채웁니다 — 인덱스 0부터 k-1까지 전부 더합니다.

let sum = 0;
for (let i = 0; i < k; i++) sum += arr[i];
let best = sum;

2. 한 칸 밀 때는 빼고 더하기만 합니다 — 나가는 값은 arr[i - k], 들어오는 값은 arr[i]입니다.

sum += arr[i] - arr[i - k]; // 미는 비용은 O(1)

3. 밀 때마다 답을 갱신합니다.

best = Math.max(best, sum);

전체 코드 — "연속 K개 합의 최댓값":

function maxWindowSum(arr: number[], k: number): number {
  // 1단계: 첫 창만 정직하게
  let sum = 0;
  for (let i = 0; i < k; i++) sum += arr[i];
  let best = sum;
  // 2~3단계: 한 칸씩 밀며 갱신하고 기록
  for (let i = k; i < arr.length; i++) {
    sum += arr[i] - arr[i - k];
    best = Math.max(best, sum);
  }
  return best;
}

• 지문에 "연속한 K개", "연속 부분 배열", "연속한 부분 문자열"이 보이면 이 유형입니다. 연속이 아니라 아무 원소나 골라도 되는 문제는 슬라이딩 윈도우가 아닙니다.
• "조건을 만족하는 가장 긴 / 가장 짧은 연속 구간의 길이" — 창 크기가 변하는 가변 윈도우 신호입니다.
• 대표 문제 상황: 연속 K일 매출의 최대 합, 서로 다른 문자가 K종 이하인 최장 부분 문자열, 합이 목표 이하인 최장 구간.
• 이중 루프로 모든 구간을 다시 더하다 시간 초과가 났다면 거의 이 기법으로 바꿔야 하는 경우입니다.

가변 크기 윈도우 (두 포인터 결합) — 조건을 만족하는 최장/최단 구간은 창 크기가 변합니다. 오른쪽을 늘리다 조건이 깨지면 왼쪽을 줄입니다.

// 합이 K 이하인 최장 연속 구간
function longestUnderK(arr: number[], K: number): number {
  let left = 0, sum = 0, best = 0;
  for (let right = 0; right < arr.length; right++) {
    sum += arr[right];                       // ① 오른쪽 확장
    while (sum > K) sum -= arr[left++];      // ② 조건 깨지면 왼쪽 축소
    best = Math.max(best, right - left + 1); // ③ 유효한 상태에서 기록
  }
  return best;
}

확장 → 축소 → 기록의 3박자를 몸에 익히세요. left와 right 모두 최대 N번 움직이므로 O(N)입니다.

창 안의 구성이 조건인 경우 — "서로 다른 문자 K종 이하 최장 부분 문자열"처럼 창 안에 무엇이 들어 있는지가 조건이면, 창과 함께 Map(문자 → 개수)을 유지합니다.

const count = new Map<string, number>();
count.set(ch, (count.get(ch) ?? 0) + 1);              // 들어올 때
const n = count.get(out)! - 1;                        // 나갈 때
n === 0 ? count.delete(out) : count.set(out, n);      // 0이면 삭제해야 size가 맞음

• 축소를 if로 한 번만 함 — 조건이 회복될 때까지 while로 반복해야 합니다.

if (sum > K) sum -= arr[left++];    // 잘못: 한 번 줄여도 여전히 초과일 수 있음
while (sum > K) sum -= arr[left++]; // 고침: 회복될 때까지

• 기록 시점 오류: 조건이 깨진 상태에서 best를 갱신 (③은 반드시 축소가 끝난 유효 상태에서).

sum += arr[right];
best = Math.max(best, right - left + 1); // 잘못: 아직 sum > K일 수 있음
while (sum > K) sum -= arr[left++];

• 음수가 섞인 배열에서 "합" 기반 가변 윈도우 사용 — 오른쪽을 늘려도 합이 커진다는 보장이 없어(단조가 아니라) 성립하지 않습니다. 그때는 누적합 + 해시로 전환합니다.
• 고정 창에서 첫 창을 만들기 전에 밀기 시작 — 인덱스 k-1까지는 채우기 단계이고, 미는 루프는 i = k부터입니다.
• Map으로 구성을 셀 때 개수가 0이 된 키를 지우지 않음 — map.size가 실제 종류 수보다 크게 나옵니다.

• 왜 O(N)인가: 가변 윈도우는 이중 루프처럼 보이지만, left는 감소하지 않고 전체 실행 동안 최대 N번만 증가합니다. 안쪽 while의 총 실행 횟수가 N을 넘지 않으므로 전체가 O(N)입니다. 이런 계산 방식을 분할 상환(amortized) 분석이라고 합니다.
• 단조성이 성립 조건: 가변 윈도우가 옳으려면 "창을 늘리면 지표가 나빠지고, 줄이면 좋아진다"는 방향성이 있어야 합니다. 모든 값이 양수인 합, 서로 다른 값의 개수는 이 성질을 만족합니다. 음수가 섞인 합은 만족하지 않습니다.
• 음수가 있을 때의 대안: 누적합 prefix[i]를 만들고 "합이 정확히 K인 구간"은 prefix[i] - K를 해시에서 찾는 방식으로 O(N)에 처리합니다. "합이 K 이하인 최장"처럼 부등호 조건이면 단조 덱(deque)이나 이진 탐색을 얹습니다.
• 최댓값/최솟값 창: 창 안의 최댓값을 계속 알아야 하면 합처럼 빼고 더할 수 없습니다. 인덱스를 담는 단조 덱을 유지해 창 밖으로 나간 인덱스를 앞에서 버리는 방식으로 O(N)을 만듭니다.

시각화로 "빼고 더하기"의 리듬을 본 뒤, 고정 크기 → 가변 크기(합 조건) → 구성 조건(Map 결합) 순으로. 이 유형은 이 사이트에 문제가 많으니 사다리를 끝까지 오르세요.