자료구조 덱(Deque)의 활용 (feat. Priority Queue)

덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 $A_1, A_2,..., A_N$이 주어질 때 임의의 상수 B에 대해 $A_{i-B}$ ~ $A_i$ 의 최대, 최소 같이 데이터를 가진 정보들을 특정한 기준에 따라 나열할 때 가장 우선순위가 높은 값을 모든 i에 대해 시간 복잡도 O(N)으로 찾아줄 수 있다. 

 

위와 같은 상황에서 A라는 배열의 각 원소에 $V_i$라는 우선순위가 주어져 있다고 하자. 우리는 덱에 다음과 같은 성질을 만족시키도록 자료들을 넣고 뺄 것이다. 

성질 : $I_i$를 덱의 앞에서부터 i번째에 있는 원소가 가지는 배열 A에서의 인덱스라고 했을 때, i<j에 대해 $I_i <I_j$와 $V_{I_i}>V_{I_j}$가 항상 성립한다.

일단 B를 무시하고 예를 들자면, 배열 A가 1 4 12 5 7 1 6 3 2$...$ 같이 되어있을때 최댓값을 찾는다고 하면 원소 2까지는 덱에 12 7 6 3 2와 같이 저장되어 있어야 한다. 덱 원소들의 I값은 3 5 7 8 9 이 되고 B값에 따라 앞 원소가 pop 될 수도 있다.

성질을 만족시키려면 for문을 A의 원소 1번부터~N번까지 돌리면서 매 반복마다 다음 작업을 수행한다. 

(1) A[i] 값과 덱의 끝 원소를 비교하면서 덱의 마지막 원소의 우선순위가 높아질 때까지 덱의 뒤 원소를 뺀다.

(이걸로 덱이 성질을 만족하도록 한다.)

(2) A[i]를 덱의 마지막에 넣는다.

(3) 덱의 앞에서 현재 포문의 i값과 덱의 맨 앞 원소의 I값을 비교해 차이가 B이하가 될 때까지 덱의 앞에서 원소를 뺀다. 그리고 그때 덱의 맨 앞 원소가 $A_{i-B}$ ~ $A_i$ 중 우선순위가 높은 값이된다. 

 

Ex) 배열 A 1 4 12 5 7 1 6 까지 B가 3일 때, 최댓값을 찾는 과정을 해보면 

i=1 : 1

i=2 : 4 (1은 작으므로 pop back)

i=3 : 12 (4는 12보다 작으므로 pop back)

i=4 : 12 5  

i=5 : 12 7 (5는 7보다 작으므로 pop_back)

i=6 : 12 7 1 

i=7 : 7 6 (12는 i-I가 3초과이므로 pop front, 1은 6보다 작으므로 pop back)

 

 

이해를 했는지 확인하기 위해 가장 간단한 문제로 11003번 최솟값 찾기 https://www.acmicpc.net/problem/11003 가 있다.

 

소스 코드(최솟값 찾기)

#include <iostream>
#include <deque>
#include <algorithm>
 
using namespace std;
 
int n,l;
deque<pair<int,int> > arr;
pair<int,int> cand;
 
int main()
{
    int in;
    std::ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>l;
    for(int i=0;i<n;i++)
    {
        cin>>in;cand=make_pair(i,in);
        while(!arr.empty()&&arr.back().second>=in)    arr.pop_back();
        arr.push_back(cand);
        if(arr.front().first<=(i-l))    arr.pop_front();
        cout<<arr.front().second<<" ";
    }
    return 0;
}

 

또, 위 원리를 조금 확장해 deque dp 같이 다음 문제들을 풀 수 있다.

 

15678번 연세워터파크 https://www.acmicpc.net/problem/15678 

 

풀이 : 덱에서 최댓값을 유지하며 매 순회마다 최댓값을 갱신해주면 된다. (왜 이게 최댓값을 항상 찾을 수 있는지는 성질과 연결해서 생각해보면 된다.)

 

소스 코드(연세워터파크)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,int> pli;
 
ll n,d,a,now,ans=-1e9;
deque<pli> deq;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>d;
    deq.push_back(pli(0,0));
    for(int i=1;i<=n;i++)
    {
        cin>>a;
        while(!deq.empty()&&deq.front().second+d<i) deq.pop_front();
        now=max(a,a+deq.front().first);
        ans=max(ans,now);
        while(!deq.empty()&&deq.back().first<=now) deq.pop_back();
        deq.push_back(pli(now,i));
    }
    cout<<ans;
    return 0;
}

 

5977번 Mowing the Lawn https://www.acmicpc.net/problem/5977

 

풀이 : 약간의 생각의 전환?을 요구하는 문제이다.(나만 그렇게 느끼나...) 먼저, 주어진 모든 값을 더하고 덱으로 구한 최솟값을 빼서 답을 구하는 문제이다. 즉, 선택하는 소들을 구하는 게 아니라 선택하지 않는 소들의 합을 최소로 하여 구하는 것이다. 최솟값을 구할 때, 덱에서 처리해주는 소들의 인덱스 차이가 k+1 이하라면 소들을 연속해서 k마리 이하로 고르는 것과 같기 때문에 문제 조건을 만족시킨다. 또, 여기서 dp배열을 연세워터파크 문제와는 다르게 만들어주어야 하는 이유는 구하는 최솟값이 어떤 위치에서나 다 가능한 게 아니라 마지막 n-k ~ n 구간에서만 가능하기 때문이다. (난 아래 소스코드에서 덱으로 처리해줄 값에 바로 -부호를 붙이고 그것의 최댓값을 구해 총합에다가 더해주었다. 이건 자기 편한 대로 하면 될 것 같다.)

 

소스 코드(Mowing the Lawn)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
 
ll n,k,anw=-1,sum;
vector<ll> ar;
deque<pair<ll,ll> > dq;
ll dp[100004];
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    for(int i=0;i<n;i++)
    {
        ll a;cin>>a;
        ar.push_back(a);
        sum+=a;
    }
    dq.push_back({0,0});
    for(int i=1;i<=n;i++)
    {
        while(!dq.empty()&&i-1-dq.front().first>k)    dq.pop_front();
        dp[i]=dq.front().second-ar[i-1];
        while(!dq.empty()&&dq.back().second<dp[i])    dq.pop_back();
        dq.push_back({i,dp[i]});
    }
    for(int i=n-k;i<=n;i++)
        anw=max(sum+dp[i],anw);
    cout<<anw;
    return 0;
}

 

Priority queue(우선순위 큐)

또, 재미있는 점은 대부분의 deque 문제들은 deque를 이용하지 않고 priority queue로도 풀이가 가능하다. 물론, 시간 복잡도는 O(nlogn)이 되지만 보통은 시간 초과 없이 무난하게 문제를 해결할 수 있다. 원리는 deque와 같다. 매 포문마다 해당 원소를 priority queue에 넣고 인덱스 값을 for문의 i값과 비교하여 일정 상수보다 작을 때까지 pop 하면서 최댓값을 갱신해주면 된다. 

 

소스 코드(연세워터파크, 우선순위 큐 버전)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
priority_queue<pair<ll,ll> > pq;
ll n,d,dp[100054],anw=-1e10;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>d;
    pq.push({-1e10,0});
    for(int i=1;i<=n;i++)
    {
        ll a;cin>>a;
        while(i-pq.top().second>d) pq.pop();
         dp[i]=max(a,pq.top().first+a);
        pq.push({dp[i],i});
    }
    for(int i=1;i<=n;i++)
        anw=max(anw,dp[i]);
    cout<<anw;
    return 0;
}

 

소스 코드(Mowing the Lawn, 우선순위 큐 버전)

#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<ll,ll> pi;
 
priority_queue<pi> pq;
ll n,k,dp[100054],anw=-1e15,sum;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin>>n>>k;
    pq.push(pi(0,0));
    for(int i=1;i<=n;i++)
    {
        ll a;cin>>a;
        sum+=a;
        while(i-1-pq.top().second>k) pq.pop();
         dp[i]=pq.top().first-a;
        pq.push(pi(dp[i],i));
    }
    for(int i=n-k;i<=n;i++)
        anw=max(anw,dp[i]);
    cout<<sum+anw;
    return 0;
}