부분 마스크 열거¶

주어진 마스크의 모든 부분 마스크 열거하기¶

비트마스크 $m$이 주어졌을 때, 그 모든 부분 마스크, 즉 마스크 $m$에 포함된 비트만 켜져 있는 마스크 $s$를 효율적으로 순회하고자 합니다.

비트 연산 기법에 기반한 이 알고리즘의 구현을 살펴봅시다:

int s = m;
while (s > 0) {
 ... you can use s ...
 s = (s-1) & m;
}

또는 더 간결한 for 문을 사용하면 다음과 같습니다:

for (int s=m; s; s=(s-1)&m)
 ... you can use s ...

두 코드 모두에서 0과 같은 부분 마스크는 처리되지 않습니다. 이를 루프 밖에서 따로 처리하거나, 덜 우아한 구조를 사용할 수 있습니다. 예를 들면 다음과 같습니다:

for (int s=m; ; s=(s-1)&m) {
 ... you can use s ...
 if (s==0)  break;
}

위 코드가 $m$의 모든 부분 마스크를 중복 없이 내림차순으로 방문하는 이유를 살펴봅시다.

현재 비트마스크 $s$가 있고, 다음 비트마스크로 넘어가고자 한다고 가정합시다. 마스크 $s$에서 1을 빼면 가장 오른쪽의 켜진 비트가 제거되고, 그 오른쪽의 모든 비트는 1이 됩니다. 그런 다음 마스크 $m$에 포함되지 않아 부분 마스크의 일부가 될 수 없는 "여분의" 1 비트를 모두 제거합니다. 이 제거는 비트 연산 (s-1) & m을 사용하여 수행합니다. 그 결과, 마스크 $s-1$을 "잘라내어" 그것이 가질 수 있는 가장 큰 값, 즉 내림차순에서 $s$ 다음에 오는 부분 마스크를 구하게 됩니다.

따라서 이 알고리즘은 반복마다 단 두 번의 연산만 수행하면서 이 마스크의 모든 부분 마스크를 내림차순으로 생성합니다.

특별한 경우는 $s = 0$일 때입니다. $s-1$을 실행하면 모든 비트가 켜진 마스크(-1의 비트 표현)를 얻게 되고, (s-1) & m 이후에는 $s$가 $m$과 같아집니다. 따라서 마스크 $s = 0$에 주의하십시오 — 루프가 0에서 끝나지 않으면 알고리즘이 무한 루프에 빠질 수 있습니다.

모든 마스크와 그 부분 마스크를 순회하기. 복잡도 $O(3^n)$¶

많은 문제, 특히 비트마스크 동적 계획법을 사용하는 문제에서는 모든 비트마스크를 순회하면서 각 마스크마다 그 모든 부분 마스크를 순회해야 합니다:

for (int m=0; m<(1<<n); ++m)
    for (int s=m; s; s=(s-1)&m)
 ... s and m ...

내부 루프가 총 $O(3^n)$번 반복됨을 증명해 봅시다.

첫 번째 증명: $i$번째 비트를 생각해 봅시다. 이 비트에는 정확히 세 가지 경우가 있습니다:

마스크 $m$에 포함되지 않는 경우(따라서 부분 마스크 $s$에도 포함되지 않음),
$m$에는 포함되지만 $s$에는 포함되지 않는 경우, 또는
$m$과 $s$ 모두에 포함되는 경우입니다.

비트는 총 $n$개이므로 서로 다른 조합은 $3^n$개가 됩니다.

두 번째 증명: 마스크 $m$에 켜진 비트가 $k$개 있다면, 부분 마스크는 $2^k$개가 된다는 점에 주목하십시오. 켜진 비트가 $k$개인 마스크는 총 $\binom{n}{k}$개이므로(이항 계수 참고), 모든 마스크에 대한 조합의 총 개수는 다음과 같습니다:

$$\sum_{k=0}^n \binom{n}{k} \cdot 2^k$$

이 수를 계산하기 위해, 위의 합이 이항 정리를 이용한 $(1+2)^n$의 전개와 같다는 점에 주목하십시오. 따라서 증명하고자 한 대로 $3^n$개의 조합이 있습니다.

부분 마스크 열거¶

주어진 마스크의 모든 부분 마스크 열거하기¶

모든 마스크와 그 부분 마스크를 순회하기. 복잡도 $O(3^n)$¶

연습 문제¶