슬라이딩 윈도우 - Sliding Window

📌 슬라이딩 윈도우란?

슬라이딩 윈도우 - $Sliding$ $Window$

📌 구간의 길이가 M일때 특정한 조건을 만족하는가?

배열이 주어졌을때 문제에서 주어지는 구간의 크기에서 특정조건을 만족하는 경우를 찾는 알고리즘이다.
슬라이딩 윈도우는 투 포인터와 아주 유사하기 때문에 투 포인터를 먼저 공부하고 슬라이딩 윈도우를 공부하는것을 추천하다.

투 포인터 알고리즘에 대해 본인이 직접 쓴 내용이다.

투 포인터에 대해 알고있으면 슬라이딩 윈도우는 바로 이해할 것이다.

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

슬라이딩 윈도우 알고리즘은 투 포인터 알고리즘과 아주 유사하다.
다만 두 알고리즘의 차이는 투 포인터는 범위가 유동적으로 매번 바뀌고
슬라이딩 윈도우는 탐색구간의 길이가 정해져 있다는 점이다.

따라서 투 포인터에 대해 이해했으면 살짝만 코드를 수정해서 슬라이딩 윈도우 알고리즘으로 활용할 수 있다.

투 포인터는 원하는 값에 따라 Start 값과 End 값을 유동적으로 움직이지만

슬라이딩 윈도우는 구간의 길이를 유지하기 위해서
매번 Start 값과 End 값이 1씩 움직인다.

📌 슬라이딩 윈도우 코드

N,M=map(int,input().split())
L=list(map(int,input().split()))

total=sum(L[:M])
answer=total
for i in range(M,N):

    total+=L[i] ; total-=L[i-M]

    answer=max(total,answer)
print(answer)

배열의 길이가 $N$ 이고 탐색구간의 길이는 $M$ 일때
$M$길이의 구간중 최대값을 구하는 코드이다.'

특정핪을 구할때는 total 값을 저렇게 변화시키고
배열의 인덱스를 구할때는 Start 와 End 변수를 세워주어서 두 변수를 1씩 매번 증가시킨다. 이때 Start 와 End 의 값의 차이는 문제에서 주어진 탐색해야하는 구간의 길이 $M$ 만큼 차이가 나야한다.

📌 슬라이딩 윈도우의 전제조건

슬라이딩 윈도우는 배열이 정렬되어있을 필요가 없다.
단지 단 하나의 조건만 만족하면 된다.

• 값을 구할때 문제에서 주어진 배열의 범위에서만 탐색한다.

📌 슬라이딩 윈도우의 시간복잡도

슬라이딩 윈도우의 시간복잡도는 모든 배열을 탐색하기 때문에

$O(N)$ 의 시간복잡도가 필요하다. 또한 슬라이딩 윈도우는 배열의 모든 경우를 탐색가능하다.

📌 슬라이딩 윈도우는 언제 써야하는가?

보통 슬라이딩 윈도우 알고리즘을 자주 쓰진않지만 문제에서
"특정한 구간 M에서 조건을 만족하는 경우를 찾으라" 라고 주어지면 사용하면된다.

슬라이딩 윈도우 문제집 - 이 문제집을 통하여서 슬라이딩 윈도우 알고리즘에 대한 감각을 익히는것을 추천한다.