덱은 앞뒤에서 빼고 넣을 수 있는 자료구조로, 처음 배울 때는 왜 배우지... 이거 과연 쓸데가 있을까?라고 생각했다. 하지만 이 자료구조를 이용하면 \(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 가 있다.
소스 코드(최솟값 찾기)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
#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
풀이 : 덱에서 최댓값을 유지하며 매 순회마다 최댓값을 갱신해주면 된다. (왜 이게 최댓값을 항상 찾을 수 있는지는 성질과 연결해서 생각해보면 된다.)
소스 코드(연세워터파크)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
|
#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)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
|
#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 하면서 최댓값을 갱신해주면 된다.
소스 코드(연세워터파크, 우선순위 큐 버전)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
#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;
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, 우선순위 큐 버전)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
#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;
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;
}
|
|