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

 

슬라이딩 윈도우?

투포인터와 매우 비슷한 알고리즘으로 

 

리스트 안에 윈도우(특정 범위)가 있을때

윈도우 내부 요소들의 값을 이용하여 문제를 풀이하는 알고리즘이다.

 

투포인터는 두개의 포인터를 바탕으로 움직임으로 가변적인 사이즈를 체크하지만

슬라이딩 윈도우는 고정적인 사이즈의 윈도우를 사용한다.  (좌 우중 한방향으로 이동)

 

 

 

슬라이딩 윈도우를 공부할 때 가장 많이 언급하는 예시가 두가지 있다. 

 

ex1 리스트가 있을 때 k = 3 크기의 슬라이딩 윈도우를 오른쪽 끝까지 이동하며 최대값을 구하라.

li = [2,5,3,6,7,1]

2

5

3

6

7

1

               윈도우 한칸 이동시 

2

5

3

6

7

1

                윈도우 한칸 이동시 

2

5

3

6

7

1

               윈도우 한칸 이동시 

2

5

3

6

7

1

노랑색의 슬라이딩 윈도우의 구간을 사용해 구간합을 구하고, 가장 큰값을 리턴하면 된다.

 

 

## 윈도우를 옮기면 중간에 값이 겹치기 때문에 그 겹치는 값 (이전에 계산한 값)을 이후에 사용하면 된다. 

 

코드를 통해 좀더 정확히 확인해보자. 

window의 크기는 3이고,

초기값으로 li[0]부터 2까지가 가장 크다고 가정하에 res에 할당했다.

여기에서 한칸씩 오른쪽으로 넘어가면서 구간합을 계산(이전의 값을 빼고 다음값을 더함으로써 O(1) 이다.)

 

 

결과적으로 가장 큰 구간합은 3 6 7 을 더한 16이 나온다. 

li = [2,5,3,6,7,1]
n = len(li)
k = 3

res = li[0] + li[1] + li[2]

for i in range(1,n-2):
   res = max(res, res - li[i-1] + li[i+2])  #O(1)

print(res)

 

이런식으로 고정 크기의 윈도우를 사용함으로써 좀더 편리하고 빠른 계산을 할 수 있다.