※ 이 공부기록은 부정확한 내용이 다수 포함되어있을 수 있다. 또한 이 글은 정보 전달이 주 목적이 아닌 개인적인 기록용이어서 체계적으로 내용이 정리되어 있지 않을 수 있다. 읽는이의 양해를 바란다.
들어가기 전에
Sum Over Subsets DP, 줄여서 SOS DP는 PS/CP에서는 꽤 유명한 주제라고 생각한다. 이름값이 있는 알고리즘이다보니 글쓴이도 예전에 SOS DP를 익히려고 시도한 적이 있었으나, 그 때에는 개념을 읽어도 이를 적용해 해결할 수 있는 관련 문제를 제대로 찾지 못해 나중으로 미뤘었다.
앞으로 계속 익힐 주제들과 비교했을 때 SOS DP는 더 미루기에는 너무 유명한 주제라는 생각이 들었다. 더 미루지 말고 이런 생각이 든 김에 SOS DP와 그 관련 주제를 공부해 보자.
Submask Enumeration
원소가 \(K\)개인 집합 \(S\)의 각 부분집합 \(A\)는 \(K\)개의 비트를 이용하여 각 원소와 대응되는 비트를 키고 끄는 것으로 모두 나타낼 수 있다. 만약 \(S\)의 모든 각 부분집합 \(m\)에 대하여 각 집합의 모든 부분집합 \(m'\)에 접근하는 알고리즘을 설계한다면 총 몇 개의 \(m'\)에 접근하게 될까?
단순하게 생각하면, 부분집합의 개수가 가장 많은 \(S\)의 부분집합 \(m\)은 \(S\)이고 \(S\)의 부분집합의 개수는 \(2^K\)개이므로 일단 \(O(4^K)\)가 될 것이라고 생각할 수 있다. 그러나 실제로는 이보다 더 적은 \(3^K\)개의 \(m'\)에 접근하게 된다.
\(A\)의 원소 \(k\)개인 부분집합은 \(\binom{K}{k}\)개이며, 각 부분집합은 \(2^k\)개의 부분집합을 가진다. 따라서 \(A\)의 원소 \(k\)개인 부분집합에서는 총 \(\binom{K}{k}2^k\)개의 \(m'\)에 접근하게 된다.
이를 모든 \(k\)에 대해 합하면 이항정리(binomial theorem)에 의해 \(\sum_{k=0}^K \binom{K}{k}2^k=3^K\)가 된다.
\(3^{17}\)이 129140163이므로, 제한시간이 넉넉하게 주어지는 문제의 경우 이러한 접근법으로 해결할 수도 있다.
참고로, bitmask를 활용하여 표현된 어떤 집합을 나타내는 정수\(x\)가 있을 때, \(x\)의 모든 부분집합은 초기값이 \(x\)인 변수 \(x'\)에 대하여 \(x':=(x'-1)\&x\)를 반복하는 것으로 모두 접근할 수 있다.
Sum Over Subsets DP
집합의 부분집합에 대한 몇몇 DP 문제는 위와 같은 접근으로 해결할 수 있지만, 모든 문제를 위와 같이 해결할 수 있는 것은 아니다.
Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m'\subseteq m} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.
각 부분집합 \(m\)과 원소의 인덱스 \(k\)에 대하여 \(dp(m, k)\)를 \(m\)의 부분집합 \(m'\)중 \(k\)를 초과하는 인덱스의 원소의 포함 여부는 \(m\)과 상태가 동일한 집합에 대한 \(f(m')\)의 합으로 정의하자. 그리고 초기값으로 \(S\)의 각 부분집합 \(m\)에 대하여 \(dp(m, -1)\)을 \(f(m)\)이라 정의하자.
\(dp(m, k)\)의 합을 구성하는 부분집합들을 인덱스 \(k\)의 원소를 포함하는 부분집합과 그렇지 않은 부분집합으로 나누어 생각해보자. "인덱스 \(k\)의 원소를 포함하는 부분집합"은 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m\)와 상태가 동일하다. 따라서 이 집합들의 \(f\)값의 합은 \(dp(m, k-1)\)와 같다. 그리고 "그렇지 않은 부분집합"의 \(f\)값의 합은 \(m\)에서 인덱스 \(k\)의 원소를 제거한 집합 \(m^*\)에 대하여 인덱스가 \(k\) 이상의 인덱스를 갖는 원소의 포함 여부가 \(m^*\)와 동일한 부분집합 \(m'\)들에 대한 \(f(m')\)의 합과 같다.
위의 관계를 식으로 나타내면 다음과 같다.
\(S\)의 부분집합 \(m\)에 대하여, \(m\)이 인덱스 \(k\)의 원소를 포함할 경우 \(dp(m, k) = dp(m^*, k-1) + dp(m,k-1)\)
\(m\)이 인덱스 \(k\)의 원소를 포함하지 않을 경우 \(dp(m, k) = dp(m, k-1)\)
구하고자 하는 값은 \(dp(S,K-1)\)이므로, 이를 계산하려면 위 형태의 점화식을 \(O(K2^K)\)회 계산하면 된다. 위 점화식을 이루는 연산은 단순 덧셈이니 \(O(1)\)에 실행할 수 있다. 따라서 점화식을 이루는 각 집합에 대한 접근이 O(1)에 이뤄질 수 있으면 이 알고리즘의 시간복잡도는 \(O(K2^K)\)가 된다. 이는 비트마스킹을 이용하여 간단히 해낼 수 있다.
정확히 위의 문제를 해결하고자 하는 경우, \(k\)값에 대한 모든 \(dp\)값을 계산한다면 \(k-1\) 이하의 값은 더 이상 필요없어지므로, \(k\)에 대해 순차적으로 계산하면서 각 \(k\)에 대하여 집합들을 적절한 순서로 방문하는 것으로 \(O(2^K)\)의 메모리를 활용해 문제를 해결할 수도 있다.
Sum Over Supersets DP
Sum Over Subsets DP는 원소가 \(K\)개인 집합 \(S\)의 모든 부분집합 \(m\)에 대하여 \(f(m)\)의 값이 알려져 있을 때 \(\sum_{m\subseteq m'\subseteq S} f(m')\)의 값들을 \(O(K2^K)\)에 계산하는 동적 계획법 알고리즘이다.
이 문제는 앞에서 살펴본 Sum Over Subsets DP와 완전히 동일한 방식으로 해결할 수 있다. 단순히 각 부분집합들을 \(S\)에 대한 여집합에 대응시키면 문제가 Sum Over Subsets DP와 동일해짐을 확인하자.
OR Convolution
두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 OR Convolution이라고 한다.
편의를 위해, 집합 \(m'\)에 대하여 \(a_{m'}\)을 \(a\)의 "\(m'\)에 대응되는 비트마스크"번째 수로 정의하자.
그리고 두 함수 \(A\)와 \(B\)를 \(A(m)=\sum_{m'\subseteq m} a_{m'}\), \(B(m)=\sum_{m'\subseteq m} b_{m'}\)으로 정의하자.
이 때, \(A(m)\cdot B(m)\)의 값은 \( \sum_{m'\subseteq m} a_{m'} \cdot \sum_{m'\subseteq m} b_{m'} \)이 된다.
그리고 위의 값은 \(C(m)=\sum_{m'\subseteq m} c_{m'}\)의 값과 같다는 것을 어렵지 않게 알 수 있다.
\(a_n\)과 \(b_n\)으로부터 \(A\)와 \(B\)를 얻는 것은 SOS DP로 어렵지 않게 해낼 수 있다. 그렇다면 \(C\)로부터 \(c_n\)을 얻는 것은 가능할까? \(c_n\)으로부터 \(C\)를 얻는 것은 SOS DP를 통해 어렵지 않게 할 수 있으므로, 이를 거꾸로 수행하면 \(C\)로부터 \(c_n\)을 얻을 수 있다!
AND Convolution
두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i\&j=m}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 AND Convolution이라고 한다.
AND Convolution 역시 위의 OR Convolution과 동일한 원리로 수행할 수 있다.
Subset Convolution
\(K\)값이 크지 않다면, 몇몇 문제는 \(O(K^22^K)\) 꼴의 시간복잡도 풀이를 갖기도 한다. 그 예시로 Subset Convolution을 소개한다.
두 수열 \(a_0, a_1, \cdots, a_{2^K-1}\)과 \(b_0, b_1, \cdots, b_{2^K-1}\)에 대하여 \(c_m=\sum_{i|j=m, i\&j=0}a_ib_j\)을 만족하는 수열 \(c_0, c_1, \cdots, c_{2^K-1}\)를 정의하자. 여기에서 \(|\)은 두 정수의 bitwise OR 연산을, \(\&\)은 두 정수의 bitwise AND 연산을 의미한다. 이 때 수열 \(c\)를 수열 \(a\)와 \(b\)의 Subset Convolution이라고 한다.
Subset Convolution이 OR Convolution과 다른 점은 \(i\&j=0\) 조건이 하나 추가된 것이 전부임을 확인하자. 이 점을 이용하면 Subset Convolution을 \(O(K^22^K)\)에 계산할 수 있다.
\(A(m, k)\)와 \(B(m,k)\)를 1인 비트의 개수가 \(k\)개인 \(m\)으로 나타나는 항의 값만을 이용한(나머지 항은 0으로 취급) \(a\)와 \(b\)에 대한 SOS DP의 결과라 하자. 그리고 \(C(m, k)=\sum_{k'=0}^{k}A(m,k')\cdot B(m,k-k')\)과 같이 정의하자. 이렇게 \(C\)를 정의하면 \(k\)가 \(m\)의 1인 비트 개수와 정확히 같을 때 \(A\)와 \(B\)에서 겹치는 비트가 없어야지만 OR 값으로 \(m\)이 정확히 나오게 강제할 수 있으므로, 각 \(k\)에 대하여 SOS DP의 undo하는 과정을 거치면 각 \(m\)에 대하여 \(m\)의 1인 비트 개수 \(k\)에 대해 (undo된) 값을 확인하는 것으로 Subset Convolution의 값을 모두 얻을 수 있다.
여담
bitmasking 문제를 만난다면 먼저 최대한 문제를 단순한 형태로 정리해보고, 두 mask 사이의 subset 관계를 활용하기 좋은 형태일 때 이 글의 내용을 풀이법 후보로 생각해보는 것이 좋다. 한편, mask 사이의 포함관계로 문제를 정리할 수 있는 경우더라도, Held-Karp Algorithm(bitmask TSP)이나 각 bitmask를 정점으로 하는 (방향)그래프에서의 BFS 등 더 쉽고 직관적인 방법을 활용할 수 있는지도 생각해보는 것이 좋다. 쉬운 방법으로도 문제를 해결할 수 있다면, 특히 대회에서는 문제를 굳이 어려운 방법으로 해결할 필요는 없다.
글쓴이의 글에서 소개한 접근 방식은 아니지만(그림 없이 다차원 누적합을 묘사하기 귀찮아서 생략했다), SOS DP를 \(K\)차원의 누적 합과 차이배열로 설명하기도 한다. 이 또한 흥미로운 내용이므로 알아두면 좋다.
관련 문제
이 글에서 Submask Enumeration을 설명하기는 했으나, 굳이 SOS DP로 안 풀어도 되는 제한의 문제를 SOS DP로 해결하는 것을 막으려는 목적으로 설명을 한 것이다. 또한 이 글에서 Subset Convolution을 설명하기는 했으나, 어디까지나 \(O(K^22^K)\)의 문제풀이 예시로 보여주기 위해서 설명했을 뿐 그 활용은 이 글의 범위를 넘는다.
아래의 문제들은 SOS DP, AND Convolution, OR Convolution과 관련된 문제들이다. 몇몇 문제는 Generating Function(생성함수)의 개념이 익숙하지 않다면 어려울 수 있다.
자기 자신에 대한 AND Convolution과 OR Convolution으로 AND와 OR의 경우를 해결할 수 있다. XOR의 경우는 간단하므로 생략한다.
Sum Over Superset DP의 결과가 나타내는 것이 무엇인지를 잘 생각해보자.
각각의 guard에 대하여, 각 날 하루를 일했을 때의 \(H\)값을 초기값으로 넣고 Sum Over Subsets DP를 돌리면 나오는 결과가 무엇인지 생각해보자.
각 장난감 상자는 사용하지 않거나 사용하므로, 각각 장난감의 사용 여부로 Sum Over Subsets DP를 한다면 convolution을 이용하여 문제를 해결할 수 있을 것이다. 그러나 각 장난감에 대하여 Sum Over Subsets DP를 사용하는 것은 당연히 무리다. 이를 최적화할 수 있을까?
조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(1)
조건을 만족하려면 각 비트의 상태가 어때야 하는지를 잘 생각해보자(2)
원소의 개수가 가장 많은 공통부분집합이 무엇일까?
SOS DP와 그 역과정의 의미를 잘 생각해보자.
[BOJ25390] Traveling Junkman Problem
문제 풀이의 부분문제로 SOS DP가 사용될 수도 있다.
주어진 전체집합의 부분집합을 이용해 만들 수 있는 chain의 경우의 수를 구해보자.
참고 자료
https://codeforces.com/blog/entry/45223
https://usaco.guide/plat/dp-sos
https://qwerasdfzxcl.tistory.com/35
https://37zigen.com/subset-convolution/
https://www.acmicpc.net/blog/view/127
https://codeforces.com/blog/entry/92153
https://codeforces.com/blog/entry/115438