슬라이딩 윈도우는 배열, 문자열 또는 기타 데이터 구조에서 고정 크기의 창을 움직이면서 연속적인 요소의 하위 집합을 검사하는 기술이다. 이 기술은 특히 부분 문자열, 연속된 요소 또는 다양한 조건을 만족하는 세그먼트를 검사하는 문제에 유용하게 사용된다.

장점

• 선형 시간 복잡도
• 효율적인 알고리즘으로 문제 해결
• 공간 복잡도를 최소화

예시

function findMaxSum(arr, k) {
  let maxSum = 0, windowSum = 0, windowStart = 0;
  for (let windowEnd = 0; windowEnd < arr.length; windowEnd++) {
    windowSum += arr[windowEnd]; // 새로운 요소 추가
    if (windowEnd >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
      windowSum -= arr[windowStart]; // 윈도우에서 맨 왼쪽 요소 제외
      windowStart++; // 윈도우 유효성 범위 조절
    }
  }
  return maxSum;
}

위 예시는 주어진 배열에서 크기가 k인 부분집합의 요소 합계를 찾는 알고리즘으로 슬라이딩 윈도우를 사용하여 선형 시간 내에 최대 합계를 찾는다.

결론

슬라이딩 윈도우는 배열 또는 문자열과 같은 데이터 구조에서 연속적인 요소의 하위 집합을 검사하는 효율적인 방법을 제공한다. 이를 통해 선형 시간 내에 문제를 해결할 수 있으며, 공간 복잡도를 최소화할 수 있는 장점이 있다.

참조: GeeksforGeeks - Sliding Window Technique