비트마스크 부분집합 열거

n개 항목의 모든 부분집합은 하나의 정수로 나타낼 수 있습니다. 0부터 세어 올라가면 각 정수의 비트가 어떤 항목을 포함할지 정확히 선택합니다. 🙂

n개의 항목으로 이루어진 집합에는 2^n개의 부분집합이 있습니다. 따라서 정수를 0부터 2^n에서 1을 뺀 값까지 순회하면 모든 부분집합을 정확히 한 번씩 방문하게 됩니다.

시프트 연산 1 << n은 2의 n제곱과 같습니다. 부분집합을 순회할 때 상한을 표현하는 가장 간결하고 빠른 방법입니다.

항목 i가 부분집합에 포함되어 있는지 확인하려면 mask와 i만큼 왼쪽으로 시프트한 1을 사용해 해당 비트를 검사합니다. 결과가 0이 아니면 항목이 포함된 것입니다.

각 비트 위치를 살펴보면서 비트가 설정된 항목을 모읍니다. 그러면 하나의 마스크를 그 마스크가 나타내는 실제 부분집합으로 바꿀 수 있습니다.

마스크 0은 공집합이고, 모든 비트가 1인 마스크는 전체 집합입니다. 순회 과정에서 모든 값을 다루므로 두 경우 모두 별도의 처리 없이 포함됩니다.

반복문 안에서 선택된 항목을 더해 각 부분집합의 점수를 계산합니다. 이는 여러 작은 완전 탐색 풀이의 핵심입니다.

선택된 항목의 수는 마스크의 설정된 비트 수와 같습니다. Python에서는 bin(mask).count('1')로 즉시 구할 수 있습니다.

부분집합이 2^n개이므로 이 기법은 작은 n에만 적합합니다. 모든 경우를 열거할 때 실용적인 상한은 대략 n이 20인 경우입니다.

하나의 정수 반복문으로 복잡한 중첩 반복문을 대신할 수 있고, 비트 연산은 빠릅니다. 코드가 짧고 명확하며 테스트하기도 쉽습니다.

마스크를 순회하고, 비트를 해석하고, 부분집합의 점수를 계산한 다음 최댓값을 추적합니다. 이 틀을 기억해 두면 많은 부분집합 문제가 일상적인 문제처럼 풀립니다.

mask로 표현된 부분집합에 항목 i가 포함되어 있는지 검사하려고 합니다.

마스크를 0부터 2^n에서 1을 뺀 값까지 순회하고, mask와 왼쪽으로 시프트한 1로 비트를 읽은 뒤 각 부분집합의 점수를 계산합니다. 작은 n에 적합한 깔끔한 완전 탐색입니다. 🚀