Mo's 알고리즘 (모스 알고리즘) 구현해보기 220902
Mo's 알고리즘이란 오프라인 쿼리(= 원소의 업데이트가 없어야 함)를 특정한 순서로 배치하여 효율적으로 처리하는 알고리즘이다.
보통 제곱근 분할법(= 루트 N개의 버킷으로 나누어, 원소들을 버킷 단위로 다루다가 필요할 때 원소 단위로 들어가 값을 다룸)을 활용하여 하나의 쿼리를 O(√N) 시간에 처리할 수 있다는 점에서 특이한 시간 복잡도를 갖는다.
** kks227님의 블로그를 통해 공부하였다. 문제도 거기서 소개한 문제들을 공부했다.
백준 BOJ 11659번 : 구간 합 구하기 (연습용)
문제 난이도 : Silver III
알고리즘 분류 : 누적 합 (..이지만? Mo's 알고리즘으로 풀어보았다.)
굳이 Mo's 알고리즘까지 필요하지는 않지만, 쿼리들을 재배치하여 풀어볼 수 있는 문제라는 점에서 한 번쯤 이런 방식으로 풀어보는 것도 나쁘지 않은 것 같다.
쿼리들의 구간 left, right 값에 따라 sqrt(N) 크기로 쪼개어 정렬하였으므로, 최악의 경우에도 각 쿼리마다 왼쪽 끝을 조정하는데에는 √N번을 넘어가지 않는다.
그리고 오른쪽 끝은 모든 쿼리를 통틀어 N번 이상 이동이 발생하지 않으므로, 둘을 종합해보면 O(M√N + N)이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int S;
struct query { int l, r, n; };
bool cmp(query a, query b) {
if(a.l / S != b.l / S) return a.l / S < b.l / S;
else return a.r < b.r;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
S = sqrt(N);
vector<query> Q(M);
for(int i=0; i<M; i++) {
int a, b; cin >> a >> b;
Q[i].l = a - 1, Q[i].r = b - 1, Q[i].n = i;
}
sort(Q.begin(), Q.end(), cmp);
vector<int> ans(M);
int tmp = 0, l = Q[0].l, r = Q[0].r;
for(int i=l; i<=r; i++) tmp += v[i];
ans[Q[0].n] = tmp;
for(int i=1; i<M; i++) {
while(Q[i].l < l) tmp += v[--l];
while(Q[i].r > r) tmp += v[++r];
while(Q[i].l > l) tmp -= v[l++];
while(Q[i].r < r) tmp -= v[r--];
ans[Q[i].n] = tmp;
}
for(int i=0; i<M; i++) cout << ans[i] << "\n";
}
백준 BOJ 13547번 : 수열과 쿼리 5
문제 난이도 : Platinum II
알고리즘 분류 : 오프라인 쿼리, Mo's
쿼리 a b에 대해 a ~ b 구간 사이의 서로 다른 수의 개수를 구하는 문제이다.
역시 마찬가지로 쿼리를 left / S 값의 오름차순, 그리고 left / S가 동률일 경우 right 값을 오름차순으로 정렬해준다.
첫 쿼리에 대해서는 개수를 일일이 세어서 구해준다.
그 다음 각 쿼리들에 대해서 정렬된 순서대로 구간을 변경하며 각 수들을 count 해주면서 답을 구해주면 된다.
수를 증가시켰는데 원래 0이었으면 수의 종류가 하나 늘어난 것이고, 수를 감소시켰는데 0이 된다면 수의 종류가 하나 감소한 것이다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
int S;
struct query { int l, r, n; };
bool cmp(query a, query b) {
if(a.l / S != b.l / S) return a.l / S < b.l / S;
else return a.r < b.r;
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
S = sqrt(N);
int M; cin >> M;
vector<query> Q(M);
for(int i=0; i<M; i++) {
int a, b; cin >> a >> b;
Q[i].l = a - 1, Q[i].r = b - 1, Q[i].n = i;
}
sort(Q.begin(), Q.end(), cmp);
vector<int> ans(M), cnt(1e6 + 1);
int val = 0, l = Q[0].l, r = Q[0].r;
for(int i=l; i<=r; i++) {
if(cnt[v[i]] == 0) val++;
cnt[v[i]]++;
}
ans[Q[0].n] = val;
for(int i=1; i<M; i++) {
while(Q[i].l < l)
if(cnt[v[--l]]++ == 0) val++;
while(Q[i].r > r)
if(cnt[v[++r]]++ == 0) val++;
while(Q[i].l > l)
if(--cnt[v[l++]] == 0) val--;
while(Q[i].r < r)
if(--cnt[v[r--]] == 0) val--;
ans[Q[i].n] = val;
}
for(int i=0; i<M; i++) cout << ans[i] << "\n";
}
백준 BOJ 2912번 : 백설공주와 난쟁이
문제 난이도 : Platinum II
알고리즘 분류 : 무작위화, 오프라인 쿼리, Mo's
N개의 (10,000 이하의) 수가 주어지고, K개의 쿼리 a b에 대해 a ~ b 구간에서 절반보다 많이 나타나는 수가 있는지 확인하고 그러한 수가 있다면 그것을 구하는 문제이다.
원래 Mo's로 먼저 접근해보려 했는데 구간에 따라 과반수 이상인 수가 바뀌면 갱신을 어떻게 해야할지 모르겠어서 일단 다른 방법으로 푸는 방식을 참고했다.
방법은 이러한데, 먼저 주어진 구간에서 하나의 수를 랜덤으로 고른다.
그 다음 그 수가 구간에서 절반 이상 나왔는지 체크하여 그렇다면 바로 출력해준다.
최악의 경우 어떤 수가 절반에 아주 가까운 과반수라고 하더라도 랜덤으로 뽑았을 때 그 수가 나타날 확률은 1/2보다 많다.
따라서 과반수 이상 존재하는 수가 있음에도 100번 뽑아서 그 수가 나타나지 않을 확률은 (1/2)^100보다 작다.
문제는 어떤 수가 구간에서 절반 이상 나왔는지 빠르게 체크하는 방법인데, 이것은 처음에 배열을 입력받을 때 2차원 벡터에서 해당 수의 주소에 그 수의 주소를 push_back 해준다.
그러면 나중에 어떤 수 x가 l ~ r 구간에서 몇 번 나왔는지 체크할 때, upper_bound(u[x].begin(), u[x].end(), r) - lower_bound(u[x].begin(), u[x].end(), l); 의 방식으로 O(log M) 시간에 확인할 수 있다.
난수 생성은 mt19937, 메르센 트위스터라는 난수 생성기를 이용하여 구현해보았다. (처음 써본다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
mt19937 mt((unsigned int)time(NULL));
uniform_int_distribution<int> uid(0, INT_MAX);
auto rd = bind(uid, mt);
int N, M; cin >> N >> M;
vector<int> v(N+1);
vector<vector<int>> u(M+1);
for(int i=1; i<=N; i++) {
cin >> v[i];
u[v[i]].push_back(i);
}
int K; cin >> K;
while(K--) {
int l, r; cin >> l >> r;
bool check = false;
for(int i=0; i<100; i++) {
int x = v[l + (rd() % (r-l+1))];
int cnt = upper_bound(u[x].begin(), u[x].end(), r) - lower_bound(u[x].begin(), u[x].end(), l);
if(cnt > (r-l+1)/2) {
cout << "yes " << x << "\n";
check = true;
break;
}
}
if(!check) cout << "no\n";
}
}