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

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

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

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

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

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

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

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

예시를 통해 알아볼까요?

예시: 최대 부분합 찾기

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

먼저 예시로 [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] 인 배열에서 연속된 3개의 숫자의 합이 최대가 되는 값을 찾아볼까요?

눈으로 봤을 때 연속된 3개의 숫자의 합들이  

6, 9, 12, 15, 18, 21, 24, 27 이라는 것을 알 수 있고

이중의 최대 값은 '27' 이라는 값을 알 수 있겠죠?

이것을 코드로 짜면 어떻게 될까요?

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

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

   # 모든 가능한 부분집합의 합을 계산
   for i in range(n - k + 1):
       # 이 부분 주목! sum(arr[i:i+k])
       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 연산을 하게 되는데요.

current_sum = sum(arr[i:i+k])
# 연속된 k개의 숫자의 합
# 이렇게 계산하는 방법보다 더 좋은 방법이 있을까? 를 논의해봅시다.

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

슬라이딩 윈도우에서는 이미 이전 step 에서 계산을 했었는데, 또 계산할 필요가 없다는 관점으로 접근하게 됩니다.

현재의 접근법은 배열의 모든 부분집합을 다 계산하므로, 비효율적이라는 시각으로 볼 수 있습니다.

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 은 이전 윈도우의 합 
       # arr[i]는 이전 윈도우에서 불필요한 값 
       # arr[i + 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 = window_sum - arr[i] + arr[i + k]
# 연속된 k개의 숫자의 합
# window_sum 은 이전 Step 에서 연속된 k개의 숫자의 합
# arr[i] 는 이전 Step 에서는 필요했지만, 현재 Step 에서는 불필요해진 값
# arr[i + k] 는 이전 Step 에서는 없었지만, 현재 Step 에서 신규로 추가된 값

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

다음 스탭 부터는

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

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

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

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

다른 예시로 들어볼까요?

현재 위에서는 k의 값(윈도우의 사이즈)이 3일 때를 가정했기 때문에 아마 체감이 안오셨을 수도 있어요.

k 값 (윈도우의 사이즈)를 늘려서 

k=10 

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

위 값으로 가정하고 시각화를 해보면 어떻게 될까요?

이럴때 슬라이딩 윈도우를 사용하지 않고, 매 단계마다  

sum(arr[i:i+10])
현재 단계에서의 윈도우 배열의 합계

이 값을 계산하는 것은 매 단계마다 10개의 숫자를 더해주겠지만, 

window_sum = window_sum - arr[i] + arr[i + k]
이전 단계의 합 - 현재 단계에서 제외되는 값 (빨간색) + 현재 단계에서 추가되는 값 (파란색)

이 값을 계산하는 것은 매 단계마다 변경되는 2개의 값 (빨간색 값, 파란색 값)만 계산해주면 완료됩니다.

슬라이딩 윈도우의 응용

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

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

문제 추천

| 돌핀코딩 | 1902번 - 최대 부분 합 구하기

요약

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

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

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