작은 집합으로 사용하는 비트마스크
부분집합을 정수로 표현합니다
작은 집합으로 사용하는 비트마스크은(는) CoddyKit의 무료 Coding Interview Prep 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 Coding Interview Prep 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
집합으로 사용하는 정수
하나의 정수로 전체 집합을 나타낼 수 있습니다. 비트 i가 1이면 원소 i가 집합에 포함된다는 뜻입니다. 이렇게 하면 부분집합을 작고 빠른 하나의 값에 담을 수 있습니다. 🎒
공집합과 전체 집합
숫자 0은 공집합이고, 가장 낮은 n개 비트가 모두 켜진 값은 모든 원소가 포함된 집합을 뜻합니다.
empty = 0
full = (1 << 4) - 1 # 0b1111, four elements원소 추가하기
집합에 원소 i를 추가하려면 해당 비트를 OR 연산으로 켜면 됩니다. 이는 한 원소와의 합집합으로 해석한 비트 설정과 정확히 같습니다.
s = 0
s |= (1 << 2) # add element 2원소 제거하기
원소 i를 제거하려면 반전된 비트와 AND 연산하세요. 해당 원소는 집합에서 빠지고 나머지는 그대로 유지됩니다. 이는 한 원소와의 집합 차집합입니다.
s &= ~(1 << 2) # remove element 2원소 포함 여부 확인하기
해당 원소의 비트와 AND 연산하여 원소 i가 포함되는지 확인합니다. 결과가 0이 아니면 그 원소는 집합의 원소입니다.
if s & (1 << 2):
print('2 is in the set')합집합과 교집합
두 마스크를 OR 연산하면 합집합이 되고, AND 연산하면 교집합이 됩니다. 전체 집합 연산을 각각 하나의 기계 명령어로 처리할 수 있습니다.
union = a | b
inter = a & b집합 크기는 1 비트 개수입니다
비트마스크의 원소 수는 설정된 비트의 개수와 같습니다. bit_count를 사용하면 크기를 즉시 얻을 수 있습니다.
size = mask.bit_count()모든 부분집합 순회하기
n개의 원소가 있으면 0부터 2의 n제곱 - 1까지의 정수가 모든 부분집합을 열거합니다. 간단한 범위 반복문 하나로 전부 순회할 수 있습니다.
for mask in range(1 << n):
pass # mask is one subset부분 마스크 빠르게 순회하기
주어진 마스크에 속한 부분집합만 방문하려면 고전적인 부분 마스크 반복문을 사용하세요. 각 부분집합을 내림차순으로 차례차례 방문합니다.
sub = mask
while sub:
sub = (sub - 1) & mask비트마스크 DP가 사용되는 곳
비트마스크는 외판원 문제처럼 많은 DP 문제에서 상태로 사용됩니다. 이때 마스크는 방문한 노드를 추적합니다.
n을 작게 유지하세요
부분집합이 2의 n제곱개이므로 이 기법은 보통 n이 약 20 이하인 작은 경우에만 실용적입니다. 그보다 커지면 개수가 폭발적으로 증가합니다. ⚠️
빠른 확인
마지막 집합과 마스크에 관한 질문입니다.
복습: 비트마스크 집합
하나의 정수에 집합을 저장하고, 마스크로 원소를 추가하거나 제거하며, 모든 부분집합을 순회할 수 있습니다. 이를 통해 빠른 비트마스크 DP를 사용할 수 있습니다. 🎉
자주 묻는 질문
“작은 집합으로 사용하는 비트마스크” 강의는 무료인가요?
네 — “작은 집합으로 사용하는 비트마스크” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 Coding Interview Prep 강의 전체를 잠금 해제할 수 있습니다. Coding Interview Prep 강의에는 총 4개의 강의가 포함되어 있습니다.
“작은 집합으로 사용하는 비트마스크”에서 뭘 배우나요?
부분집합을 정수로 표현합니다 브라우저에서 직접 실행하는 실습 코드로 Coding Interview Prep을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
Coding Interview Prep을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 Coding Interview Prep은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“작은 집합으로 사용하는 비트마스크” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 Coding Interview Prep 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 Coding Interview Prep 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.
이 강의의 모든 강의
- AND, OR, XOR와 시프트
- 비트 설정, 삭제와 토글
- 비트 개수와 최하위 설정 비트
- 작은 집합으로 사용하는 비트마스크