배열 하나와 목표 합계 값이 주어졌을 때, 주어진 합계 값을 초과하지 않는 최대 부분집합 합을 구하는 것이 이번 문제의 목표입니다. 주어진 배열의 구조가 일반적인 분할 정복(divide and conquer) 방식과 잘 맞지 않기 때문에 단순 브루트 포스(완전 탐색) 접근법은 효율적이지 않습니다.
이럴 때 유용하게 쓸 수 있는 것이 바로 미트 인 더 미들(Meet in the Middle) 기법입니다. 이 기법은 전체 집합을 절반씩 나누어 각각의 부분집합 합을 미리 계산해 둔 뒤, 두 결과를 조합하여 정답을 찾습니다. 이렇게 하면 시간 복잡도를 O(2n)에서 약 O(2n/2) 수준으로 크게 줄일 수 있습니다.
예제로 이해하기
입력 − long arr[] = { 21, 1, 2, 45, 9, 8 }, long given_Sum = 12
출력 − 주어진 합보다 작거나 같은 최대 부분집합 합 --> 12
설명 − 배열을 두 개의 부분집합으로 나눕니다. 첫 번째 부분집합은 n/2개의 원소를, 두 번째 부분집합은 나머지 원소들을 가집니다. 첫 번째 부분집합에서 만들 수 있는 모든 부분집합 합을 계산해 배열 A에 저장하고, 같은 방식으로 두 번째 부분집합의 부분집합 합을 계산해 배열 B에 저장합니다. 마지막으로 두 하위 문제의 결과를 조합하여 합이 주어진 값 이하가 되도록 병합합니다.
입력 − long arr[] = { 2, 12, 16, 25, 17, 27 }, long given_Sum = 24
출력 − 주어진 합보다 작거나 같은 최대 부분집합 합 --> 19
설명 − 위와 동일하게 배열을 절반으로 나눈 뒤 각 부분의 모든 부분집합 합을 구하고, 두 배열(A, B)을 조합해 주어진 합을 넘지 않는 최댓값을 찾습니다.
프로그램에서 사용된 접근 방식
- long 타입의 배열과 long 타입의 변수(목표 합계)를 선언·초기화한 뒤, calculateSubsetSum(arr, arr.length, given_Sum) 함수를 호출합니다.
- calculateSubsetSum(arr, arr.length, given_Sum) 메서드 내부에서는 다음 과정을 수행합니다.
- solve_subarray(a, A, len / 2, 0)와 solve_subarray(a, B, len - len / 2, len / 2)를 호출해 앞부분과 뒷부분의 모든 부분집합 합을 각각 A, B에 저장합니다.
- A와 B의 크기를 계산한 뒤, sort() 메서드로 배열 B를 정렬합니다.
- i를 0부터 배열 A의 크기까지 반복하는 FOR 루프를 시작합니다. A[i]가 given_Sum 이하라면 get_lower_bound를 calculate_lower_bound(B, given_Sum - A[i])로 설정합니다. 이때 get_lower_bound가 size_B와 같거나 B[get_lower_bound]가 (given_Sum - A[i])와 같지 않으면 get_lower_bound를 1 감소시킵니다.
- B[get_lower_bound] + A[i]가 현재 max보다 크면 max를 B[get_lower_bound] + A[i]로 갱신합니다.
- max를 반환합니다.
- solve_subarray(long a[], long x[], int n, int c) 메서드 내부에서는 다음 과정을 수행합니다.
- i를 0부터 (1 << n) 미만까지 반복하는 FOR 루프를 시작하고, 루프 안에서 sum을 0으로 초기화합니다.
- j를 0부터 n 미만까지 반복하며, (i & (1 << j)) 연산 결과가 0이면 sum에 a[j + c]를 더합니다.
- x[i]에 sum을 저장합니다.
- calculate_lower_bound(long a[], long x) 메서드 내부에서는 다음 과정을 수행합니다.
- left를 -1로, right를 배열의 길이로 초기화합니다.
- left + 1이 right보다 작은 동안 WHILE 루프를 돌며, m을 (left + right) >>> 1로 설정합니다. a[m]이 x보다 크거나 같으면 right를 m으로, 그렇지 않으면 left를 m으로 설정합니다.
- right를 반환합니다.
예제 코드
import java.util.*;
import java.lang.*;
import java.io.*;
public class testClass{
static long A[] = new long[2000005];
static long B[] = new long[2000005];
static void solve_subarray(long a[], long x[], int n, int c){
for (int i = 0; i < (1 << n); i++){
long sum = 0;
for (int j = 0; j < n; j++){
if ((i & (1 << j)) == 0){
sum += a[j + c];
}
}
x[i] = sum;
}
}
static long calculateSubsetSum(long a[], int len, long given_Sum){
solve_subarray(a, A, len / 2, 0);
solve_subarray(a, B, len - len / 2, len / 2);
int size_A = 1 << (len / 2);
int size_B = 1 << (len - len / 2);
Arrays.sort(B);
long max = 0;
for (int i = 0; i < size_A; i++){
if (A[i] <= given_Sum){
int get_lower_bound = calculate_lower_bound(B, given_Sum - A[i]);
if (get_lower_bound == size_B || B[get_lower_bound] != (given_Sum - A[i])){
get_lower_bound--;
}
if((B[get_lower_bound] + A[i]) > max){
max = B[get_lower_bound] + A[i];
}
}
}
return max;
}
static int calculate_lower_bound(long a[], long x){
int left = -1, right = a.length;
while (left + 1 < right){
int m = (left + right) >>> 1;
if (a[m] >= x){
right = m;
}
else{
left = m;
}
}
return right;
}
public static void main(String[] args){
long arr[] = { 21, 1, 2, 45, 9, 8 };
long given_Sum = 12;
System.out.println("The maximum sum subset having sum less than or equal to the given sum-->" + calculateSubsetSum(arr, arr.length, given_Sum));
}
}
출력
위 코드를 실행하면 다음과 같은 출력이 생성됩니다.
The maximum sum subset having sum less than or equal to the given sum-->12
정리
미트 인 더 미들 기법은 n이 대략 30~40 수준으로 완전 탐색으로는 감당하기 어렵지만, 값의 범위가 커서 DP 테이블을 만들기 어려운 상황에서 특히 유용합니다. 부분집합을 절반으로 나누어 각각 2^(n/2)개의 합을 구한 뒤, 정렬과 이분 탐색(lower bound)으로 두 결과를 결합하면 전체 탐색 공간을 극적으로 줄일 수 있습니다.