17. 슬라이딩 윈도우 (Sliding window, c++)

슬라이딩 윈도우 (Sliding window)?

슬라이딩 윈도우는 고정 크기의 부분배열을 배열의 왼쪽에서 오른쪽으로 이동시키는 방법입니다.

 

슬라이딩 윈도우의 각 위치에서 부분 배열에 대한 정보들을 계산할 수 있습니다.

 

특정 길이(슬라이딩 윈도우의 크기)가 주어지고  배열의 모든 특정 길이의 부분배열에 대해 그 배열에서의 가장 작은 값을 구하는 문제가 있습니다.

 

예를 들어 { 2, 1, 4, 5, 3, 4 } 라는 배열이 있고 슬라이딩 윈도우의 크기가 3라면 { 2, 1, 4 } 의 최소값, { 1, 4, 5 }의 최소값...을 계산해야 합니다.

 

이 문제는 Nearest smaller elements와 유사한 접근방식을 사용해 해결할 수 있습니다.

 

이번에도 왼쪽에서 오른쪽으로 탐색을 하고 Deque를 사용해 특정 요소들을 관리할 것입니다.

 

Deque는 Front와 Back 양쪽으로 삽입, 삭제가 O(1)에 가능한 자료구조입니다.

 

Deque의 요소들은 왼쪽에 있는 값이 항상 오른쪽 값보다 작습니다.

 

매번 슬라이딩 윈도우가 움직일 때 마다 Front에서는 슬라이딩 윈도우의 범위에 벗어난 값들을 제거합니다.

 

Back에서는 새로 윈도우에 추가될 값보다 큰 값들은 제거합니다.

 

왜냐하면 앞으로 고정 크기의 슬라이딩 윈도우에서 그 값들은 최소값이 될 가능성이 없기 때문입니다.

 

Deque가 비거나 Back에 현재 값보다 작은 값이 발견된다면 제거하는 작업을 중단합니다.

 

그리고 현재 탐색중인 값을 윈도우에 추가합니다.

 

이 때, Front에 위치한 값이 슬라이딩 윈도우에서의 최소값이 됩니다.

 

배열의 요소 { 2, 1, 4, 5, 3, 4 }, 구간의 길이 3을 예로 들면 아래와 같습니다.

Deque(before)	index	value	sliding window minimum	deque(after)
{ }	1	2	2	{ 2 }
{ 2 }	2	1	1	{ 1 }
{ 1 }	3	4	1	{ 1, 4 }
{ 1, 4 }	4	5	1	{ 1, 4, 5 }
{ 1, 4, 5 }	5	3	3	{ 3 }
{ 3 }	6	4	3	{ 3, 4 }

 

이 방식은 배열의 모든 요소를 정확히 한번씩 탐색하므로 O(N)에 수행됩니다.