슬라이딩 윈도우(Sliding Window)

슬라이딩 윈도우(Sliding Window)

알고리즘 문제를 풀다 보면, 배열이나 문자열과 같이 연속된 구간에 대한 처리가 필요할 때가 있을텐데,

이때 슬라이딩 윈도우 기법을 사용하면 도움이 된다.

---

1. 슬라이딩 윈도우란?

슬라이딩 윈도우 기법은 두 개의 포인터(또는 인덱스)를 사용하여

배열이나 문자열의 특정 구간(윈도우)를 유지하면서 문제를 해결하는 방법이다.

이 기법은 주로 다음과 같은 상황에서 유용하게 사용된다.

• 연속된 구간의 합 구하기
• 특정 조건을 만족하는 최대 또는 최소 길이 구하기
• 중복이 없는 가장 긴 구간 찾기 등

---

2. 기본 아이디어

슬라이딩 윈도우는 아래의 단계를 반복하면서 문제를 해결한다.

• 윈도우 정의
  시작 인덱스(left)와 끝 인덱스(right)를 두어 구간을 정의한다.
  
  
• 윈도우 확장
  right 포인터를 이동시키면서 윈도우에 새로운 요소를 추가한다.
  
  
• 조건 만족 여부 확인
  윈도우에 포함된 요소에 대해 문제에서 요구하는 조건(예: 중복이 없는지, 합이 특정 값 이하인지 등)을 확인한다.
  
  
• 윈도우 축소
  조건을 만족하지 못하는 경우, left 포인터를 이동시켜 윈도우에서 요소를 제거한다.
  
  
• 최적값 갱신
  조건을 만족하는 윈도우가 등장하면, 해당 윈도우의 길이와 합 등 문제에서 요구하는 값을 갱신한다.

---

3. 시간 복잡도

슬라이딩 윈도우의 시간 복잡도는 일반적으로 배열이나 문자열을 한 번만 탐색하기 때문에 O(N)으로 매우 효율적이다

---

4. 예시 풀어보기(Python)

[주어진 배열에서 합이 특정 값 이하인 연속된 부분 배열 중 최대 길이 구하기]
nums = [1, 3, 2, 5, 1, 1, 2, 3]
max_sum = 7

풀이 보기

nums = [1, 3, 2, 5, 1, 1, 2, 3]
max_sum = 7

left, total = 0, 0
max_length = 0

for right in range(len(nums)):
    total += nums[right]  # 윈도우 확장 (새로운 요소 추가)

    # 조건을 만족하지 않을 때까지 윈도우 축소
    while total > max_sum:
        total -= nums[left]
        left += 1

    # 조건을 만족하는 최대 길이 갱신
    max_length = max(max_length, right - left + 1)

print(max_length)  # 결과: 4 ([2,5] 또는 [5,1,1] 등)