연습 문제

이 장의 문제 다섯 개는 앞에서 본 XOR 성질, popcount, 비트마스크 집합, 비트마스크 DP를 하나씩 연습하도록 만든 것입니다. 먼저 스스로 풀어 본 뒤 접근 방법과 Python 풀이를 확인하세요.

문제 1. 짝 없는 출입증

출입 기록에는 직원의 출입증 번호가 들어올 때 한 번, 나갈 때 한 번 남습니다. 그런데 한 사람만 아직 나가지 않아 그 번호만 한 번 기록되어 있습니다. 번호 목록이 주어질 때 아직 안에 있는 사람의 번호를 O(n) 시간, O(1) 추가 공간으로 찾으세요.

접근: a ^ a == 0, a ^ 0 == a이고 XOR은 순서와 상관없으므로 전부 XOR 하면 두 번 나온 번호는 사라지고 한 번 나온 번호만 남습니다. 해시 집합을 쓰면 O(n) 공간이 필요하지만 XOR은 변수 하나면 됩니다.

from functools import reduce
from operator import xor


def still_inside(badges: list[int]) -> int:
    return reduce(xor, badges, 0)


print(still_inside([7, 3, 9, 3, 7]))   # 9

문제 2. 비트 수 표

정수 n이 주어질 때 0부터 n까지 각 수의 켜진 비트 수를 담은 리스트를 만드세요. 각 수를 따로 세지 말고 전체를 O(n)에 채워야 합니다.

접근: i >> 1은 i에서 최하위 비트를 떼어 낸 수이고 i보다 작으므로 이미 계산되어 있습니다. 따라서 bits[i] = bits[i >> 1] + (i & 1)입니다. bits[i] = bits[i & (i - 1)] + 1도 같은 결과를 냅니다.

def bit_table(n: int) -> list[int]:
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits


print(bit_table(8))   # [0, 1, 1, 2, 1, 2, 2, 3, 1]
assert bit_table(1000) == [i.bit_count() for i in range(1001)]

문제 3. 한 칸씩 바뀌는 스위치

n개의 스위치를 모두 끈 상태에서 시작해, 한 번에 스위치 하나만 바꾸면서 2^n가지 상태를 한 번씩 모두 거치는 순서를 출력하세요. 이런 순서를 그레이 코드(Gray code)라고 합니다.

접근: i번째 상태를 i ^ (i >> 1)로 만들면 이웃한 두 상태가 정확히 한 비트만 다릅니다. i에서 i + 1로 갈 때 바뀌는 비트 묶음과 그것을 한 칸 민 묶음을 XOR 하면 맨 위 한 비트만 남기 때문입니다. 검증은 이웃끼리 XOR 한 값의 popcount가 1인지로 합니다.

def gray_code(n: int) -> list[int]:
    return [i ^ (i >> 1) for i in range(1 << n)]


codes = gray_code(3)
print([format(c, "03b") for c in codes])
assert len(set(codes)) == 8
assert all((a ^ b).bit_count() == 1 for a, b in zip(codes, codes[1:]))

문제 4. 모든 기술을 갖춘 최소 비용 팀

프로젝트에 필요한 기술이 k개(k ≤ 12) 있고, 후보 m명이 있습니다. 후보마다 가진 기술의 목록과 비용이 주어집니다. 팀원들의 기술을 합쳐 k개를 모두 갖추는 최소 비용을 구하세요. 불가능하면 -1을 출력합니다.

접근: 기술 집합을 k비트 마스크로 바꿉니다. dp[mask]를 "mask의 기술을 모두 갖추는 최소 비용"으로 두면, 후보 한 명을 더할 때 dp[mask | skill] = min(dp[mask | skill], dp[mask] + cost)입니다. 후보마다 모든 마스크를 갱신하면 O(m * 2^k)입니다. 같은 후보를 두 번 넣어도 OR 결과가 같아 비용만 늘어나므로 답에는 영향이 없습니다.

def min_team_cost(k: int, candidates: list[tuple[list[int], int]]) -> int:
    full = (1 << k) - 1
    INF = float("inf")
    dp = [INF] * (1 << k)
    dp[0] = 0
    for skills, cost in candidates:
        skill_mask = 0
        for s in skills:
            skill_mask |= 1 << s
        for mask in range(1 << k):
            if dp[mask] + cost < dp[mask | skill_mask]:
                dp[mask | skill_mask] = dp[mask] + cost
    return -1 if dp[full] == INF else dp[full]


people = [([0, 1], 5), ([2], 3), ([1, 2, 3], 7), ([3], 2), ([0], 1)]
print(min_team_cost(4, people))   # 8: [0] + [1, 2, 3]

문제 5. 빠진 좌석 번호

공연장 좌석 번호는 0부터 n까지인데, 판매 목록에는 n개의 번호만 순서 없이 들어 있습니다. 빠진 번호 하나를 O(n) 시간, O(1) 추가 공간으로 찾으세요. 합을 이용하는 방법도 있지만 고정 폭 정수를 쓰는 언어에서는 오버플로를 걱정해야 합니다.

접근: 0부터 n까지의 모든 수와 목록의 모든 수를 함께 XOR 하면, 양쪽에 다 있는 번호는 짝을 이뤄 사라지고 빠진 번호만 남습니다. XOR은 값을 키우지 않으므로 오버플로가 없습니다.

def missing_seat(sold: list[int]) -> int:
    result = len(sold)              # n
    for i, seat in enumerate(sold):
        result ^= i ^ seat
    return result


print(missing_seat([3, 0, 1]))        # 2
print(missing_seat([0, 1, 2, 4, 5]))  # 3

정리

XOR은 짝을 지우고, i >> 1과 i & 1은 이전 결과를 재사용하게 해 주며, i ^ (i >> 1)은 한 비트씩 바뀌는 순서를 만들고, 마스크를 배열 인덱스로 쓰면 집합 상태의 DP가 됩니다. 문제를 볼 때 "원소가 20개 이하인가", "짝을 이루는가", "켜짐/꺼짐 상태인가"를 먼저 물어보면 비트 연산을 쓸 자리가 보입니다.