슬라이딩 윈도우(Sliding Window) 알고리즘 개념-고정크기,가변크기,투포인터 슬라이딩 윈도우

 

연속된 구간(부분 배열 또는 부분 문자열)을 다룰 때 사용되며, O(n)의 시간 복잡도로 효율적인 문제 해결이 가능합니다.

---

🔹 슬라이딩 윈도우 알고리즘 개념

💡 일반적인 접근법

1. 초기 윈도우를 설정 (길이 k의 첫 번째 부분 배열 또는 문자열)
2. 윈도우를 한 칸씩 이동하면서 이전 값은 제거하고 새로운 값을 추가
3. 필요한 계산을 업데이트 (예: 합, 평균, 최대값, 최소값 등)
4. 모든 윈도우에 대해 최적값을 찾음

💡 시간 복잡도

• 단순 O(n * k) 브루트포스 접근법을 O(n)으로 최적화할 수 있음
• 모든 원소를 한 번씩만 처리하므로 O(n)

---

🔹 슬라이딩 윈도우 알고리즘 유형

1️⃣ 고정 크기(Fixed Size) 슬라이딩 윈도우

📌 길이가 k인 고정된 윈도우를 이동시키며 계산하는 방식
📌 대표 문제: 최대/최소 합, 평균, 특정 조건을 만족하는 연속 부분 문자열

function maxSumSubarray(arr, k) {
    let maxSum = 0;
    let currentSum = 0;

    // 초기 윈도우 계산 (첫 k개의 합)
    for (let i = 0; i < k; i++) {
        currentSum += arr[i];
    }
    maxSum = currentSum;

    // 윈도우를 이동하며 업데이트
    for (let i = k; i < arr.length; i++) {
        currentSum += arr[i] - arr[i - k]; // 새로운 값 추가, 오래된 값 제거
        maxSum = Math.max(maxSum, currentSum);
    }

    return maxSum;
}

// 테스트
console.log(maxSumSubarray([2, 1, 5, 1, 3, 2], 3)); // 9 (5+1+3)

 

✅ 이해하기 쉬운 포인트

• currentSum을 활용하여 이전 값을 빼고, 새 값을 더하면서 윈도우를 유지
• 한 번만 순회하므로 O(n)

---

2️⃣ 가변 크기(Variable Size) 슬라이딩 윈도우

📌 윈도우 크기가 가변적이며 특정 조건을 만족할 때만 확장/축소
📌 대표 문제: 최소 길이 부분 배열 찾기, 특정 조건을 만족하는 연속 부분 문자열

function minSubarrayLen(arr, target) {
    let left = 0, sum = 0;
    let minLength = Infinity;

    for (let right = 0; right < arr.length; right++) {
        sum += arr[right];  // 우측 확장

        while (sum >= target) {  // 조건 충족 시 최소 길이 업데이트 후 축소
            minLength = Math.min(minLength, right - left + 1);
            sum -= arr[left];
            left++;  // 왼쪽 이동
        }
    }

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

// 테스트
console.log(minSubarrayLen([2, 3, 1, 2, 4, 3], 7)); // 2 (4+3)

✅ 이해하기 쉬운 포인트

• 우측을 확장하면서 합을 누적
• 조건 충족 시 좌측을 줄이며 최소 길이 업데이트
• while을 통해 특정 조건을 만족하는 최소 윈도우를 찾아냄

---

3️⃣ 투 포인터(Two Pointers)와 결합된 슬라이딩 윈도우

📌 투 포인터(Two Pointer)와 유사한 개념이지만, 윈도우 내부 조건을 최적화
📌 대표 문제: 두 개의 포인터로 최적 구간을 찾는 문제 (예: 부분 문자열, 배열 구간)

function longestSubstringWithoutRepeating(s) {
    let charSet = new Set();
    let left = 0, maxLength = 0;

    for (let right = 0; right < s.length; right++) {
        while (charSet.has(s[right])) {
            charSet.delete(s[left]);  // 중복 제거
            left++;
        }
        charSet.add(s[right]);
        maxLength = Math.max(maxLength, right - left + 1);
    }

    return maxLength;
}

// 테스트
console.log(longestSubstringWithoutRepeating("abcabcbb")); // 3 ("abc")

✅ 이해하기 쉬운 포인트

• 중복 문자가 발생하면 좌측을 이동하여 해결
• 윈도우 크기를 유지하면서 최적의 부분 문자열을 찾음

---

🔹 슬라이딩 윈도우 알고리즘의 장점

✅ O(n)으로 최적화 가능 → 모든 원소를 한 번만 확인하며 처리
✅ 별도 리스트 저장 없이 O(1) 공간만 사용 가능
✅ 연속된 데이터 처리에 적합 (문자열, 배열, 시간 기반 데이터 등)

---

🔹 슬라이딩 윈도우를 사용하는 대표 문제

 

✅ 고정 크기 윈도우	최대 합 서브배열	주어진 길이의 부분 배열에서 최대 합 찾기
✅ 가변 크기 윈도우	최소 길이 부분 배열	특정 조건을 만족하는 최소 길이 찾기
✅ 투 포인터 결합	중복 없는 가장 긴 부분 문자열	같은 문자가 없는 가장 긴 연속 부분 문자열 찾기
✅ 모음 포함 부분 문자열	[findSubstring 문제 (네가 푼 문제!)]	특정 문자 개수를 만족하는 부분 문자열 찾기

---

🔹 정리

1. 고정 크기(Fixed Size) → O(n) 유지하면서 k 길이 유지
2. 가변 크기(Variable Size) → 조건을 만족하면 좌측을 축소하여 최적 길이 찾기
3. 투 포인터 결합(Two Pointers) → 중복 없이 특정 속성을 유지하는 구간 찾기