[Algorithm] 슬라이딩 윈도우

Algorithm in HelloMinchan

[Algorithm] 슬라이딩 윈도우

(글쓴날 : 2020.05.15)

 

---

* 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다.

---

 

 

슬라이딩 윈도우

---

1) 슬라이딩 윈도우란?

슬라이딩 윈도우 알고리즘은 사실 따로 다룰 필요가 없을 정도로 투 포인터 알고리즘과 비슷합니다.

딱 한 가지 다른 점은 바로 범위의 제한인데, 투 포인터의 경우 연산을 위하여 포인터를 이동시키는 범위에 대한 제한이 전혀 없지만, 슬라이딩 윈도우의 경우 특정 범위를 제한하여 이동하는 특징이 있습니다.

이에 따라 크기가 고정적인 창문(특정 범위)을 옆으로 미는 것(이동)을 묘사하여 슬라이딩 윈도우라는 이름이 붙은 것 같습니다.

 

이런 슬라이딩 윈도우는 주로, 자료구조 Deque를 사용하여 구현합니다.

예를 들어, N개의 숫자가 들어있는 1차원 배열에서 특정 범위 L마다의 최솟값을 구하고 싶을 경우에 적용한다면,

다음과 같은 로직의 순서로 해결할 수 있습니다.

 

1) N개의 배열 값들을 차례로 탐색합니다.

2) 탐색 중인 수와 덱에 저장되어 있는 수를 뒤에서부터 비교하여 만약, 덱에 저장되어 있는 수가 더 클 경우, 범위 내에서 최솟값이 될 수 없는 수이므로 해당 값들을 전부 뒤로 빼줍니다.

3) 현재 탐색 중인 수를 인덱스와 함께 덱에 저장합니다.

4) 그 후, 덱에 저장되어 있는 수를 앞에서부터 체크하여 만약 특정 범위 밖에 있는 인덱스일 경우 전부 앞으로 빼줍니다.

 

이렇게 되면, 덱의 맨 앞에 저장되어 있는 수가 문제에서 요구하는 특정 범위의 최솟값으로 유지되게 됩니다.

단, 덱을 사용함으로써 주의해야 할 점이 한 가지 있는데, 덱에서 값을 빼기 전 항상 덱이 비었는지 체크해 주어야 빈 덱에서 값을 빼는 에러를 사전에 방지할 수 있습니다.

---

2) 코드

코드는 위에서 예시로 든 문제를 해결하는 템플릿이며, 백준 11003번 최솟값 찾기 문제와도 같습니다.

 

* Python 코드

from collections import deque
 
N, L = 7, 3
arr = [1, 2, 3, 7, 5, 4, 3]
 
# 덱 생성
dq = deque()
 
# 로직 1)
for i in range(N):
    # 로직 2)
    while dq and dq[-1][1] > arr[i]:
        dq.pop()
 
    # 로직 3)
    dq.append((i, arr[i]))  # 튜플 형태로 저장 : (인덱스, 수(값))
 
    # 로직 4)
    while dq and dq[0][0] < i - L + 1:
        dq.popleft()
    
    # 범위내의 최솟값 출력  
    print(dq[0][1], end=" ")  # 출력 결과 : 1 1 1 2 3 4 3

---