Meet In The Middle

MITM 알고리즘

주어진 문제를 절반으로 나누어서 부분 문제를 해결한 다음에 결과를 조합하여서 전체를 해결하는 알고리즘을 의미한다.

예를 들어서 브루트 포스 알고리즘을 사용할 때 완전 탐색을 한다면 시간 복잡도가 O(2^N)이지만 Meet In The Middle을 활용하면 O(2^(N/2))로 줄일 수 있다!

활용해 보기

1. 문제를 절반으로 나눈다!.

• N/2인 두 개의 부분으로 나눈다.

2. 각각의 부분을 알고리즘을 활용하여 해결한다.

• 각각의 부분의 경우의 수를 구해주고 저장해 준다.

3. 두 부분을 합쳐서 문제를 해결한다.

• 이분탐색 혹은 정렬 등을 활용하여서 빠르게 조합을 찾아낸다.

예시(배냥 문제)

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

// (무게, 가치) 리스트에서 가능한 모든 부분집합을 생성하는 함수
vector<pair<ll, ll>> getSubsets(vector<pair<int, int>> items) {
    int n = items.size();
    vector<pair<ll, ll>> subsets;

    // 부분집합 생성 (브루트포스)
    for (int i = 0; i < (1 << n); i++) {
        ll weight = 0, value = 0;
        for (int j = 0; j < n; j++) {
            if (i & (1 << j)) { // j번째 아이템을 포함하는 경우
                weight += items[j].first;
                value += items[j].second;
            }
        }
        subsets.push_back({ weight, value });
    }

    return subsets;
}

// Meet in the Middle을 활용한 배낭 문제 해결
ll MITM(int W, vector<pair<int, int>>& items) {
    int n = items.size();

    // 1. 왼쪽과 오른쪽으로 나누기
    vector<pair<int, int>> leftItems(items.begin(), items.begin() + n / 2);
    vector<pair<int, int>> rightItems(items.begin() + n / 2, items.end());

    // 2. 각 부분에서 가능한 부분집합 (무게, 가치) 계산
    vector<pair<long long, long long>> leftSubsets = getSubsets(leftItems);
    vector<pair<long long, long long>> rightSubsets = getSubsets(rightItems);

    // 3. 오른쪽 부분집합을 무게 기준으로 정렬
    sort(rightSubsets.begin(), rightSubsets.end());

    // 4. 같은 무게일 때 최대 가치만 뽑아주기기
    vector<pair<long long, long long>> filteredRight;
    long long max_value = 0;
    for (auto [w, v] : rightSubsets) {
        if (filteredRight.empty() || v > max_value) {
            filteredRight.push_back({ w, v });
            max_value = v;
        }
    }

    // 5. 왼쪽 부분집합을 하나씩 확인하며, 오른쪽 부분집합에서 최적 선택 (이진 탐색 활용)
    ll best_value = 0;
    for (auto [wL, vL] : leftSubsets) {
        if (wL > W) continue;

        // 이진 탐색: W - wL 이하의 최대 가치를 가진 부분집합 찾기
        auto it = upper_bound(filteredRight.begin(), filteredRight.end(), make_pair(W - wL, LLONG_MAX));
        if (it != filteredRight.begin()) { 
            --it; //upper_bound는 W-wL보다 큰 첫 번째 요소이기에 이전 요소를 가져와야한다!
            best_value = max(best_value, vL + it->second); //update!
        }
    }

    return best_value;
}

int main() {
    int N = 4, W = 10;
    vector<pair<int, int>> items = { {3, 6}, {2, 4}, {4, 5}, {5, 7} }; // (무게, 가치)

    cout << "최대 가치: " << knapsackMeetInMiddle(W, items);
}

1. 부분집합을 생성!
-getSubsets함수에서 비트마스크를 활용하여서 모든 경우의 수를 확인해 준다!

2. MITM
-주어진 아이템 값을 절반으로 나누어준다.
- 그 후에 모든 부분집합을 생성한 다음에 무게와 값(가치)으로 저장해 준다.
-모든 부분집합을 정렬해 주어서 무게별 최대 가치만 저장해 준다.

3. 이진 탐색
-W-wL이하의 최대 가치를 찾아준다!
-upper_bound를 이용하여서 무게 제한을 초과하지 않는 최대 가치를 가지는 값을 찾아준다.

활용 반경!

브루트 포스와 같은 완전 탐색 방법을 최적화하는 데 주로 사용되며, 부분집합 문제나 암호 해독 문제와 같은 부분에서 유용하게 활용된다.