sko.kr
  • 홈
  • 블로그
  • 알고리즘 - 1. 슬라이딩 윈도우 (고정 크기)

알고리즘 - 1. 슬라이딩 윈도우 (고정 크기)

algorithmssliding-windowarraysoptimizationtwo-pointers
By sko•9/27/2025•2 min read

고정 크기 슬라이딩 윈도우를 언제 사용할까

특정 크기의 최적 연속 부분 배열을 찾아야 할 때 고정 크기 슬라이딩 윈도우를 사용합니다. 크기 제약이 제한적으로 보이지만, 이 패턴은 자주 나타납니다:

  • 최대/최소 합 k개의 연속 원소 (전형적인 사용 사례)
  • 평균 k개의 연속 원소
  • 패턴 매칭 고정 길이 패턴으로 (애너그램 찾기 등)
  • 롤링 해시 부분 문자열 매칭을 위한
  • 시계열 분석 고정 시간 윈도우로 (예: 7일 이동 평균)
  • 크기 k의 모든 부분 배열 분석을 요구하는 모든 문제

예제 문제

K개 원소의 최대 합: 일일 매출 수익 [100, 200, 300, 400, 100, 200, 50]이 주어졌을 때, 가장 높은 총 수익을 가진 3연속일 기간을 찾으세요.

  • 일[0-2]: 100 + 200 + 300 = 600
  • 일[1-3]: 200 + 300 + 400 = 900 ✓ 최고 기간
  • 일[2-4]: 300 + 400 + 100 = 800
  • 일[3-5]: 400 + 100 + 200 = 700
  • 일[4-6]: 100 + 200 + 50 = 350

답: 1-3일이 최고 총 수익 $900을 기록했습니다.

가장 중요한 통찰

중복 계산을 재사용하라 - 크기 k의 인접한 윈도우는 k-1개의 공통 원소를 공유하고, 나가는 하나의 원소와 들어오는 하나의 원소만 다르므로, 모든 것을 재계산하는 대신 이 두 변화만 업데이트하여 O(n*k) 대신 O(n) 복잡도를 달성합니다.

메모: 이 알고리즘의 천재성은 인접한 윈도우가 상당히 겹친다는 것을 인식하는 데 있습니다. 크기 3의 윈도우의 경우, 앞으로 이동시키는 것은 2개의 원소가 동일하게 유지됨을 의미하며 - 가장 왼쪽만 나가고 새로운 가장 오른쪽이 들어옵니다. 처음부터 재계산하는 대신, 실행 중인 상태를 유지하고 점진적으로 업데이트합니다. 하나의 뺄셈, 하나의 덧셈 - 다음 윈도우로 "슬라이드"하는 데 필요한 전부입니다.

결정 프레임워크

윈도우의 모든 슬라이드에서, 두 가지 연산을 수행합니다:

  • 윈도우를 떠나는 원소의 기여도를 제거 (왼쪽)
  • 윈도우에 들어오는 원소의 기여도를 추가 (오른쪽)

코드

// 참고: while문이 아닌 for문을 사용하는 이유:
// - 고정 크기 슬라이딩 윈도우에서는 각 원소를 정확히 한 번 처리한다
// - 오른쪽 포인터는 항상 1씩 증가한다
// - for문이 더 깔끔하고 right++ 잊는 것을 방지한다

// 정확히 크기 k의 고정 윈도우
// 가능한 모든 k 크기 윈도우를 검사해야 한다
function maxSumOfK(nums: number[], k: number): number {
  if (nums.length < k) return -1;

  let windowSum = 0;
  let maxSum = -Infinity;
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 현재 원소를 윈도우에 추가
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 결정 프레임워크: 정확히 크기 k의 윈도우 유지
    const windowSize = right - left + 1;
    // 윈도우가 정확히 k일 때 처리하고, 그 후 슬라이드
    if (windowSize === k) {
      maxSum = Math.max(maxSum, windowSum);
      // 다음 반복을 위해 윈도우 슬라이드
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return maxSum;
}

// 최대 크기 k의 윈도우
// "k 거리 내 중복"은 k를 초과하지 않는 윈도우가 필요함을 의미
function hasDuplicateWithinK(nums: number[], k: number): boolean {
  const window = new Set<number>();
  let left = 0;

  for (let right = 0; right < nums.length; right++) {
    // 결정 프레임워크: 윈도우 크기 <= k 유지
    // 위와 다른 이유? "k 거리 내"는 최대 k개 원소만큼 떨어져 있음을 의미
    // 따라서 k까지 성장하고, 그 후 크기 k에서 슬라이드하는 고정 윈도우를 유지
    const windowSize = right - left + 1;
    const windowExceedsK = windowSize > k;
    if (windowExceedsK) {
      const elementLeavingWindow = nums[left];
      window.delete(elementLeavingWindow);
      left++;
    }

    // 현재 윈도우에서 중복 확인
    const currentElement = nums[right];
    const isDuplicate = window.has(currentElement);

    if (isDuplicate) {
      return true;
    }

    // 현재 원소를 윈도우에 추가
    window.add(currentElement);
  }

  return false;
}

의문 해결

흔한 의문: "왜 윈도우 합을 추적하나요? 중첩 루프를 사용해서 각 k개 원소의 윈도우를 별도로 합계할 수 없나요?"

중첩 루프로 충분하다고 생각하는 이유

k=3으로 [100, 200, 300, 400, 100, 200, 50]에서 최대 합을 찾는 것을 고려해보세요:

  • "시작 위치용 외부 루프, k개 원소를 합하는 내부 루프를 사용할 수 있다"
  • "각 시작 위치 i에 대해, i부터 i+k-1까지 합한다"
  • "단지 3개 원소이므로, 내부 루프는 작다"
  • "코드가 더 직관적이다 - 무엇이 합해지는지 정확히 볼 수 있다"

이런 생각이 비효율적인 이유

핵심 깨달음: 중첩 루프는 같은 원소들을 반복적으로 재계산합니다!

k=3으로 [100, 200, 300, 400, 100, 200, 50]을 추적해봅시다:

중첩 루프 접근법 (O(n*k)):
윈도우 [0-2]: 100 + 200 + 300 = 600    (3번 덧셈)
윈도우 [1-3]: 200 + 300 + 400 = 900    (3번 덧셈)
윈도우 [2-4]: 300 + 400 + 100 = 800    (3번 덧셈)
윈도우 [3-5]: 400 + 100 + 200 = 700    (3번 덧셈)
윈도우 [4-6]: 100 + 200 + 50 = 350     (3번 덧셈)
총계: 15번 덧셈

슬라이딩 윈도우 (O(n)):
초기 [0-2]: 100 + 200 + 300 = 600   (3번 덧셈)
[1-3]으로 슬라이드: 600 - 100 + 400 = 900  (1번 뺄셈, 1번 덧셈)
[2-4]로 슬라이드: 900 - 200 + 100 = 800  (1번 뺄셈, 1번 덧셈)
[3-5]로 슬라이드: 800 - 300 + 200 = 700  (1번 뺄셈, 1번 덧셈)
[4-6]으로 슬라이드: 700 - 400 + 50 = 350   (1번 뺄셈, 1번 덧셈)
총계: 3번 덧셈 + 4번 뺄셈 + 4번 덧셈 = 11번 연산

300 같은 원소가 중첩 루프에서는 3번 더해지지만, 슬라이딩 윈도우에서는 단 한 번만 더해진다는 것을 주목하세요!

구체적 예시: 확장 문제

k=1000으로 10,000개 원소 배열에서 최대 합을 찾는 경우:

중첩 루프:

  • 각 윈도우: 1000개 원소 합계
  • 총 윈도우 수: 9001
  • 총 덧셈 횟수: 9,001,000

슬라이딩 윈도우:

  • 초기 윈도우: 1000번 덧셈
  • 각 슬라이드: 1번 뺄셈 + 1번 덧셈
  • 총 연산 수: 1000 + (9000 × 2) = 19,000
  • 474배 빠름!

최적화가 중요한 이유

슬라이딩 윈도우 기법은:

  • 중복 계산을 재사용 (k-1개 원소는 동일하게 유지)
  • 각 원소는 정확히 한 번 더해지고 정확히 한 번 빼짐
  • 같은 원소들의 중복 계산 없음
  • O(n×k) 중첩 루프 해법을 O(n) 슬라이딩 윈도우로 변환

핵심 통찰: 윈도우를 한 위치 이동시킬 때, 단지 2개 원소만 변경됩니다 (하나는 나가고, 하나는 들어옴). 그런데 왜 모든 것을 재계산할까요?

← Back to Blog