슬라이딩 윈도우는 고정된 크기의 구간인 “윈도우"를 관리하되, 윈도우를 한 단위씩 움직여가면서 구간 내에서의 목푯값을 계산하는 알고리즘입니다.
이때, 고정된 크기의 구간을 움직이는 연산을 지원하기 위해서 덱을 사용할 수 있습니다.
따라서, 목푯값을 계산하는 데 덱을 이용한 최적화를 생각해볼 수 있도록 합니다.
구간의 관리
그럼 구간을 움직이는 연산을 어떻게 덱을 이용해 지원할까요?
구간을 움직일 때 구간의 양 끝에서만 자료의 추가와 삭제가 일어난다는 점에 집중하면 구간을 덱으로 쉽게 관리할 수 있다는 것을 알 수 있습니다.
현재 구간 $[r - k, r]$ 내의 자료가 모두 덱에 위치 순으로 존재하고, 새로운 자료가 $r' (r' \gt r)$ 의 위치를 가진다고 해 봅시다.
덱의 뒤쪽에 새로운 자료를 추가하면 구간이 $[r - k, r']$으로 업데이트되므로, 구간이 $[r' - k, r']$ 가 될 때까지 덱의 앞부터 하나씩 자료를 삭제합니다.
이렇게 $N$개의 자료를 모두 추가 / 삭제한 뒤에는 모든 자료가 한 번씩 추가 / 삭제되고, 각 연산에는 상수 시간이 걸리므로 전체 시간복잡도 $O(N)$에 윈도우를 탐색할 수 있습니다.
목푯값의 계산
슬라이딩 알고리즘의 핵심은 덱의 양쪽에 자료를 추가 / 삭제하는 동시에 목푯값을 업데이트하는 것입니다.
이를 쉽게 지원할 수 있는 연산으로 구간 최솟값, 최댓값 연산이 있습니다.
덱의 앞에서부터 자료의 값이 증가하는 방향으로 자료가 저장되어 있다면, 덱의 맨 앞에서 구간의 최솟값을 가져올 수 있습니다.
이제 윈도우에서 앞쪽 자료를 삭제할 때 최솟값을 갱신해야 합니다.
덱에 저장된 값들은 정렬되어 있기 때문에, 단순히 앞쪽 자료를 삭제하면 새로운 앞쪽 자료가 구간의 최솟값이 됩니다.
다음으로 윈도우 뒤쪽에 자료를 추가할 때를 봅시다.
덱에서 자료의 정렬 순서를 유지하는 방법은 여럿 있겠지만, 위에서 가정한 다음 사항을 고려해야 합니다.
- 덱에 저장된 각 자료로 시작하는 구간에서 그 자료의 값이 구간의 최솟값입니다.
덱의 맨 뒤에 추가할 자료보다 값이 큰 자료가 있다면, 값이 큰 자료로 시작하는 구간에서 새로 추가할 자료가 최솟값이 될 가능성이 있으므로 값이 큰 자료를 삭제합니다.
덱의 맨 뒤에 추가할 자료보다 값이 작은 자료가 있다면, 값이 작은 자료로 시작하는 구간에서 항상 그 자료가 최솟값이므로 유지해야 합니다.
값이 같은 자료의 경우 어떤 선택을 해도 무방합니다.
그러면 모든 윈도우에서의 최솟값을 $O(N)$ 에 구할 수 있고, 같은 방법으로 최댓값도 구할 수 있습니다.
인터랙티브 예시
관련 문제
BOJ 1306 달려라 홍준 - 기초 문제입니다.