Meet in the middle (MITM)

Meet in the middle 

Meet in the middle 은 브루트포스 알고리즘을 사용해야 하지만 경우의 수가 브루트포스 알고리즘을 사용하기에 조금 클 때 사용 된다.

즉 브루트포스 알고리즘을 사용하되 이를 분할 해서 연산의 수를 최소화 하는 것이다.

예를 들면 N크기 배열 원소의 모든 조합을 고려해야 하는 문제가 있다고 하자.

이때 N이 20이라면 2^20(약 100만)개의 연산을 하면 된다.

하지만 만약 N이 40이라면 2^40 개의 연산을 수행하므로 초당 연산 수 1억번 이내에서 해결이 어렵다.

이때 MITM 알고리즘을 사용하게 되는데~

MITM 은 분할 정복과 비슷한 형태를 취하지만 분할정복은 작은 문제 해결을 통해 커다란 하나의 문제를 해결하는 반면~

MITM은 작은 문제 해결 + 알파의 연산이 필수적이다.

 

백준 https://www.acmicpc.net/problem/1208 문제를 해결 하면서 알고리즘을 이해해 보자.

5 0
-7 -3 -2 5 8

에서 부분 합이 0이 되는 경우의 수를 해결하는 문제이다.

즉 -3 + -2 + 5 = 0 이 되는 경우 한가지가 있다.

 

이 문제는 N <=  40 개의 수로 이루어진 집합이 주어졌을 때 원소의 합이 S가 되는 부분집합의 개수를 구해야 하는 문제이다.

 

가장 간단한 해법은 각각의 원소를 선택/선택안함 과 같이 모든 경우를 다 세어 주면 되지만 이 경우 2^40 이므로 시간초과가 발생한다.

 

이 상황에서 mitm 알고리즘으로 어떻게 개선하는지 살펴 보자.

 

우선 집합을 N/2 개씩 두개의 집합으로 분리해 보자.

편의상 A집합 과 B 집합으로 나눈다.

A 집합 {-7,-3,-2}, B집합 {5,8} 이라고 하면 이 부분 집합의 원소의 합들을 모두 계산하여 각각의 합이 몇번씩 나오는지를 미리 계산해 두자.

Asum = {0,-7,-3,-2,-10,-5,-9,-12} Bsum={0,5,8,13}

에서 각각의 수는 1회씩 나온다.

이 배열을 cnt라고 하면 이 과정을 수행한 결과 cnti 에는 원소의 합이 i인 부분집합의 개수가 저장 되어 있다.

 

Acnt[-12]=1(여기서 -12번지는 없지만 이해를 돕기 위해 그냥 -12로 표기한다.)

Acnt[-10]=1,Acnt[-9]=1,Acnt[-7]=1,Acnt[-5]=1,Acnt[-3]=1,Acnt[-2]=1,Acnt[0] = 1

 

이부분의 시간 복잡도는 O(2^N/2)이다.

 

이제 이 문제는 다음과 같이 바뀐다.

A의 원소와 B의 원소의 합이 S인 경우는 몇가지 인가?

이 부분은 정렬 후에 이분탐색이나 혹은 투포인터를 사용하는 등의 방법으로 해결 할 수 있다.

 

그렇다면 위의 문제를 풀어 보자.

 

#include <bits/stdc++.h>
using namespace std;


long long n, s;
long long a[41];
vector <long long> lv, rv;

void DFS(int s, int e, long long sum, vector<long long>& v)
{
    if (s >= e)
    {
        v.push_back(sum);
        return;
    }

    DFS(s + 1, e, sum, v); ///s 위치를 선택 하지 않고 진행
    DFS(s + 1, e, sum + a[s], v); ///s 위치를 선택 하고 진행
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(0);

    cin >> n >> s;
    for (int i = 0; i < n; i++) cin >> a[i];

    DFS(0, n/2, 0, lv);
    DFS(n/2, n, 0, rv);

    sort(lv.begin(), lv.end());
    sort(rv.begin(), rv.end());

    long long ans = 0;
    for (long long x : lv) ans += upper_bound(rv.begin(), rv.end(), s - x)- lower_bound(rv.begin(), rv.end(), s - x);

    if (s == 0) ans--; ///s==0 인 경우는 왼쪽 0, 오른쪽 0 의 갯수가 하나 포함 되어 있는데 이것은 아무것도 선택하지 않은 경우이므로 빼 주어야 한다.

    cout << ans;
}

 

 

 

 

Meet in the middle 문제집

 

https://www.acmicpc.net/workbook/view/2112

문제집: Meet in the Middle (kks227)

 

 

참고]

https://anz1217.tistory.com/127