Meet in the middle / 중간에서 만나기

1. 관련 문제

 

https://www.acmicpc.net/problem/1208

1208번: 부분수열의 합 2

 

 

 

2. Meet in the middle

 

최대 길이 40의 수열이 주어졌을 때, 이 수열의 원소들 중 몇 개를 중복되지 않게 선택하여 모두 더한 값이 S가 되도록 하는 경우의 수가 몇 개나 있는지 찾는 문제이다. 시간, 공간 복잡도를 생각하지 않고 간단하게 접근했을 때, 모든 원소들을 순회하면서 [포함 / 미포함]으로 둘 수 있기 때문에 최대 $2^{40}$번의 연산을 수행하게 된다. 여기서 더 최적화를 시키기 위해서 사용하는 방법이 Meet-in-the-middle 알고리즘이다. 

 

 

 

 

Meet-in-the-middle은 총 길이 40의 수열을 길이 20의 수열 2개로 나눈다. 각 수열마다 모든 경우의 수를 탐색하는 경우의 수는 $2^{20}$으로 매우 많이 감소될 수 있다. 40개의 수열을 반으로 나누었을 때, 왼쪽을 leftArr, 오른쪽을 rightArr이라고 해보자.

 

 

 

 

leftArr의 각 원소를 순회하면서 rightArr에서 S - leftArr[i] 의 값을 가진 것이 몇 개인지 찾아서 answer에 더해주면 된다. S - leftArr[i] 의 값이 몇 개인지 탐색하기 위해서 이분 탐색(Binary Search)을 사용하며 upper_bound와 lower_bound를 사용하여 검색한다.

 

 

 

• upper_bound: x보다 큰 값이 해당 배열에서 어디에 최초로 등장 하였는지를 반환한다.
• lower_bound: x보다 같거나 큰 값이 해당 배열에서 어디에 최초로 등장하였는지를 반환한다.

for (int i = 0; i < leftArr.size(); ++i) {
    auto upperIdx = upper_bound(rightArr.begin(), rightArr.end(), S-leftArr[i]);
    auto lowerIdx = lower_bound(rightArr.begin(), rightArr.end(), S-leftArr[i]);
    answer += upperIdx - lowerIdx;
}

 

 

 

 

결과적으로 meet-in-the-middle알고리즘은 $n^{m}$ 의 연산을 $2 \times n^{m-1}$ 의 연산으로 크게 줄여주는 알고리즘이다. 

 

 

 

3. 참고

 

https://blog.naver.com/chogahui05/221374387858

meet in the middle 알고리즘 - 반으로 쪼갠다.

https://blog.naver.com/kks227/221382873753

밋 인 더 미들(Meet in the Middle) (수정: 2018-10-25)