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

알고리즘 - 2. 슬라이딩 윈도우 (가변 크기)

algorithmssliding-windowtwo-pointersoptimizationarraysstrings
By sko•9/28/2025•2 min read

가변 크기 슬라이딩 윈도우를 사용하는 시기

크기가 미리 정해지지 않은 최적의 연속 부분 배열을 찾아야 할 때 가변 크기 슬라이딩 윈도우를 사용합니다. 이 알고리즘은 크기를 최적화하면서 특정 조건을 유지하기 위해 윈도우 경계를 동적으로 조정합니다.

  • 합계 ≥ 목표값인 최소/최대 크기 부분 배열 (대표적인 사용 사례)
  • 중복 문자가 없는 가장 긴 부분 문자열
  • 필요한 모든 문자를 포함하는 최소 윈도우 부분 문자열
  • 특정 속성을 가진 부분 배열의 개수
  • 종류 제약이 있는 최대 아이템 수집 (예: 과일 바구니)
  • 조건을 유지하기 위해 윈도우 크기가 적응하는 모든 문제

예제 문제

최소 장보기 가방: 아이템 무게 [2, 3, 1, 2, 4, 3]이 주어지고 최소 7kg이 필요할 때, 선택해야 할 연속된 아이템의 최소 개수는?

  • 아이템 [0-3]: 2 + 3 + 1 + 2 = 8 kg ✓ (4개 아이템)
  • 아이템 [1-4]: 3 + 1 + 2 + 4 = 10 kg ✓ (4개 아이템)
  • 아이템 [2-4]: 1 + 2 + 4 = 7 kg ✓ (3개 아이템)
  • 아이템 [4-5]: 4 + 3 = 7 kg ✓ (2개 아이템) ← 최적!

답: 2개 아이템 (위치 4-5의 아이템).

가장 중요한 통찰

가능성을 탐색하기 위해 윈도우를 확장하고, 조건이 만족되면 왼쪽에서 축소한다 - 이 확장-축소 댄스는 모든 O(n²) 가능성을 확인하지 않고도 최적의 크기를 찾기 위해 경계를 체계적으로 조정함으로써 모든 유효한 윈도우를 검사하는 것을 보장합니다.

멘탈 노트: 이 알고리즘의 천재성은 "유효한 윈도우 불변식"을 유지하는 데 있습니다. 각 단계에서 우리는 단지 "이 윈도우를 축소해도 여전히 조건을 만족하는가?"라는 간단한 결정만 내립니다. 이 간단한 결정이 자동으로 최적의 윈도우를 찾아냅니다. 모든 가능한 윈도우를 확인하는 대신, 새로운 요소를 포함하도록 확장한 다음, 각 위치에서 끝나는 가장 작은 유효한 윈도우를 찾기 위해 탐욕적으로 축소합니다.

결정 프레임워크

모든 위치에서 알고리즘은 두 가지 순차적인 결정을 내립니다:

  • 확장: 항상 현재 요소를 포함 (오른쪽 포인터 이동)
  • 축소: 조건이 만족되는 동안 왼쪽에서 제거하여 최소화 시도

코드

// 합계 >= 목표값인 최소 크기 부분 배열 찾기
// 중첩 루프가 있지만 O(n) 시간 - 각 요소는 최대 2번 방문됨
function shortestSubarray(nums, target) {
  let left = 0;
  let windowSum = 0;
  let minLength = Infinity;

  for (let right = 0; right < nums.length; right++) {
    // 단계 1: 확장 - 항상 현재 요소 포함
    const elementEnteringWindow = nums[right];
    windowSum += elementEnteringWindow;

    // 결정 프레임워크: 축소해도 여전히 조건을 만족하는가?
    // 단순히 유효한 윈도우가 아닌, 최적의 윈도우를 찾기 위해 while 사용 (if가 아님)
    while (windowSum >= target) {
      // 현재 윈도우가 조건을 만족함, 가장 작은 경우 기록
      const currentWindowSize = right - left + 1;
      minLength = Math.min(minLength, currentWindowSize);

      // 왼쪽에서 축소하여 더 작은 유효한 윈도우 찾기 시도
      const elementLeavingWindow = nums[left];
      windowSum -= elementLeavingWindow;
      left++;
    }
  }

  return minLength === Infinity ? 0 : minLength;
}

// 최대 k개의 서로 다른 문자를 가진 가장 긴 부분 문자열
// 문제: 최대 k개의 서로 다른 문자를 포함하는 가장 긴 부분 문자열 찾기
// 예: k=2인 "eceaba" → "eceab"는 3개 문자 ✗, "eceba"는 3개 문자 ✗, "ece"는 2개 문자 ✓
function longestSubstringKDistinct(s, k) {
  const charFrequency = new Map(); // 윈도우 내 각 문자의 개수 추적
  let left = 0;
  let maxLength = 0;

  for (let right = 0; right < s.length; right++) {
    // 확장: 윈도우에 문자 추가
    const charEntering = s[right];
    charFrequency.set(charEntering, (charFrequency.get(charEntering) || 0) + 1);

    // 결정 프레임워크: k개를 초과하는 서로 다른 문자가 있으면 왼쪽에서 축소
    // 왜 오른쪽이 아닌 왼쪽에서 축소하는가? 이유:
    // 1. 우리는 체계적으로 모든 위치를 오른쪽 경계로 시도하고 있음
    // 2. 각 오른쪽 위치에 대해 가장 왼쪽의 유효한 위치를 찾음
    // 3. 이는 모든 가능한 윈도우를 확인하는 것을 보장함 (아래 의문 해소 참조)
    while (charFrequency.size > k) {
      const charLeaving = s[left];
      const count = charFrequency.get(charLeaving);

      // 윈도우를 떠나는 문자의 빈도 감소
      if (count === 1) {
        // 마지막 출현, 맵에서 제거
        charFrequency.delete(charLeaving);
      } else {
        // 윈도우에 아직 더 많은 출현이 있음
        charFrequency.set(charLeaving, count - 1);
      }
      left++;
    }

    // 여기서 윈도우는 유효함 (≤ k개의 서로 다른 문자), 최대값 업데이트
    const currentWindowSize = right - left + 1;
    maxLength = Math.max(maxLength, currentWindowSize);
  }

  return maxLength;
}

의문 해소

일반적인 의문: "왜 왼쪽에서만 축소하는가? 오른쪽에서 제거하면 더 나은 결과를 얻을 수 있지 않을까?"

오른쪽에서 제거하는 것이 더 나을 수 있다고 생각하는 이유

이것은 자연스러운 우려입니다! 윈도우에 너무 많은 서로 다른 문자가 있을 때 다음과 같이 생각할 수 있습니다:

  • "방금 추가한 문자(오른쪽)가 문제인가?"
  • "오른쪽에서 제거하면 더 긴 유효한 윈도우를 유지할 수 있지 않을까?"
  • "양쪽 방향을 시도하고 더 나은 것을 선택해야 하지 않을까?"
  • "항상 왼쪽에서 축소하는 탐욕적 선택이 임의적으로 보인다"

예를 들어, 문자열 "abcba"와 k=2인 경우:

  • 인덱스 2(문자 'c')에 도달하면 윈도우는 3개의 서로 다른 문자를 가진 "abc"가 됨
  • 왼쪽에서 제거하면 "bc" (길이 2)
  • 하지만 오른쪽에서 제거하면 "ab" (역시 길이 2)?
  • 두 옵션을 모두 고려해야 하지 않을까?

이 생각이 틀린 이유

핵심 깨달음: 오른쪽에서 제거할 필요가 없습니다. 왜냐하면 그 옵션을 향후 반복에서 자연스럽게 탐색할 것이기 때문입니다!

결정적인 통찰은 다음과 같습니다: 알고리즘은 체계적으로 모든 위치를 오른쪽 경계로 시도합니다. 따라서 오른쪽에서 제거하는 것이 더 나은 윈도우를 제공한다면, 그 위치에 도달했을 때 발견할 것입니다.

"abcba"와 k=2로 이를 증명해 보겠습니다:

right=0: 윈도우 ["a"], 1개의 서로 다른 문자, 유효 ✓
right=1: 윈도우 ["ab"], 2개의 서로 다른 문자, 유효 ✓, maxLen=2
right=2: 윈도우 ["abc"], 3개의 서로 다른 문자, 무효 ✗
  - 왼쪽에서 축소: ["bc"], 2개의 서로 다른 문자, 유효 ✓
right=3: 윈도우 ["bcb"], 2개의 서로 다른 문자, 유효 ✓, maxLen=3
right=4: 윈도우 ["bcba"], 3개의 서로 다른 문자, 무효 ✗
  - 축소: ["cba"], 3개의 서로 다른 문자, 여전히 무효 ✗
  - 축소: ["ba"], 2개의 서로 다른 문자, 유효 ✓

핵심 통찰: "abc"가 있고 왼쪽에서 제거하여 "bc"를 얻었을 때, "ab"를 놓쳤다고 걱정했습니다. 하지만 주목하세요:

  • 윈도우 "ab"는 right=1일 때 이미 평가되었습니다!
  • 그 시점에 길이(2)를 기록했습니다
  • 나중에 길이 3인 "bcb"를 찾았는데, 이것이 더 좋습니다

모든 가능한 윈도우가 평가됩니다, 왜냐하면:

  1. 위치 1에서 끝나는 윈도우: ["a"], ["ab"]를 시도
  2. 위치 2에서 끝나는 윈도우: ["abc"]→["bc"], ["c"]를 시도
  3. 위치 3에서 끝나는 윈도우: ["bcb"], ["cb"], ["b"]를 시도
  4. 계속...

알고리즘은 어떤 윈도우도 놓치지 않습니다 - 체계적으로 모두 평가합니다!

구체적인 증명: 왜 왼쪽에서 축소하는 것만으로 충분한가

이렇게 생각해 보세요: 최적의 윈도우 [i, j]가 있다면, 알고리즘은 그것을 찾을 것입니다:

  1. 오른쪽 포인터가 j에 도달했을 때: 어떤 왼쪽 위치부터 j까지의 모든 요소를 가짐
  2. while 루프가 축소: 윈도우가 유효해질 때까지 왼쪽 포인터를 오른쪽으로 이동
  3. i 또는 그 이전에 멈춤: [i, j]가 유효하므로, 축소는 위치 i까지 멈출 것
  4. 이 윈도우를 기록: 지금까지 본 것 중 최고라면 최대값 업데이트

오른쪽에서 제거하는 것이 중복인 이유

위치 right=5에서 윈도우 [2,3,4,5]가 있고 무효하다고 상상해 보세요. "[2,3,4]가 [3,4,5]보다 나을 수 있다"고 생각할 수 있습니다.

하지만 [2,3,4]를 확인할 필요가 없는 이유는:

  • right가 위치 4에 있을 때 이미 [2,3,4]를 확인했습니다!
  • [2,3,4]가 유효하고 좋았다면 그때 기록했습니다
  • 이제 위치 5에서 5로 끝나는 최고의 윈도우를 찾고 있습니다
  • 다음 반복(right=6)에서 6으로 끝나는 최고의 윈도우를 찾을 것입니다

알고리즘의 보장: 배열의 모든 가능한 윈도우에 대해 다음과 같은 순간이 있을 것입니다:

  • 오른쪽 포인터가 윈도우의 끝 위치에 있음
  • 왼쪽 포인터가 윈도우의 시작 위치로 (또는 지나서) 이동됨
  • 따라서 모든 윈도우가 정확히 한 번 평가됨

이것이 O(n²)가 필요해 보이지만 알고리즘이 O(n)인 이유입니다 - 백트래킹이나 이전 결정을 재고할 필요가 없습니다.

← Back to Blog