알고리즘/기타
2021. 6. 30.
MITM, sqrt Decomposition
Meet in the middle (MITM)에 대해 알아봅시다. https://www.acmicpc.net/problem/1208 1208번: 부분수열의 합 2 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 40, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다. www.acmicpc.net 길이가 최대 40인 수열이 주어지고, 이 수열의 부분수열 중 원소의 합이 \(S\)인 것의 개수를 구해야 합니다. 이를 나이브하게 브루트 포스로 구하려면 \(O(2^n)\)의 시간복잡도를 가지게 되고, 이는 \(n\)이 최대 40이므로 너무 느립니다. 하지만, 수열을 반으로 나눠서 생각해 보면..
