이 포스팅은 Algorithm Problem Solving 시리즈 113 편 중 17 번째 글 입니다.
목차
플래티넘5 : 슬라이딩 윈도우 문제이다.
생각
N이 500만이라 세그먼트 트리로 풀면 터진다.
- 세그먼트 트리를 만드는데 드는 시간
- nlogn = 대략 22 * 5000000 = 110000000
- 쿼리를 보는데 드는 시간
- nlogn
- 2nlogn
그런데 재귀이기 때문에 간당간당하다. 실제로 재귀로 풀면 터지고 비재귀로 풀면 들어온다고 한다. 해당 문제는 세그먼트 트리보다 간단한 구현을 원하는 듯하다.
문제는 간단하다. N개의 수가 들어왔을 때, L의 윈도우에서 최솟값을 차례대로 구하면 된다. 이 때 문제는, 10개의 원소가 있을 때 L이 3이라 가정하면, 순서대로 이 윈도우에 해당하는 최솟값을 구하면 되는데, 계속해서 다음 윈도우와 겹치는 부분이 발생한다는 것이다. 결국 중복이 발생하고, 이부분에서 오래 걸린다.
문제를 해결하는 방법은 그리디이다. 즉, 윈도우 내에서 최솟값을 구하는 데에는 어떠한 정답이 존재한다.
Sliding Window
input 배열, deque, result 세개의 구조가 필요하다.
위 동영상은 sliding window를 통해 max 값을 찾는 방법을 소개하고 있다. 이 방법의 핵심은 sliding window에서 감소하는 부분 수열을 찾는 것이다. 답은 감소하는 부분 수열에서 나올 수 밖에 없다. 내가 이 수열을 만들 수 있다면, 그 수열에서 가장 첫번째 값이 무조건 답이다.
그렇다면 고민해야 하는 부분은, window가 이동할 때, 어떤식으로 업데이트가 이루어져야 하냐는 점이다. 감소하는 부분 수열을 만들기 위해서 우리가 고려해야 하는 부분은 감소하는 부분 수열의 양단이다.
입력이 8, 6, 2가 들어왔을 때를 생각해보자. 첫번째 window에서 최대 감소 수열을 구하면 위와 같다.
이 상황에서 다음 window로 넘어가는 과정에, 2보다 작은 수가 들어왔다고 생각해보자. 그러면 맨 앞에 있는 8을 빼고, 1을 그냥 뒤에 추가하면 된다. 그리고 이 윈도우에서 최댓값은 여전히 맨 앞에 있는 요소이다.
그런데 같은 상황에서 이번에는 5가 들어왔다고 생각해보자. 그렇다면 이 window에서 최대 감소 수열은 변경된다. 맨 앞에 있는 요소는 여전히 빠지지만, window 내의 감소 수열은 위와 같이 변경되야 한다. 여전히 최댓값은 맨 앞의 요소이다.
Pop을 하는 과정에서 중요한 것이 있다. 무조건적으로 맨 앞에 있는 요소를 빼면 안된다. deq에 들어가 있는 것은 최대 감소수열을 가리키는 index이다. window가 이동하면서 제거되는 index가 deq에 들어가있는 첫번째 요소의 index와 같을 때 deq안의 원소를 지워줘야 한다. 그렇지 않을 경우 해당 요소는 여전히 넘어가는 window안에 있기 때문에 지워지면 안되는 값이다.
결론
- window내에서 최대 감소 수열을 만들었을 때 최댓값은 맨 앞 요소이다.
- window가 이동 할 때, 업데이트 방식이 존재한다.
- 이런 방법을 사용했을 때, 시간 복잡도는 N이다.
이런 방법을 사용하면 결국 한번의 탐색과정과 동시에 모든 윈도우에서 최댓값을 구할 수 있다. 그렇다면 최솟값 찾기에 이 방법을 도입해보자.
Code
#include<iostream>
#include<vector>
#include<algorithm>
#include<list>
#include<cmath>
using namespace std;
typedef long long ll;
int N, L;
vector<int> v;
list<int> deq;
void pop_front(int index){
// 증가하는 수열의 맨 첫번째가 지금 윈도우의 시작점과 같다면 이동하면서 빼준다.
// 만약 아니라면 그 값을 빼주면 안된다!
if (!deq.empty() && deq.front() == index) {
deq.pop_front();
}
}
void push_back(int index){
// 현재 새로들어온 index보다 작은 이전의 녀석들은 증가하는 수열에서 제거해준다.
while (!deq.empty() && v[deq.back()] > v[index]) {
deq.pop_back();
}
deq.push_back(index);
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> N >> L;
v.resize(N+1);
for (int i = 1; i <= N; i++) cin >> v[i];
for (int i = 1; i <= N; i++) {
push_back(i);
cout << v[deq.front()] << ' ';
// 시작할 때 window size보다 작은 index는 pop을 하지않고 넣어준다.
if (i - L >= 0) {
pop_front(i - L + 1);
}
}
}