중간에서 만나기(Meet in the Middle)이란?중간에서 만나기란 완전 탐색에 시간이 오래 걸리는 경우 대상을 두 그룹으로 나누어 탐색하여 시간을 단축하는 방법이다. 예를 들어, 크기가 $N$인 집합의 모든 부분 집합을 구하기 위해서는 $O(2^N)$의 시간이 걸린다.하지만 모든 부분 집합 중 특정 조건을 만족하는 경우를 찾기만 하면 된다면, 집합을 반으로 쪼개 각각 탐색하여 $O(2\times2^{N/2})$만에 해결할 수 있다. MITM 적용해보기백준 1208번 부분수열의 합 2 문제를 직접 풀어보자.수열의 부분수열 중 합이 $S$가 되는 경우의 수를 구하는 문제이다. 완전 탐색을 위해서는 앞에서 말했듯이 $2^{40} = 1,099,511,627,776$회의 연산이 필요한데, 이는 제한 시..
