MITM(Meet-in-the-Middle): n <= 40에 대한 Subset Sum 문제를 위한 방법

기본적인 브루트 포스 방법은 O(2^n)이 걸린다.

그래서, n=20인 경우에만 시간 효율적으로 사용할 수 있다.

 

개선해서, n <=40에서 효율적인, O(2^{n/2})인 방법이 존재한다.

MITM, Meet-in-the-Middle알고리즘이다.

 

n길이의 배열 arr이 주어지고, 합이 s인 부분배열의 개수를 구한다고 해보자.

 

핵심 아이디어는 다음과 같다:

배열을 절반으로 나눠서, 각각 브루트 포스로 모든 조합을 구한다. 각각 left, right라 한다.

이진탐색을 이용할 것이기에, right를 정렬해준다. 

 

left의 조합들에서 각각 right에서  target = s-leftsum값에 대해 upper_bound(target보다 초과인 큰 요소의 첫 인덱스), lower_bound(target이상인 요소의 첫 인덱스)를 구해서 upper_bound - lower_bound를 구해서 총 개수에 누적한다.

즉, 해당 left의 조합에 대응하는 right의 조합이 upper_bound - lower_bound개 있다는 뜻이다.

 

코드 - C++

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

void generateSubsetSums(const vector<int>& arr, vector<int>& subsetSums) {
    int size = arr.size();
    int numSubsets = 1 << size;
    for (int mask = 0; mask < numSubsets; ++mask) {
        int sum = 0;
        for (int i = 0; i < size; ++i) {
            if (mask & (1 << i))  // i번째 요소가 부분 집합에 포함되면
                sum += arr[i];
        }
        subsetSums.push_back(sum);
    }
}

int main() {
    int n, s;
    n = 40, s = 100; // (예시)
	vector<int> arr(n);
    for(int i = 0; i < n; ++i) {
    	arr[i] = i;
    }

    // 배열 나누기
    vector<int> leftArr(arr.begin(), arr.begin() + n / 2);
    vector<int> rightArr(arr.begin() + n / 2, arr.end());

    // 부분 집합 합 계산
    vector<int> leftSums, rightSums;
    generateSubsetSums(leftArr, leftSums);
    generateSubsetSums(rightArr, rightSums);

    // 정렬
    sort(rightSums.begin(), rightSums.end());

    // 이진 탐색으로 대응되는 합 맞춰서 개수 누적
    int ans = 0;
    for (int leftSum : leftSums) {
        int target = s - leftSum;
        ans += upper_bound(rightSums.begin(), rightSums.end(), target) -
               lower_bound(rightSums.begin(), rightSums.end(), target);
    }

    cout << ans << "\n";

    return 0;
}

 

 

https://www.geeksforgeeks.org/meet-in-the-middle/