직접 풀어보자! 비트마스킹 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 비트 연산과 2ⁿ 순회, 그리고 비트 DP 세 갈래라냥. 1·2·3번으로 손을 풀고 4·5번으로 DP 를 맛보자냥.

비트마스킹 기본기

mask |= (1 << i)        # i 번째 비트 켜기 (넣기)
mask &= ~(1 << i)       # i 번째 비트 끄기 (빼기)
mask & (1 << i)         # i 번째가 켜졌냥? (확인)
mask ^= (1 << i)        # 켜짐/꺼짐 뒤집기 (토글)
for mask in range(1 << n):   # 모든 부분집합 훑기

미션 1비트로 만든 집합20분

여섯 가지 집합 연산을 비트마스크로 처리한다냥.

문제 풀러 가기

뼈대코드마다 비트 연산을 고른다냥

mask = 0
FULL = (1 << 20) - 1
for _ in range(q):
    code, x = map(int, input().split())
    if code == 1: mask |= 1 << (x - 1)
    elif code == 2: mask &= ~(1 << (x - 1))
    elif code == 3: out.append("1" if mask & (1 << (x - 1)) else "0")
    elif code == 4: mask ^= 1 << (x - 1)
    elif code == 5: mask = FULL
    elif code == 6: mask = 0

전체·비움 연산에서는 x 를 쓰지 말자냥.

5(전체) 와 6(비움) 은 x 가 0 으로 들어온다냥. 그때 1 << (x-1) 을 계산하면 1 << -1 이 되어 에러가 난다냥. 그러니 비트 계산은 x 를 쓰는 코드(1~4) 안에서만 하자냥.

출력이 많으니 print 를 매번 부르지 말고 리스트에 모아 한 번에 출력하자냥.

미션 2XOR이 목표가 되는 부분집합20분

부분집합의 XOR 이 k 가 되는 개수를 센다냥.

문제 풀러 가기

뼈대2ⁿ 부분집합을 훑는다냥

cnt = 0
for mask in range(1, 1 << n):    # 1 부터: 빈 집합 제외
    x = 0
    for i in range(n):
        if mask & (1 << i):
            x ^= nums[i]
    if x == k:
        cnt += 1

11장의 부분집합 완전탐색을 비트로 옮긴 거라냥. n 이 16까지라 2ⁿ 이 6만 5천쯤이라 넉넉하다냥.

빈 부분집합을 세면 안 된다냥.

mask 를 0 부터 돌리면 빈 집합(XOR 0)까지 센다냥. 크기 1 이상만 세야 하니 range(1, 1 << n) 으로 1 부터라냥. 특히 k 가 0 이면 빈 집합의 XOR 도 0 이라 하나가 더 세진다냥. 공개된 예시 뒤쪽이 이걸 확인해준다냥.

미션 3전부 켜는 부분집합15분

부분집합의 OR 이 전체 OR 과 같아지는 개수를 센다냥.

문제 풀러 가기

2번과 순회가 똑같다냥. ^= 를 |= 로 바꾸고, 목표를 "전체 OR" 로 두면 된다냥.

full = 0
for v in nums:
    full |= v

for mask in range(1, 1 << n):
    x = 0
    for i in range(n):
        if mask & (1 << i):
            x |= nums[i]
    if x == full:
        cnt += 1

먼저 전체를 OR 해서 목표 full 을 구해두는 게 핵심이라냥.

미션 4최소 개수로 전부 덮기25분

원소를 모두 덮는 최소 집합 수를 구한다냥.

문제 풀러 가기

뼈대덮은 원소 집합을 상태로 DP 라냥

각 집합을 비트마스크로 만들고, 덮은 원소들의 마스크를 상태로 둔다냥.

FULL = (1 << m) - 1
dp = [INF] * (1 << m)
dp[0] = 0
for state in range(1 << m):
    if dp[state] == INF: continue
    for sm in sets:              # 집합 하나를 더 쓰면
        ns = state | sm
        dp[ns] = min(dp[ns], dp[state] + 1)
print(-1 if dp[FULL] == INF else dp[FULL])

m 이 15까지라 상태가 2¹⁵ 로 3만 개쯤이라 충분하다냥.

그리디로 풀면 틀린다냥.

"매번 새로 덮는 게 가장 많은 집합" 을 고르는 그리디는 그럴듯하지만 최소가 아니다냥. 큰 집합을 먼저 집었다가 나머지를 비효율적으로 덮게 될 수 있다냥.

숨겨진 테스트에 그런 경우가 있다냥 — 그리디는 3개, 정답은 2개라냥. 반드시 DP 로 최소를 찾자냥.

미션 5일 나눠주기25분

각 사람에게 서로 다른 일을 맡길 때 최소 비용을 구한다냥.

문제 풀러 가기

뼈대맡긴 일 집합을 상태로 DP 라냥

dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    if dp[mask] == INF: continue
    worker = bin(mask).count("1")   # 켜진 비트 수 = 다음 사람 번호
    if worker >= n: continue
    for job in range(n):
        if mask & (1 << job): continue
        nxt = mask | (1 << job)
        dp[nxt] = min(dp[nxt], dp[mask] + cost[worker][job])
print(dp[(1 << n) - 1])

사람 번호 = 켜진 비트 수라냥.

mask 에 켜진 비트 수가 곧 "이미 일을 맡은 사람 수" 라, 다음에 일을 맡을 사람의 번호라냥. bin(mask).count("1") 로 켜진 비트를 센다냥.

그래서 사람을 따로 추적할 필요 없이 마스크 하나로 다 된다냥. n 이 15까지라 상태가 3만 개쯤이라 충분하다냥.

다섯 개 다 풀었냥? 비트마스킹은 집합을 정수 하나로 다루는 발상 전환이라냥. 익숙해지면 부분집합 완전탐색과 비트 DP 가 한결 깔끔해진다냥.

다음은 트라이라냥. 문자열을 글자마다 갈라지는 나무에 담아서, 접두사 검색을 아주 빠르게 하는 자료구조라냥. 정말 수고했다냥~

직접 풀어보자! 비트마스킹 5문제

안녕, 나 코딩냥이다냥! 오늘 문제는 비트 연산과 2ⁿ 순회, 그리고 비트 DP 세 갈래라냥. 1·2·3번으로 손을 풀고 4·5번으로 DP 를 맛보자냥.

비트마스킹 기본기

mask |= (1 << i)        # i 번째 비트 켜기 (넣기)
mask &= ~(1 << i)       # i 번째 비트 끄기 (빼기)
mask & (1 << i)         # i 번째가 켜졌냥? (확인)
mask ^= (1 << i)        # 켜짐/꺼짐 뒤집기 (토글)
for mask in range(1 << n):   # 모든 부분집합 훑기

미션 1비트로 만든 집합20분

여섯 가지 집합 연산을 비트마스크로 처리한다냥.

문제 풀러 가기

뼈대코드마다 비트 연산을 고른다냥

mask = 0
FULL = (1 << 20) - 1
for _ in range(q):
    code, x = map(int, input().split())
    if code == 1: mask |= 1 << (x - 1)
    elif code == 2: mask &= ~(1 << (x - 1))
    elif code == 3: out.append("1" if mask & (1 << (x - 1)) else "0")
    elif code == 4: mask ^= 1 << (x - 1)
    elif code == 5: mask = FULL
    elif code == 6: mask = 0

전체·비움 연산에서는 x 를 쓰지 말자냥.

출력이 많으니 print 를 매번 부르지 말고 리스트에 모아 한 번에 출력하자냥.

미션 2XOR이 목표가 되는 부분집합20분

부분집합의 XOR 이 k 가 되는 개수를 센다냥.

문제 풀러 가기

뼈대2ⁿ 부분집합을 훑는다냥

cnt = 0
for mask in range(1, 1 << n):    # 1 부터: 빈 집합 제외
    x = 0
    for i in range(n):
        if mask & (1 << i):
            x ^= nums[i]
    if x == k:
        cnt += 1

11장의 부분집합 완전탐색을 비트로 옮긴 거라냥. n 이 16까지라 2ⁿ 이 6만 5천쯤이라 넉넉하다냥.

빈 부분집합을 세면 안 된다냥.

미션 3전부 켜는 부분집합15분

부분집합의 OR 이 전체 OR 과 같아지는 개수를 센다냥.

문제 풀러 가기

2번과 순회가 똑같다냥. ^= 를 |= 로 바꾸고, 목표를 "전체 OR" 로 두면 된다냥.

full = 0
for v in nums:
    full |= v

for mask in range(1, 1 << n):
    x = 0
    for i in range(n):
        if mask & (1 << i):
            x |= nums[i]
    if x == full:
        cnt += 1

먼저 전체를 OR 해서 목표 full 을 구해두는 게 핵심이라냥.

미션 4최소 개수로 전부 덮기25분

원소를 모두 덮는 최소 집합 수를 구한다냥.

문제 풀러 가기

뼈대덮은 원소 집합을 상태로 DP 라냥

각 집합을 비트마스크로 만들고, 덮은 원소들의 마스크를 상태로 둔다냥.

FULL = (1 << m) - 1
dp = [INF] * (1 << m)
dp[0] = 0
for state in range(1 << m):
    if dp[state] == INF: continue
    for sm in sets:              # 집합 하나를 더 쓰면
        ns = state | sm
        dp[ns] = min(dp[ns], dp[state] + 1)
print(-1 if dp[FULL] == INF else dp[FULL])

m 이 15까지라 상태가 2¹⁵ 로 3만 개쯤이라 충분하다냥.

그리디로 풀면 틀린다냥.

숨겨진 테스트에 그런 경우가 있다냥 — 그리디는 3개, 정답은 2개라냥. 반드시 DP 로 최소를 찾자냥.

미션 5일 나눠주기25분

각 사람에게 서로 다른 일을 맡길 때 최소 비용을 구한다냥.

문제 풀러 가기

뼈대맡긴 일 집합을 상태로 DP 라냥

dp = [INF] * (1 << n)
dp[0] = 0
for mask in range(1 << n):
    if dp[mask] == INF: continue
    worker = bin(mask).count("1")   # 켜진 비트 수 = 다음 사람 번호
    if worker >= n: continue
    for job in range(n):
        if mask & (1 << job): continue
        nxt = mask | (1 << job)
        dp[nxt] = min(dp[nxt], dp[mask] + cost[worker][job])
print(dp[(1 << n) - 1])

사람 번호 = 켜진 비트 수라냥.

mask 에 켜진 비트 수가 곧 "이미 일을 맡은 사람 수" 라, 다음에 일을 맡을 사람의 번호라냥. bin(mask).count("1") 로 켜진 비트를 센다냥.

그래서 사람을 따로 추적할 필요 없이 마스크 하나로 다 된다냥. n 이 15까지라 상태가 3만 개쯤이라 충분하다냥.

다섯 개 다 풀었냥? 비트마스킹은 집합을 정수 하나로 다루는 발상 전환이라냥. 익숙해지면 부분집합 완전탐색과 비트 DP 가 한결 깔끔해진다냥.

다음은 트라이라냥. 문자열을 글자마다 갈라지는 나무에 담아서, 접두사 검색을 아주 빠르게 하는 자료구조라냥. 정말 수고했다냥~