[Sliding Window] 슬라이딩 윈도우 알고리즘

슬라이딩 윈도우 알고리즘(Sliding Window)

고정된 사이즈의 윈도우를 이동시켜셔 윈도우 내에 있는 데이터를 이용해 문제를 푸는 알고리즘이다.

 

배열이나 리스트의 요소의 일정 범위의 값을 비교할 때 사용하기에 유용하다

ex) 구간 합 구하기, 부분 문자열 구하기 등

 

 

 

슬라이딩윈도우와 투포인터

슬라이딩 윈도우 알고리즘은 *투 포인터와 유사하게 부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘이지만, 부분 배열의 길이(크기)가 고정적 이라는 가장 큰 차이점이 있다.

 

	슬라이딩 윈도우	투포인터
공통점	-  부분 배열들을 활용하여 특정 조건을 일치시키는 알고리즘 - 선형 공간(1차원 배열)을 2회 이상 반복적으로 탐색해야 할 경우 O(N²) 이상 걸릴 시간 복잡도를 부분 배열을 활용하여 O(N)으로 줄일 수 있다
차이점	구간의 넓이가 고정	구간의 넓이가 조건에 따라 유동적으로 변화

 

 

* 투 포인터(two pointers)알고리즘 : 1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키는 2개의 포인터를 조작하며 원하는 값을 얻는 형태의 알고리즘

 

 

슬라이딩 윈도우 동작원리

{A, A, A, C, C, T, G, C}라는 배열이 있다고 가정해보자. 그리고 이 배열에서 길이가 3인 부분 문자열을 슬라이딩 윈도우를 이용해 구해보자

 

먼저, 길이가 3인 부분집합의 초기배열을 설정한다.

 

이후 제일 앞에 요소를 제거한 후, 제일 마지막요소의 다음요소를 부분문자열에 포함시킨다.

 

위에서 했던 과정을 반복하며 부분 문자열을 구한다.

 

 

간단한 원리이다.

 

 

슬라이딩 윈도우를 활용한 문제풀이

 

1. 꿀 아르바이트 (백준 12847)

 

n, m = map(int, input().split())
pay = list(map(int, input().split()))

# 첫 윈도우의 합 계산
current_sum = sum(pay[:m])
max_sum = current_sum

# 슬라이딩 윈도우 적용
for i in range(m, n):
    current_sum = current_sum - pay[i - m] + pay[i]
    max_sum = max(current_sum, max_sum)

print(max_sum)