중간에서 만나기3 - 부분집합의 합이 s가 되는 경우의 수를 세는 놀라운 방법

1. 중간에서 만나기(meet in the middle)

 

중간에서 만나기 알고리즘은, 다익스트라 알고리즘처럼 전형화된 그런 알고리즘은 아니다.

 

다이나믹 프로그래밍 같은 알고리즘이라고 해야할까

 

완전탐색의 시간복잡도가 매우 높을 때, 이를 절반으로 줄이는 기법이다.

 

가능한 경우의 수를 절반씩 나누어 탐색한 뒤 그 결과를 조합하여 정답을 찾는 방식이다.

 

예를 들어 브루트포스가 $O(2^{N})$으로 매우 높은 경우, $O(2^{N/2})$로 줄일 수 있을때 효과적이다.

 

N = 40인 경우만 해도 아예 불가능한 정도가 $10^{6}$정도로 가능해진다

 

 

 

 

예를 들어 주어진 수열 A에서 부분집합의 합이 S가 되는 경우의 수는 몇가지일까?

 

부분집합의 개수는 $2^{N}$이므로, 시간복잡도는 $O(2^{N})$

 

1) 하지만 A를 절반으로 나눠서 left_A, right_A라고 하자.

 

2) left_A에서 부분집합을 구해 그 합을 L이라고 하자.

 

3) target값은 S일때, right_A에서 구해야할 부분집합의 합은 S-L이다.

 

4) right_A에서 만들 수 있는 모든 부분집합의 합을 어떤 배열 right_s_A로 저장해두고 정렬하자.

 

5) 여기서 S-L이 정확히 될 수 있는 값을 이분탐색으로 찾는다면, $O(2^{N/2} * log(2^{N/2}))$정도에 답을 찾을 수 있다.

 

from itertools import combinations
import bisect

def get_sums(arr):
    result = []
    for k in range(len(arr)+1):
        for comb in combinations(arr, k):
            result.append(sum(comb))
    return result

A = [1, 3, 5, 7, 9]
S = 8
n = len(A)

left = A[:n//2]   # [1, 3]
right = A[n//2:]  # [5, 7, 9]

left_sums = get_sums(left)
right_sums = get_sums(right)
right_sums.sort()

found = False
for l in left_sums:
    target = S - l
    idx = bisect.bisect_left(right_sums, target)
    if idx < len(right_sums) and right_sums[idx] == target:
        found = True
        break

print("YES" if found else "NO")

 

 

2. 연습문제

 

1450번: 냅색문제

 

n개의 물건의 무게들이 주어지고, 최대 C만큼 가방에 담을 수 있다.

 

물건들을 이 가방에 담을 수 있는 방법의 수는?

 

---------------------------------------------------------------------------------------------------------------------------------

 

가장 쉽게 생각할 수 있는 방법은, 물건들 무게의 모든 부분집합 $O(2^{N})$에 찾아서, 부분집합의 합이 C보다 작거나 같은지 검사하는 방법

 

하지만 N <= 30이라 2^30 = 1073741824나 되어서 시간안에 불가능하다.

 

위에서 배운 중간에서 만나기... 부분집합의 합을 중간에서 만나기를 이용해 해결해보자.

 

물건 무게 배열을 절반으로 나누자

 

두 배열 각각에서 가능한 모든 부분집합의 합을 찾아 배열로 만든다

 

n,c = map(int,input().split())

A = list(map(int,input().split()))

B = A[:n//2]

sum_B = []

for i in range(len(B)+1):
    
    combs = combinations(B,i)

    for comb in combs:
        
        sum_B.append(sum(comb))

C = A[n//2:]

sum_C = []

for i in range(len(C)+1):
    
    combs = combinations(C,i)

    for comb in combs:
        
        sum_C.append(sum(comb))

 

 

배열 하나 sum_C는 정렬해두고, sum_B에서 순회해서, 그 합을 b라고 하자.

 

배낭의 가능한 최대 무게는 c이므로, 정렬해둔 배열 sum_C에서 c-b 이하의 값이 몇개나 있는지 찾으면 된다.

 

즉, 이분탐색으로 c-b 이하의 값이 몇개나 있는지 인덱스를 찾아내서, 그 인덱스를 더해주면 된다

 

from itertools import combinations

def binary_search(array,target,start,end):
    
    while start < end:
        
        mid = (start+end)//2

        if array[mid] > target:
            
            end = mid
        
        else:
            
            start = mid + 1
    
    return end
    
sum_C.sort()

count = 0

for b in sum_B:
    
    ind = binary_search(sum_C,c-b,0,len(sum_C))

    if ind >= 1:

        count += ind

print(count)