fineman999
commented
1 year ago meet in the middle Brute force를 이용할 때 조금은 부담되는 경우 사용하는 알고리즘입니다. 특히 부분집합을 구하는 경우 원소의 개수 N에 따라 연산은 2^N이 됩니다. 만약 N이 40이라면 이는 대략 10^12가 되어 모든 경우를 조사하는데 많은 시간을 쏟게 됩니다.
Meet in the middle 은 divide and conquer과 비슷하게 아래와 같은 과정을 거칩니다.
집합을 두 부분으로 나눕니다. 나뉜 집합에 필요한 연산을 각각 수행합니다. 두 결과를 이용해 원하는 조건을 만족하는 경우의 수를 구합니다.
1208번: 부분수열의 합 2