MITM (Meet in the Middle)

정의

Meet in the Middle (MITM) 은 입력을 절반으로 나누어 각각의 모든 경우를 2^(N/2) 에 열거한 뒤, 두 결과를 합쳐서 정답을 찾는 알고리즘. naive O(2^N) 을 O(2^(N/2)) 로 줄인다.

PS 에서는 N ≤ 40 정도의 완전 탐색 / 부분 수열 합 문제에서 가장 자주 등장한다.

문제 상황과 동기

크기 N 인 집합에서 조건을 만족하는 부분집합을 찾아야 한다. 완전 탐색 O(2^N) 은 N=40 에서 약 1조 가지로 불가능.

• naive: 모든 부분집합 탐색. O(2^N).
• MITM: N 을 N/2 + N/2 로 분할, 각각 열거 (2^(N/2) + 2^(N/2)) 후 이분 탐색으로 합병. O(2^(N/2) log 2^(N/2)).

N=40 이면 2^40 = 1.1 x 10^12 이지만, 2^20 = 1,048,576 으로 충분히 실용적.

핵심 통찰: 큰 문제를 반으로 쪼개고, 각 절반의 모든 상태를 나열한 뒤 적절히 조합하면 중복 계산을 피할 수 있다.

시각화

핵심 아이디어

invariant: 전체 해 = 왼쪽 절반의 어떤 부분집합 + 오른쪽 절반의 어떤 부분집합. 두 반쪽이 독립적이므로 각각 열거 후 합성.

solve(arr, N, target):
    left = arr[0..N/2-1]
    right = arr[N/2..N-1]

    left_sums = 모든 부분집합 합   // 2^(N/2) 개
    right_sums = 모든 부분집합 합  // 2^(N/2) 개

    right_sums.sort()

    ans = 0
    for sumL in left_sums:
        ans += count(right_sums, target - sumL)

    return ans

알고리즘

meet_in_the_middle(arr, N, K):
    L = arr[:N//2], R = arr[N//2:]

    function enumerate(A):
        res = []
        for mask in 0..(1<<len(A))-1:
            sum = 0
            for i in 0..len(A)-1:
                if mask & (1<<i): sum += A[i]
            res.push(sum)
        return res

    left_sums = enumerate(L)
    right_sums = enumerate(R)
    right_sums.sort()

    count = 0
    for s in left_sums:
        // K - s 가 right_sums 에 몇 개 있는지
        count += upper_bound(right_sums, K - s)
              - lower_bound(right_sums, K - s)

    return count

구현

// BOJ 1208: 부분수열의 합 2 (MITM)
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
​
int main() {
  int n, k; cin >> n >> k;
  vector<int> a(n);
  for (auto& v : a) cin >> v;
​
  int mid = n / 2;
  vector<int> left(a.begin(), a.begin() + mid);
  vector<int> right(a.begin() + mid, a.end());
​
  auto gen = [](const vector<int>& v) {
      vector<ll> res;
      int m = v.size();
      for (int mask = 0; mask < (1 << m); mask++) {
          ll sum = 0;
          for (int i = 0; i < m; i++)
              if (mask & (1 << i)) sum += v[i];
          res.push_back(sum);
      }
      return res;
  };
​
  vector<ll> L = gen(left), R = gen(right);
  sort(R.begin(), R.end());
​
  ll ans = 0;
  for (ll s : L) {
      auto [lo, hi] = equal_range(R.begin(), R.end(), k - s);
      ans += hi - lo;
  }
​
  if (k == 0) ans--;  // 공집합 제외
  cout << ans << "\n";
}

# BOJ 1208: 부분수열의 합 2 (MITM)
import sys
from bisect import bisect_left, bisect_right
input = sys.stdin.readline
​
n, k = map(int, input().split())
a = list(map(int, input().split()))
mid = n // 2
​
def gen(v):
  res = []
  m = len(v)
  for mask in range(1 << m):
      s = 0
      for i in range(m):
          if mask & (1 << i):
              s += v[i]
      res.append(s)
  return res
​
L = gen(a[:mid])
R = gen(a[mid:])
R.sort()
​
ans = 0
for s in L:
  target = k - s
  ans += bisect_right(R, target) - bisect_left(R, target)
​
if k == 0:
  ans -= 1
print(ans)

5 0
-7 -3 -2 5 8

1

4 3
1 2 2 3

3

복잡도

변형 / 활용

함정

1. 공집합 처리

k=0 일 때 왼쪽/오른쪽 모두 공집합(합=0) 을 포함하고, 0+0=0 이 카운트되는데 이는 문제에서 요구하지 않을 수 있다 (공집합 제외). ans-- 처리 필요.

2. 정렬 후 이분 탐색

right_sums 를 정렬한 후 left_sums 의 각 값에 대해 target - s 의 개수를 upper_bound - lower_bound 로 센다. unordered_map 도 가능하지만 충돌 / 시간 차이 고려.

3. N 이 홀수일 때

절반 분할은 mid = N//2 로 한 쪽이 1개 더 많아도 된다. 열거 크기는 각각 2^(floor(N/2)) 와 2^(ceil(N/2)). 최대 차이는 2 배라 O(2^(N/2)) 에 흡수.

4. 정수 오버플로우

부분집합 합이 int 범위를 넘을 수 있다. C++ 에서는 long long 사용. K 도 마찬가지.

BOJ 연습 문제

참고

• 양방향 탐색
• 이분 탐색
• 두 포인터
• 냅색 DP