백준 1450번 meet in the middle

서론

1450번: 냅색문제

문제에 meet in the middle로 풀라고 쓰여 있었는데 모르는 알고리즘이라서 학습 후에 풀었습니다. 굉장히 신기해서 글로 남깁니다. 탐색 구간을 줄이는 방법인데 시간제한 조건 쪽에서 자세하게 설명할 수 있을 것 같습니다. 그리고 더 잘 짜려고 다른 사람의 코드를 보던 중 느낀 점이 많아 생각 부분에 정리하도록 하겠습니다.

제한 조건

• 시간제한 - 1초

시간제한은 1초입니다. 일반적인 컴퓨터로 1초에 1억 번 연산한다는 기준을 가지고 풉니다. N<=30 이기 때문에 사실상 물건을 넣고 안 넣고를 기준으로 2^30가지 경우를 탐색하면 되는 문제입니다. 하지만 2^30 = 10억이므로 1초를 훌쩍 넘기게 됩니다. 여기서 meet in the middle 개념이 나옵니다.

이 알고리즘은 N을 둘로 쪼개서 탐색하는 방법을 사용합니다. N을 둘로 쪼개면 탐색 구간은 2*2^15가 되고 2^15는 32,000밖에 되지 않기 때문에 탐색이 엄청나게 줄어듭니다. 제가 짠 코드의 경우 탐색을 하면서 그 조합에 대한 물건의 합을 리스트에서 계산했기 때문에 N이 곱해졌고 총 시간복잡도 O(N*2^(N/2))으로 풀 수 있었습니다.

• 메모리 제한 - 128MB

메모리 제한은 128MB입니다. N 자체가 30밖에 안 돼서 메모리 제한은 문제가 없습니다. N에 들어가는 숫자가 10억으로 꽤 큰데 어차피 파이썬에서는 10억까지 28byte에 담기 때문에 전혀 문제없습니다.

Meet in the middle

meet in the middle 알고리즘을 사용하여 탐색 수를 줄이면 됩니다. 여기서는 절반씩 나눠서 탐색하며 그 부분합을 리스트에 담았고, 이분탐색을 통해서 가방의 크기와 같거나 보다 작은 케이스를 카운트했습니다.

import sys
input = sys.stdin.readline

N, C = map(int, input().split())
num_list = list(map(int, input().split()))

left_list = num_list[:N//2]
right_list = num_list[N//2:]

left_sum = []
right_sum = []

# (N/2)*2^(N/2)
for i in range(2**(len(left_list))):
    subset = bin(i)[2:].zfill(len(left_list))
    sum = 0
    for j in range(len(subset)):
        if subset[j] == '1':
            sum += left_list[j]
    left_sum.append(sum)

# (N/2)*2^(N/2)
for i in range(2**(len(right_list))):
    subset = bin(i)[2:].zfill(len(right_list))
    sum = 0
    for j in range(len(subset)):
        if subset[j] == '1':
            sum += right_list[j]
    right_sum.append(sum)

# N*log(N)
right_sum.sort()

cnt = 0

# (N/2)*log(N/2)
for num in left_sum:
    if num > C:
        continue
    target = C-num
    left = 0
    right = len(right_sum)
    while left < right:
        mid = (left+right)//2
        if right_sum[mid] > target:
            right = mid
        else:
            left = mid+1
    cnt += right

print(cnt)
# 따라서 총시간복잡도는 N*2^(N/2)
# 이분탐색도 중요하지만 meet in the middle 알고리즘을 통해서 시간복잡도가 정해진다.

생각

위의 코드에서 부분합을 계산하는 과정에서 bitmask가 떠올라서 bitmask를 사용하여 담았는데 동작은 파이썬 표준 lib인 combinations와 똑같습니다. 또 이분탐색을 하는 동작도 마찬가지로 bisect가 하는 동작과 똑같습니다. 지금까지는 연습한다는 느낌으로 이런 lib를 사용하지 않고 직접 짰지만, 앞으로는 내장함수만 사용하라고 따로 명시한 게 아니라면 표준 lib는 쓰는 게 좋을 것 같습니다. 아래 코드는 제가 짠 코드와 완벽하게 똑같은 동작을 하는데 표준 lib를 사용해서 훨씬 직관적이고 깔끔합니다.

import bisect
from itertools import combinations


def solve():
    n, c = map(int, input().split())
    w = list(map(int, input().split()))

    # len(left) <= len(right)
    left = w[:len(w)//2]
    right = w[len(w)//2:]

    left_sums = []
    right_sums = []
    for i in range(len(left) + 1):
        left_sums += list(map(sum, combinations(left, i)))
    for i in range(len(right) + 1):
        right_sums += list(map(sum, combinations(right, i)))

    left_sums.sort()
    ans = 0
    for r in right_sums:
        ans += bisect.bisect_right(left_sums, c - r)
    print(ans)


solve()

물론 표준 lib에 익숙해져서 추후 코딩테스트에서 표준 lib을 사용하지 말라고 했을 때 문제가 생길 수 있습니다. 따라서 표준 lib을 사용하더라도 원리나 구현을 꾸준히 생각하면서 사용하는 것이 좋을 것 같습니다.

*추가

검색해보니까 특정 코딩테스트를 제외하곤 딱히 표준 lib에 대한 제한이 없습니다. 지금까지 표준 lib 기능을 하는 것들을 구현하면서 충분히 공부했으니 이제는 그냥 표준 lib을 활용하는 법을 배워야겠습니다. 표준 lib도 잘 사용해야겠습니다.