icpc.me 11003 - CyberFlower Algorithm

https://www.acmicpc.net/problem/11003

최솟값 찾기 문제에서는 5,000,000개의 원소들에 대해서 구간(창의 크기가 5,000,000)개이므로 O(NN)이나 O(ND)로는 해결이 어렵다.

따라서 이 문제 해결을 위해서는 슬라이딩 윈도우 알고리즘을 사용한다. 보통 슬라이딩 윈도우 알고리즘이라 하면 두개의 포인터를 이용하여 해결하는 경우가 많지만, 적절한 자료구조를 사용하면 코드 이해가 편해지고 깔끔해지는 경우가 있다.

대략적인 알고리즘은 다음과 같다

자료구조는 deque을 사용하면 이 문제에 한해서 편리하다.
deque에는 {원소, index}가 들어가며 원소는 오름차순으로 들어간다.
deque front에 원소들 중 창(window)에 속하지 못하는 index들은 모두 뽑아낸다.
deque back에 원소들 중 새로 추가되는 원소보다 큰 원소는 모두 뽑아낸다.
{arr[i],i} 원소를 추가한다.
남아있는 원소들 중에서 가장 앞에 있는 원소가 구간의 최솟값이다.

코드를 보고 복잡도를 분석해보자.

#include<bits/stdc++.h>
using namespace std;
deque<pair<int,int> > dq;
int main(void){
  ios::sync_with_stdio(false); cin.tie(NULL);
  int n,l; cin>>n>>l;
  for(int i=1;i<=n;i++){
    int x; cin>>x;
    while(!dq.empty() && dq.front().second<=i-l){
      dq.pop_front();
    }
    while(!dq.empty() && dq.back().first>=x){
      dq.pop_back();
    }
    dq.push({x,i});
    cout<<dq.front().first<<" ";
  }
  return 0;
}

코드는 간단하군요… 복잡도를 계산하기 위해 deque에 들어가는 원소의 입장이 되어보겠습니다. 원소는 2가지 일을 수행합니다. deque에 들어가거나, 나가거나. 모든 원소가 deque에 들어가거나 나오기 때문에 복잡도는 O(c*n), 즉 O(n)이 되는군요!

백준 11003 최솟값 찾기