본문 바로가기
카테고리 없음

비트마스킹: 효율적인 상태 관리의 비밀

by xylavo 2025. 4. 27.

알고리즘과 코딩 테스트에서 우리는 종종 여러 상태를 효율적으로 관리해야 하는 상황을 마주합니다. 컴퓨터의 가장 기본 연산 단위인 비트를 활용한 비트마스킹은 이러한 상황에서 강력한 도구가 됩니다.

비트마스킹의 정의

비트마스킹(Bit Masking)은 이진수의 각 자리(비트)를 하나의 상태로 활용하여 여러 상태를 효율적으로 표현하고 관리하는 기법입니다. 컴퓨터는 내부적으로 모든 데이터를 0과 1의 비트로 처리하는데, 비트마스킹은 이러한 컴퓨터의 특성을 활용하여 메모리와 연산 효율을 극대화합니다.

비트마스킹의 핵심 아이디어는 하나의 정수 변수를 마치 불리언(Boolean) 값의 배열처럼 사용하는 것입니다. 예를 들어, 32비트 정수는 32개의 독립적인 상태(켜짐/꺼짐, 포함/미포함 등)를 표현할 수 있습니다. 각 비트 위치는 2의 거듭제곱(1, 2, 4, 8, ...)의 값을 가지며, 이를 이용해 특정 원소의 포함 여부를 나타낼 수 있습니다.

비트마스킹이 특히 유용한 이유는 비트 단위 연산(비트 연산)이 매우 빠르기 때문입니다. AND(&), OR(|), XOR(^), NOT(~), 왼쪽 시프트(<<), 오른쪽 시프트(>>) 등의 비트 연산자를 사용하면 집합의 합집합, 교집합, 차집합 등의 연산을 O(1) 시간에 수행할 수 있습니다. 이는 배열이나 리스트를 사용할 때 발생하는 선형 시간 복잡도보다 훨씬 효율적입니다.

또한 비트마스킹은 메모리 사용량을 극적으로 줄일 수 있습니다. 예를 들어, 20개의 원소가 있는 집합을 표현하기 위해 일반적인 배열은 최소 20바이트가 필요하지만, 비트마스킹을 사용하면 단 4바이트(32비트 정수)만으로 충분합니다. 이러한 메모리 효율성은 제한된 자원에서 실행되는 프로그램이나 대규모 데이터를 처리해야 하는 상황에서 큰 장점이 됩니다.

비트마스킹의 구현 방법

비트마스킹을 효과적으로 활용하려면 비트 연산자에 대한 이해가 필수적입니다. 다음은 프로그래밍에서 자주 사용되는 비트 연산자와 그 활용법입니다.

기본 비트 연산자

  1. AND 연산 (&): 두 비트가 모두 1일 때만 1을 반환합니다. 특정 비트가 켜져 있는지 확인하는 데 사용됩니다.
    if (mask & (1 << i)) // i번째 비트가 켜져 있는지 확인
  2. OR 연산 (|): 두 비트 중 하나라도 1이면 1을 반환합니다. 특정 비트를 켜는 데 사용됩니다.
    mask |= (1 << i); // i번째 비트를 켬
  3. XOR 연산 (^): 두 비트가 다를 때 1을 반환합니다. 특정 비트를 토글(반전)하는 데 사용됩니다.
    mask ^= (1 << i); // i번째 비트를 토글
  4. NOT 연산 (~): 비트를 반전시킵니다. 모든 비트를 반전할 때 사용됩니다.
    mask = ~mask; // 모든 비트를 반전
  5. 왼쪽 시프트 (<<): 비트를 왼쪽으로 이동시킵니다. 2의 거듭제곱 값을 생성할 때 사용됩니다.
    int bit = 1 << i; // 2^i 값 생성
  6. 오른쪽 시프트 (>>): 비트를 오른쪽으로 이동시킵니다. 숫자를 2로 나눌 때 사용됩니다.
    mask >> 1; // mask를 2로 나눈 값

비트마스킹 기본 연산

  1. 비트 켜기: mask |= (1 << i)
  2. 비트 끄기: mask &= ~(1 << i)
  3. 비트 토글하기: mask ^= (1 << i)
  4. 비트 상태 확인하기: if (mask & (1 << i))
  5. 최하위 켜진 비트 찾기: int lsb = mask & -mask
  6. 최하위 켜진 비트 끄기: mask &= (mask - 1)
  7. 모든 부분집합 순회하기: 
    for (int subset = mask; subset; subset = (subset - 1) & mask) {    // subset은 mask의 부분집합}

이러한 연산들은 대부분 O(1) 시간에 수행되므로, 상태 전환이나 집합 연산을 매우 빠르게 처리할 수 있습니다. 비트마스킹은 특히 동적 프로그래밍에서 상태를 메모이제이션할 때, 그래프 알고리즘에서 방문 상태를 기록할 때, 그리고 조합 문제에서 모든 가능한 경우를 효율적으로 탐색할 때 유용하게 활용됩니다.

백준 비트마스킹 추천 문제

비트마스킹에 대한 이해와 활용 능력을 키우기 위해 다음과 같은 백준 문제들을 추천합니다. 난이도 순으로 정리했으니 단계적으로 도전해보세요.

입문 단계

  1. 백준 11723번 - 집합
    • 간단한 집합 연산을 비트마스킹으로 구현하는 문제
    • 비트마스킹의 기본 연산(추가, 삭제, 확인, 토글, 전체 설정, 전체 해제)을 연습하기 좋음

중급 단계

  1. 백준 2098번 - 외판원 순회
    • 전형적인 TSP(Traveling Salesman Problem) 문제
    • 비트마스킹과 다이나믹 프로그래밍을 결합한 대표적인 예시
  2. 백준 1562번 - 계단 수
    • 0부터 9까지의 숫자가 모두 등장하는 계단 수의 개수를 구하는 문제
    • 상태를 비트마스크로 표현하여 DP로 해결하는 좋은 예시

고급 단계

  1. 백준 1311번 - 할 일 정하기 1
    • N명의 사람과 N개의 일이 있을 때, 각 일을 한 명씩 배정하여 비용의 합을 최소화하는 문제
    • 비트마스킹 DP의 전형적인 응용 사례
  2. 백준 17453번 - 두 개의 문
    • 스위치와 전구 상태 관리를 비트마스킹으로 해결하는 문제
    • XOR 연산을 활용하는 비트마스킹의 응용

각 문제를 풀면서 비트마스킹의 다양한 응용법을 익히고, 코드의 효율성을 높이는 방법을 배울 수 있습니다. 실제 코딩테스트에서도 비슷한 유형의 문제가 자주 출제되므로, 이러한 문제들을 통해 비트마스킹 기법을 완벽하게 마스터하시길 바랍니다.

티스토리툴바