슬라이딩 윈도우(Sliding Window)란?

슬라이딩 윈도우(Sliding Window)란?

슬라이딩 윈도우는 데이터를 일정한 크기의 윈도우(부분집합)로 나누어 이동하면서 처리하는 기법입니다. 

주로 배열이나 리스트에서 연속된 요소를 다룰 때 사용됩니다. 

이 기법은 알고리즘의 성능을 향상시키고 문제를 효율적으로 해결하는 데 매우 유용합니다.

슬라이딩 윈도우의 기본 개념

슬라이딩 윈도우는 다음과 같은 방식으로 작동합니다.

1. 윈도우 설정: 일정한 크기의 윈도우를 설정합니다.
2. 윈도우 이동: 데이터를 처음부터 끝까지 일정한 간격으로 윈도우를 이동하며 처리합니다.

예시를 통해 알아볼까요?

예시: 최대 부분합 찾기

주어진 배열에서 연속된 k개의 숫자의 합이 최대가 되는 값을 찾는 문제를 생각해봅시다.

1. 기본 접근법 (모든 경우 탐색)

def max_sum(arr, k):
   n = len(arr)
   max_sum = 0

   # 모든 가능한 부분집합의 합을 계산
   for i in range(n - k + 1):
       current_sum = sum(arr[i:i+k])
       max_sum = max(max_sum, current_sum)

   return max_sum

# 예시 배열
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
print(max_sum(arr, k))  # 출력: 27 (8+9+10)

arr[i:i+k] 를 계속해서 sum 연산을 하게 되는데요.

다음 index 를 순회할 때, 꼭 모든 arr[i:i+k]의 합을 구해야 할까요?

이 접근법은 배열의 모든 부분집합을 다 계산하므로, 비효율적입니다.

2. 슬라이딩 윈도우 접근법

슬라이딩 윈도우를 사용하면 더 효율적으로 문제를 해결할 수 있습니다.

def max_sum_sliding_window(arr, k):
   n = len(arr)
   if n < k:
       return -1

   # 첫 윈도우의 합 계산
   window_sum = sum(arr[:k])
   max_sum = window_sum

   # 슬라이딩 윈도우로 합을 계산
   for i in range(n - k):
       window_sum = window_sum - arr[i] + arr[i + k]
       max_sum = max(max_sum, window_sum)

   return max_sum

# 예시 배열
arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 3
print(max_sum_sliding_window(arr, k))  # 출력: 27 (8+9+10)

이 접근법에서는 첫 번째 윈도우의 합을 계산한 후, 윈도우를 한 칸씩 오른쪽으로 이동하면서 새로운 윈도우의 합을 업데이트합니다. 

window_sum = sum(arr[:k]) 를 통해 첫번째 윈도우의 합을 계산하고

다음 스탭 부터는

- arr[i] 를 통해 첫 요소를 제거한 후, 

+ arr[i + k] 를 통해 추가되는 요소를 합하는 방법을 사용합니다.

이렇게 하면 이전 윈도우의 합에서 첫 번째 요소를 빼고, 

새로 포함된 요소를 더하는 방식으로 윈도우의 합을 계산할 수 있습니다.

슬라이딩 윈도우의 응용

슬라이딩 윈도우 기법은 다양한 문제에 응용될 수 있습니다:

1. 최대 또는 최소 부분합: 연속된 k개의 숫자의 합 중 최대 또는 최소를 찾는 문제.
2. 부분 배열 평균: 연속된 k개의 숫자의 평균을 구하는 문제.
3. 문자열 검색: 문자열에서 특정 패턴을 찾는 문제.
4. 투 포인터 문제: 두 개의 포인터를 사용하여 배열에서 특정 조건을 만족하는 부분 배열을 찾는 문제.

요약

• 슬라이딩 윈도우: 데이터를 일정한 크기의 윈도우로 나누어 이동하며 처리하는 기법.
• 장점: 효율적으로 연속된 데이터를 처리할 수 있습니다.
• 응용 분야: 배열이나 문자열에서 연속된 요소를 다루는 문제.

이제 슬라이딩 윈도우에 대해 잘 이해할 수 있겠죠? 

이 기법을 통해 알고리즘의 성능을 높이고, 문제를 효율적으로 해결해보세요!