[알고리즘] Meet In The Middle 기법

이상현·2025년 4월 2일

알고리즘

목록 보기

14/15

완전 탐색 해야하는데 시간복잡도가 초과한다

알고리즘 문제를 풀어야 하는데, 완전탐색이 아니면 불가능한 문제인데, 만약 시간복잡도가 너무 크다면 어떻게 해야할까?

Meet in the Middle 은 이 문제를 해결하기 위한 기법이다.

Meet in the Middle

완전탐색을 해야하는데, $N = 30$ 이여서 시간복잡도가 $O(2^{30}) = 1,000,000,000$ 처럼 나온다면 문제를 유심히 봐보자.

범위를 반으로 나누어서 완전탐색을 해서 나온 값끼리 뭔가 계산을 하면 정답을 구할 수 있을 확률이 높다.

각 부분을 완전탐색하는 시간복잡도는 $O(2^{15}) = 30,000$ 으로 매우 크게 줄어든다. 심지어 $O(N^2)$ 연산을 곱해도 1억 미만이다.

예시 문제

백준 1450 - 냅색문제
이름이 냅색문제지만 알려진 냅색의 문제 풀이 방식이 아니다.
완전탐색을 통해 답을 구해야 하는 문제이다.

그냥 완전탐색을 하면, 위 예시와 동일하게 $O(2^{30}) = 1,000,000,000$ 으로 시간 초과가 나온다.

하지만 문제를 잘 생각해보면,

물건의 무게 배열을 절반으로 나누고
두 부분에 대해서 각각 가능한 모든 부분합을 구한 다음
그 두개의 부분합끼리의 모든 원소의 합을 구하면 답을 구할 수 있다.

예를 들면 입력이

4 5
1 2 3 4

이라고 할 때 완전탐색과 절반으로 나누어서 완전탐색을 했을때를 비교해보자.

완전탐색

무게 5 이하로 가능한 물건 담는 경우의 수는

1, 2, 3, 4 -> {}, {1}, {2}, {3}, {4}, {1, 2}, {1, 3}, {1, 4}, {2, 3}

이므로 가능한 무게의 경우의 수는 집합의 원소를 더해서

{0, 1, 2, 3, 4, 3, 4, 5, 5}
이렇게 9개의 경우의 수가 생겨서 답은 9 이다.

절반 나눠서 완전탐색

이번엔 무게 배열을 절반으로 나눠서 구해보자.

(무게 5 이하)
1, 2 의 물건 담는 경우의 수 -> {}, {1}, {2}, {1, 2} -> {0, 1, 2, 3}
3, 4 의 물건 담는 경우의 수 -> {}, {3}, {4} -> {0, 3, 4}

두 부분에 대해서 가능한 모든 부분합
-> {0, 3, 4, 1, 4, 5, 2, 5, 3}
이렇게 9개의 경우의 수가 생겨서 동일하게 답이 9이다.

절반으로 나눠서 탐색하고, 부분합으로 합쳐도 정답은 동일하게 나오는 것을 확인했다.

구현

단, 두 부분에 대해서 가능한 모든 부분합 을 단순하게 구해버리면, 전체 시간복잡도가 원래와 동일하게 $O(2^N)$ 이 되버린다.

이 때, 이진탐색 또는 투포인터 개념이 사용된다.

여기서는 이진탐색 (파라매트릭 서치) 를 사용했다. (참고: [알고리즘] Parametric Search)

절반 나누어서 나온 부분합에서 각 원소의 합을 정렬한 다음, 파라매트릭 서치를 활용하면 모든 원소를 순회하지 않아도 무게 5 이하로 될 수 있는 개수를 찾을 수 있다.

S1 = {0, 1, 2, 3}
S2 = {0, 3, 4}
라고 한다면
(예시에서는 이미 정렬되어있지만 코드에 따라 정렬되어있지 않을 확률이 높다.)

S1[0] = 0 에 대해서 S2중에 합해서 5가 넘지 않는 가장 큰 수는 4이다. 해당 값보다 작은 값은 모두 정답이라는 것이므로 정답 카운트에 3을 더한다.

...

S[3] = 3 에 대해서 S2중에 합해서 5가 넘지 않는 가장 큰 수는 0이므로 정답 카운트에 1을 더한다.

모든 원소에 대해 반복하면 정답이 나온다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int N, C;
    static int[] weight;
    static List<Integer> leftSum = new ArrayList<>();
    static List<Integer> rightSum = new ArrayList<>();

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken()); // 30
        C = Integer.parseInt(st.nextToken()); // 10^9
        weight = new int[N];

        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            weight[i] = Integer.parseInt(st.nextToken());
        }
        
        // 왼쪽 절반
        int[] leftWeight = Arrays.copyOfRange(weight, 0, N / 2);
        // 오른쪽 절반
        int[] rightWeight = Arrays.copyOfRange(weight, N / 2, N);

        List<Integer> leftSum = new ArrayList<>(); 
        List<Integer> rightSum = new ArrayList<>(); 

		// 각 부분에 대한 부분합 배열 계산
        calcSubSum(leftSum, leftWeight, 0, 0); 
        calcSubSum(rightSum, rightWeight, 0, 0);

		// 이분탐색을 위해 부분합 결과를 정렬
        leftSum.sort(null);
        rightSum.sort(null);

		// 파라매트릭 서치를 활용해 정답 계산
        int count = parametricSearch(leftSum, rightSum);

        System.out.println(count);
    }

	// ary 배열의 가능한 모든 원소 경우의 수의 합을 계산한다.
    private static void calcSubSum(List<Integer> subSum, int[] ary, int index, int sum) {
        if (sum > C) {
            return;
        }
        if (index >= ary.length) {
            subSum.add(sum);
            return;
        }

        calcSubSum(subSum, ary, index + 1, sum + ary[index]);
        calcSubSum(subSum, ary, index + 1, sum);
    }

	// 모든 leftSum 에 대해 rightSum 에서 적절한 값을 이분탐색
    private static int parametricSearch(List<Integer> leftSum, List<Integer> rightSum) {
        int count = 0;
        for (int i : leftSum) {
            // rightSum 에서 i + rightSum[index] 가 C 보다 같거나 작은 값 중 최대 값 찾기
            int ans = -1;
            int start = 0;
            int end = rightSum.size() - 1;

            while (start <= end) {
                int mid = (start + end) / 2;
                if (i + rightSum.get(mid) <= C) {
                    start = mid + 1;
                    ans = mid;
                } else {
                    end = mid - 1;
                }
            }

            if (ans == -1) {
                continue;
            }

            count += ans + 1;
        }

        return count;
    }
}