Sum over Subsets (1) 썸네일형 리스트형 82. Sum over Subsets 집합이 존재할 때 각각의 부분집합에 대해 그 집합의 부분집합의 합(Sum over Subsets)을 빠르게 계산하는 방법에 대해서 다룬다. 이 방법은 DP 테이블을 채우면서 부분집합의 합을 계산하기 때문에 SOS DP라고 불린다. 원소의 개수가 $n$인 집합의 부분집합의 개수가 $2^n$이고, SOS DP의 기본 시간복잡도가 $\Theta(2^n \cdot n)$이기 때문에 일반적으로 $n$은 $20$ 이하이다. SOS DP는 집합을 비트마스크로 표현하며, 따라서 비트필드를 이용하게 된다. 집합을 0-based로 나타내면 $0 \le p < 2^n$을 만족하는 정수 $p$는 $p$의 켜진 비트에 해당하는 원소들을 포함하는 집합을 나타내는 것으로 생각할 수 있다. 예를 들어 $0$번째, $3$번째 원소를 .. 이전 1 다음
