Meet in the middle (MITM)에 대해 알아봅시다.
https://www.acmicpc.net/problem/1208
1208번: 부분수열의 합 2
첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
www.acmicpc.net
길이가 최대 40인 수열이 주어지고, 이 수열의 부분수열 중 원소의 합이 \(S\)인 것의 개수를 구해야 합니다.
이를 나이브하게 브루트 포스로 구하려면 \(O(2^n)\)의 시간복잡도를 가지게 되고, 이는 \(n\)이 최대 40이므로 너무 느립니다.
하지만, 수열을 반으로 나눠서 생각해 보면 어떨까요?
수열의 앞 절반에서 나올 수 있는 모든 부분수열의 원소의 합을 구해 저장해 놓고, 이를 A라고 합시다.
역시 수열의 뒤 절반에서 나올 수 있는 모든 부분수열의 원소의 합을 구해 이를 B라고 합시다.
A와 B 각각 \(O(2^{\frac n2})\)개의 원소를 가지고 있을 것입니다.
이제 문제는 다음과 같이 바뀝니다.
"A의 원소와 B의 원소의 합이 \(S\)인 경우의 수는 몇 가지인가?"
이는 적절한 자료구조를 사용하거나, 정렬해서 이분탐색을 하거나, 투 포인터를 사용하는 등 다양한 방법을 사용하여 풀 수 있으므로,
총 시간복잡도 \(O(2^{\frac n2})\) 또는 \(O(n \cdot 2^{\frac n2})\)로 풀린다는 사실을 알 수 있습니다.
이렇듯 문제를 절반 크기의 2개로 나눠 각각 해결하고, 중간에서 만나 큰 문제를 해결하는 방식이 바로 MITM입니다.
|
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
36
37
38
39
40
41
42
43
44
45
46
47
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll n, s;
ll a[41];
vector <ll> lw, rw;
void DFS(int idx, int midx, ll sum, vector<ll>& v)
{
if (idx >= midx)
{
v.push_back(sum);
return;
}
DFS(idx + 1, midx, sum, v);
DFS(idx + 1, midx, sum + a[idx], v);
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> s;
for (int i = 0; i < n; i++) cin >> a[i];
DFS(0, min(20ll, n), 0, lw);
DFS(20, n, 0, rw);
sort(lw.begin(), lw.end());
sort(rw.begin(), rw.end());
ll ans = 0;
for (ll x : lw) ans += upper_bound(rw.begin(), rw.end(), s - x)
- lower_bound(rw.begin(), rw.end(), s - x);
if (s == 0) ans--;
cout << ans;
}
|
cs |
https://www.acmicpc.net/problem/4357
4357번: 이산 로그
소수 P(2 ≤ P < 231), 정수 B(2 ≤ B < P), 정수 N(1 ≤ N < P)가 주어졌을 때, 밑을 B, 나머지를 P로 하는 N의 이산 로그를 구하는 프로그램을 작성하시오. 즉, 다음과 같은 조건을 만족하는 정수 L을 찾으
www.acmicpc.net
MITM으로 풀리는 대표적인 문제가 하나가 바로 이산 로그 문제 입니다.
\(a^x = b \pmod p\)를 만족하는 \(x\)를 찾아 봅시다. (\(p\)는 소수)
먼저, \(a^x \pmod p\)는 주기를 가지며, 그 주기는 최대 \(p\)라는 사실은 자명합니다.
\(\sqrt p = k\)일 때, \(x = nk + m\)의 형태로 나타낼 수 있습니다.
따라서,
$$a^{nk} \cdot a^{m} = b \pmod p$$
로 나타낼 수 있고,
$$a^{nk} = b \cdot a^{-m} \pmod p$$
를 만족하는 \(n, m\)을 찾으면 이산 로그를 구할 수 있게 됩니다.
\(n\)과 \(m\) 모두 \(k\)보다 작거나 같으므로, 시간복잡도 \(O(\sqrt p)\)에 이산 로그를 구할 수 있습니다.
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
|
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
ll mpow(ll a, ll n, ll p)
{
if (n == 0) return 1;
ll res = mpow(a, n / 2, p);
res = res * res % p;
if (n % 2) res = res * a % p;
return res;
}
map <ll, ll> mp;
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
ll a, b, p;
while (cin >> p >> a >> b)
{
mp.clear();
ll k = sqrt(p);
ll inv_a = mpow(a, p - 2, p);
ll ak = mpow(a, k, p);
ll cur = b;
for (int i = 0; i < k; i++)
{
mp[cur] = i;
cur = cur * inv_a % p;
}
bool hasAns = false;
cur = 1;
for (int i = 0; i <= k; i++)
{
if (mp.find(cur) != mp.end())
{
cout << i * k + mp[cur] << '\n';
hasAns = true;
break;
}
cur = cur * ak % p;
}
if (!hasAns) cout << "no solution\n";
}
}
|
cs |
위에서 \(n\)을 \(\sqrt n\) 2개로 쪼개어 문제를 해결해 봤는데, 이 루트를 조금 더 일반적으로도 써먹을 수 있는 방법이 있습니다.
일반적으로 \(O(n)\)의 시간복잡도가 필요한 작업을 \(\sqrt n\)개의 작은 문제로 나눠서 풂으로써 \(O(\sqrt n)\)에 해결할 수 있는 제곱근 분할법 (sqrt Decomposition)에 대해 알아봅시다.
https://www.acmicpc.net/problem/2042
2042번: 구간 합 구하기
첫째 줄에 수의 개수 N(1 ≤ N ≤ 1,000,000)과 M(1 ≤ M ≤ 10,000), K(1 ≤ K ≤ 10,000) 가 주어진다. M은 수의 변경이 일어나는 횟수이고, K는 구간의 합을 구하는 횟수이다. 그리고 둘째 줄부터 N+1번째 줄
www.acmicpc.net
세그먼트 트리를 이용해 쿼리당 \(O(\log n)\)에 처리할 수도 있지만,
제곱근 분할법을 이용해 쿼리당 \(O(\sqrt n)\)에 해결해 봅시다.
수열을 \(\sqrt n\)개의 버킷으로 분할합시다.
각 버킷은 역시 \(\sqrt n\)개의 원소를 가집니다.
그리고 각 버킷에 속한 모든 원소의 합을 따로 저장합시다.
이 상태로 배열을 유지한다고 가정하고, 각 쿼리의 시간복잡도를 계산해 봅시다.
먼저 값 갱신입니다.
위의 그림에서 5번째 원소인 2를 7로 바꾼다고 생각해 봅시다.
실제 원소와 구간의 합, 두 값만을 갱신하면 되므로, 값 갱신의 복잡도는 \(O(1)\)입니다.
다음은 구간 합 쿼리입니다.
위의 그림에서 2번째부터 7번째 원소까지의 구간 합을 구해야 된다고 생각해 봅시다.
이 때, 2가지 경우로 나눠 생각할 수 있습니다.
1. 구간 안에 버킷이 완전히 포함된다
→ 미리 구해놓은 버킷의 합을 사용하면 됩니다.
2. 버킷에 구간의 끝이 걸친다.
→ 걸치는 만큼 원소를 직접 하나하나 더해주면 됩니다.
1번의 경우, 버킷의 개수가 많아도 \(\sqrt n\)개이므로, 시간복잡도는 \(O(\sqrt n)\)입니다.
2번의 경우, 최악의 경우 양 끝이 각각 버킷에 걸치면서 걸치는 원소의 개수가 각각 \(\sqrt n\)개일 수 있습니다.
따라서 최대 \(2 \sqrt n\)개의 원소를 직접 더하게 되고, 시간복잡도는 역시 \(O(\sqrt n)\)입니다.
따라서 이렇게 단순한 방법으로 구간 합 쿼리를 \(O(\sqrt n)\)에 해결할 수 있게 됩니다!
|
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
|
#include <iostream>
using namespace std;
const int N = 1000001;
const int BK = 1001;
int n, m, k;
long long a[N];
long long bucket[BK];
int getBucketIdx(int idx)
{
return (idx - 1) / BK + 1;
}
void init()
{
for (int i = 1; i <= n; i++)
{
int bidx = getBucketIdx(i);
bucket[bidx] += a[i];
}
}
long long getSum(int l, int r)
{
int bidxl = getBucketIdx(l);
int bidxr = getBucketIdx(r);
if (bidxl == bidxr)
{
long long result = 0;
for (int i = l; i <= r; i++) result += a[i];
return result;
}
long long result = 0;
for (int i = l; getBucketIdx(i) == bidxl; i++)
result += a[i];
for (int i = r; getBucketIdx(i) == bidxr; i--)
result += a[i];
for (int i = bidxl + 1; i <= bidxr - 1; i++)
result += bucket[i];
return result;
}
void update(int idx, long long val)
{
int bidx = getBucketIdx(idx);
bucket[bidx] -= a[idx];
a[idx] = val;
bucket[bidx] += a[idx];
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
init();
for (int i = 0; i < m + k; i++)
{
int a; cin >> a;
if (a == 1)
{
int b; long long c;
cin >> b >> c;
update(b, c);
}
else
{
int l, r; cin >> l >> r;
cout << getSum(l, r) << '\n';
}
}
}
|
cs |
제곱근 분할법은 이런 1차원 배열에서 뿐만 아니라 2차원 배열, 심지어 트리에서도 사용할 수 있습니다.
(차수가 \(\sqrt n\)이상인 정점이 \(\sqrt n\)개 이하라는 것을 이용하는 방법 등)
어려운 문제를 봤을 때 푸는 방법을 잘 모르겠다면, 제곱근 분할법을 이용해 루트 시간복잡도로 한번 "비벼"보는 것도 나쁘지 않은 선택입니다.
제 그룹의 문제집에서 연습 문제들을 관리하고 있습니다.
문제집의 문제들을 보고 싶으시다면, 가입 신청을 해 주세요.
+ 요즘 많이 가입 신청이 들어오고 있습니다만, 꼭 그룹에 가입하셔서 제 문제들을 푸실 필요는 없습니다.
solved.ac 에서 태그를 찾아 푸시거나 백준 단계별로 풀기 에서 문제를 찾아 푸셔도 충분합니다!
그룹은 단순히 제 개인용 알고리즘 문제집 정리 용도이니 참고해주세요!
https://www.acmicpc.net/group/7712
ANZ1217
무슨 내용을 넣어야 좋을까요?
www.acmicpc.net
