SOS DP (1) 썸네일형 리스트형 82. Sum Over Subsets 집합이 존재할 때 각각의 부분집합에 대해 그 집합의 부분집합의 합(Sum Over Subsets, SOS)을 빠르게 계산하는 방법에 대해서 다룬다. 이 방법은 DP 테이블을 채우면서 부분집합의 합을 계산하기 때문에 SOS DP라고 불린다. 원소의 개수가 $n$인 집합의 부분집합의 개수가 $2^n$이고, SOS DP의 기본 시간복잡도가 $\Theta(2^n \cdot n)$이기 때문에 일반적으로 $n$은 $20$ 이하이다. SOS DP는 집합을 비트마스크로 표현하며, 따라서 비트필드를 이용하게 된다. 집합을 0-based로 나타내면 $0 \le p 두 집합 $A, B$를 나타내는 정수가 각각 $x, y$일 때 $(x \And y) = y$인 경우 $B \subset A$이고 $(y \And x) = x$.. 이전 1 다음
