hongjunland

Welcome

2 분 소요

학습목표

  • 비트마스크 개념에 대해 설명할 수 있다.
  • 비트마스크를 쓰는 이유에 대해 설명할 수 있다.
  • 비트마스크의 적용 예시에 대해서 설명할 수 있다.

기존에 공부했었던 개념이였지만, 자주 쓰지 않다보니 잊어버리는 현상이 일어나서 다시 상기하고자 글을 써본다.

1. 비트마스크(Bitmask)란?

  • 용어 그대로 비트(bit)와 같이 이진수(binary digit)의 형태로 집합을 표현한 방식이다. 알고리즘이라기 보단 테크닉에 가깝다.
  • 보통 비트가 1이면 “선택 되었다”, 0이면 “선택되지 않았다”라고 말한다.

2. 비트마스크의 장점

  • 수행시간이 빠름

    연산은 bit연산을 사용하기 때문에 수행시간은 O(1).

  • 코드가 비교적 간결

    다양한 집합 연산들을 비트연산자 1줄로 작성할 수 있기 때문에, 반복문, 조건문등을 이용한 기존 코드보다 간결해짐.

  • 메모리 사용량 절약(중요)

    N개의 원소가 있다면, 다른 자료구조인 경우 2^N개의 공간을 만들어야 하는 경우가 있다. 그러나 비트마스크는 2^N가지의 경우를 10비트의 이진수하나로 표현 가능하다.

3. 적용 방식

  • 기본 논리연산(AND, OR등)은 안다고 가정한다.

3.1 집합 구현

  • 원소의 개수 N, 해당 원소가 k번째라 가정한다.

    연산 적용
    꽉찬집합 B = (1« N)-1
    원소 추가 B |= (1« k)
    원소 삭제 B &= ~(1« k)
    포함 여부 if(A & (1« k))
    토글 B ^= (1 « k)
    집합크기 B%2 + bitCount(B/2)
    집합크기(라이브러리) Integer.bitCount(B)
    최소원소 B & (-B);
    최소원소제거 B &= (B-1);

  • 모든 집합 순회

              for(int i = 0 ; i < (1<<N) ; i++){
              // 부분집합 순서
              for(int j = 0 ; j < N ; j++){
                  if((i& 1 <<j) != 0){
                      // 부분집합
                  }
              }

4. 적용 예시 (백준 1182번) -java

제한

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2초 256MB 44010 20272 12920 44.189%

문제

N개의 정수로 이루어진 수열이 있을 때, 크기가 양수인 부분수열 중에서 그 수열의 원소를 다 더한 값이 S가 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.

출력

첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.

풀이

부분집합에 대해서 해당 조건이 맞는지만 판별하면 된다.
20C10 < 2*10^8 이므로 수행시간도 넉넉한 편이다.


import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int N;       // 집합크기
    static int S;       // 조건 값
    static int[] nums;  // 집합배열
    static int Result = 0;  // 조건에 맞는 집합 개수
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        S = Integer.parseInt(st.nextToken());
        st = new StringTokenizer(br.readLine());
        nums = new int[N];
        for(int i = 0 ; i < N ; i++){
            nums[i] = Integer.parseInt(st.nextToken());
        }
        for(int i = 1 ; i < (1<<N) ; i++){
            int sum = 0;
            for(int j = 0 ; j < N ; j++){
                if((i& 1 <<j) != 0){
                    sum+=nums[j];
                }
            }
            if(sum==S) Result++;
        }
        System.out.println(Result);
    }
}

참고