1. 개요
이분탐색 문제를 찾아 풀다가 1450. 냅색문제에서 처음에는 투포인터로 접근해서 풀다가
정답을 보니 브루트포스, 분할정복(?), 이분탐색이 한데 어울러진 듯한 느낌을 받아 정리하게 되었다.
cf. MITM 기법의 핵심은 브루트포스를 분할하는 것이며, 추가적인 연산에 +a의 알고리즘 기법이 사용되었을 뿐이다.
2. MITM(Meet In The Middle)
: 브루트포스 알고리즘을 사용해야 할 경우, 브루트포스를 분할해서 복잡도를 최소화하는 알고리즘 기법이다.
분할정복과의 차이점?
: 분할정복은 작은 문제들의 해결을 합치면서, 큰 문제의 해결로 이어져 나간다.
MITM 문제를 쪼개는 것은 같지만, 중간에서 만나 결합하는 과정에서 +a의 추가적인 연산이 필요하다.
3. 문제 예시
*BOJ - 1450. 냅색문제
[코드]
# O(2^(N/2))
# 부분집합 합 리스트를 생성한다.
def createPartialSumList(wList, sumList, idx, currentSum):
if idx == len(wList):
sumList.append(currentSum)
return
createPartialSumList(wList, sumList, idx + 1, currentSum) # 현재 요소를 포함하지 않는 경우
createPartialSumList(wList, sumList, idx + 1, currentSum + wList[idx]) # 현재 요소를 포함하는 경우
# O(log(2^(N/2)))
# upperBound를 찾는다. 0 ~ upperBound index 전까지 짐을 넣을 수 있다.
def bns(sumB, k):
lo, hi = -1, len(sumB)
while lo + 1 < hi:
mid = (lo + hi) // 2
if sumB[mid] <= k:
lo = mid
else:
hi = mid
return hi
def main():
N, C = map(int, input().split())
weight = list(map(int, input().split()))
mid = len(weight) // 2
weightA = weight[:mid]
weightB = weight[mid:]
sumA = []
sumB = []
createPartialSumList(weightA, sumA, 0, 0) # 부분집합 합
createPartialSumList(weightB, sumB, 0, 0)
# "sumA의 원소 + sumB의 원소 <= C"인 경우의 수를 체크해야 된다.
# sumA와 sumB 각 원소의 갯수는 최대 2^15
# 일반적으로 체크할 시 복잡도는, (2^15) * (2^15) 가 된다.
# 따라서 sumB를 정렬을 진행하고, sumA의 lowerBound를 찾아 하위에 있는 경우의 수는 모두 포함시키도록 하자.
sumB.sort()
result = 0
for k in sumA:
idx = bns(sumB, C-k) # C-k 무게 이하로 넣어야 한다.
result += idx
print(result)
if __name__ == "__main__":
main()
[풀이]
"N개의 물건을 가방에 넣을 수 있는 조합의 갯수"를 찾는 문제이다.
이는 각 물건을 넣고 빼는 경우의 수를 모두 고려해야 하므로 시간복잡도가 O(2^N)이 된다.
위의 흐름으로 접근할 때, 입력값의 범위에 의하면 O(2^30) = 10억으로 시간초과가 나게 된다.
그러면 어떻게 접근해야 했을까?
N개를 a, b 절반으로 나누면 된다.
a, b의 '부분집합의 합'으로 나올 수 있는 경우의 수를 고려하면, O(2^(2/N)), O(2^(2/N))이 나온다.
위에서 나온 '부분집합의 합' 리스트를 sumA, sumB라고 하자.
이대로 다시 sumA와 sumB에서 각각 1개씩 추출해, 주어진 무게 w와 비교하는 로직은 이전과 변함없이 O(2^30)이 된다.
여기에서 이분탐색이 필요하다.
sumB를 정렬을 하고, (w - sumA 각 원소)에 대한 upperBound를 찾고
그 이하의 sumB의 원소들은 현재 sumA 원소와 매칭되어 가방에 들어갈 수 있는 경우의 수이다.
4. 문제 적용
1) BOJ - 1208. 부분수열의 합 2
[코드]
# O(2^len(k))
# 부분수열 집합 구하기
def createPartialSum(k, sumK, l, value):
if l == len(k):
sumK.append(value)
return
createPartialSum(k, sumK, l + 1, value + k[l]) # l번째 원소 포함 o
createPartialSum(k, sumK, l + 1, value) # l번째 원소 포함 x
# O(log(len(k)))
# lowerBound 구하기
def lowerBound(lst, criteria):
lo, hi = -1, len(lst),
while lo + 1 < hi:
mid = (lo + hi) // 2
if lst[mid] < criteria:
lo = mid
else:
hi = mid
return hi
# O(log(len(k)))
# upperBound 구하기
def upperBound(lst, criteria):
lo, hi = -1, len(lst),
while lo + 1 < hi:
mid = (lo + hi) // 2
if lst[mid] <= criteria:
lo = mid
else:
hi = mid
return hi
# upperBound - lowerBound 구하기
def minusUpperLower(sums, criteria):
return upperBound(sums, criteria) - lowerBound(sums, criteria)
# O(len(k) * log(len(k)))
def main():
# 정수의 갯수, 수열의 원소를 더해서 목표하는 값
N, S = map(int, input().split())
lst = list(map(int, input().split()))
a, b = lst[:N // 2], lst[N // 2:]
sumA, sumB = [], []
createPartialSum(a, sumA, 0, 0)
createPartialSum(b, sumB, 0, 0)
sumA.pop()
sumB.pop()
result = 0
sumA.sort()
sumB.sort()
for one in sumA:
# ---Bound + one = S 가 되어야 한다.
# ---Bound = S - one 이 되어야 한다.
result += minusUpperLower(sumB, S - one)
result += minusUpperLower(sumA, S)
result += minusUpperLower(sumB, S)
print(result)
if __name__ == "__main__":
main()
[풀이]
"크기가 양수인 부분 수열 중에서, 그 수열의 원소를 다 더한 값이 S"가 되는 경우의 수를 찾는 문제이다.
N의 범위는 1 <= N <= 40 으로 부분 수열의 집합을 구하는 데만 2^40 가 되어 시간 초과가 난다.
따라서 2개의 집합 sumA, sumB으로 분리, 각 집합의 부분 수열 집합을 구한다. (2^20)
'a + b = S' 가 되어야 하기 때문에, 이분 탐색을 할 때 'b = S - a' 로 접근해 upper/lowerBound를 구하면 된다.
이 때 upper/lowerBound를 모두 구하는 이유는 중복된 수가 있을 수도 있기 때문에 upper - lower 를 하여 해당 수의 갯수를 모두 찾아주어야 한다.
sumA, sumB 자체 리스트에도 'S'가 포함될 수 있기 때문에 각 부분 수열 집합에도 'S'를 찾는 이분탐색을 진행해주어야 한다.
[주의해야 할 점]
sumA, sumB 모두 upper/lowerBound를 구하기 때문에 정렬을 반드시 해주어야 한다.
sumA, sumB에서 'S'를 찾는 과정을 잊으면 안 된다.
+. "+a의 추가적인 연산" 은 이분탐색에 해당한다.
2) BOJ - 16287. Parcel
[코드]
W, N = map(int, input().split())
lst = list(map(int, input().split()))
memoization = [False] * W
for i in range(1, N):
# i를 기준으로, 왼쪽에서 크기가 2인 부분집합을 고른다.
for j in range(i):
if lst[i] + lst[j] < W:
memoization[lst[i] + lst[j]] = True
# i+1을 기준으로, 오른쪽에서 크기가 2인 부분집합을 고른다.
# j는 i+2부터 시작해야 한다.
for j in range(i + 2, N):
if lst[i + 1] + lst[j] < W and memoization[W - (lst[i + 1] + lst[j])]:
print("YES")
exit()
print("NO") # i+1을 기준으로, 오른쪽에서 크기가 2인 부분집합을 고른다.
# 여기에서 i+1은 왼쪽 기준 i가 끝나고 반복문이 1번 끝남으로써 i++이 적용된 i이므로, i+1이라고 명시했다.
for j in range(i+1, N):
if lst[i] + lst[j] < W and memoization[W - (lst[i] + lst[j])]:
print("YES")
exit()
# i를 기준으로, 왼쪽에서 크기가 2인 부분집합을 고른다.
for j in range(i):
if lst[i] + lst[j] < W:
memoization[lst[i] + lst[j]] = True
[풀이]
"n개의 물건 중에 4개를 선정해 정확히 W 무게를 맞출 수 있는지?"를 묻는 문제이다.
n의 범위는 4 <= n <= 5000으로, 일반적인 브루트 포스로 접근했을 때 시간복잡도는 nC4 = n^4 가 되어 시간초과가 난다.
따라서 2개의 집합으로 나누어서 생각을 해야 하는데, 이 때 2개의 집합으로 나누는 것을 포인터를 bottom-up 방식으로 바꿔가며 약 N번을 진행해야 한다.
Left 집합에서 2개의 원소 i, j1 조합 합에 대한 memoization을 진행하고,
Right 집합에서 2개의 원소 i, j2 조합 합(value), W - value 값에 대한 memoization이 되었는지 확인하면 된다.
이렇게 시간복잡도를 n^4에서 n^2으로 줄일 수 있다.
[주의해야 할 점]
Left 집합에서 memoization 진행, Right 집합에서 memoization 체크가 이뤄지는데
Left, Right 연산에 대한 순서를 정확히 잡고, i 포인터를 잡는 것이 중요하다.
첫 번째 코드는 memoization 진행, memoization 체크
두 번째 코드는 memoization 체크, memoization 진행
으로 작성을 해보았다.
+. "+a의 추가적인 연산" 은 DP/memoization 해당한다.