비트 연산으로 조합구하기

 

'1 ~ 10 의 수들 중 숫자 3개 뽑기' 와 같은 조합의 개념을 물어보는 문제들이 많은데,

이는 쉽게 백트래킹을 이용해서 구할 수 있다.

다만, 1 ~ 10 의 수들 중 뽑을 수 있는 카드의 경우의 수를 구해라 하면 조금 문제가 복잡해진다. 

 

이런 경우에 쉽게 해당 경우의 수를 구할 수 있는 방법을 공부해보았다

 

 

 

비트 마스킹 이라는 기법이다.

 

예시로, 1, 2, 3 의 3가지 수에 대해서 모든 가능한 카드를 뽑는 방법은 2 * 2 * 2 이다. (2는 해당 카드를 뽑거나 안뽑을 경우의 수)

2 * 2 * 2를 조금 sparse하게 펼쳐보면

000 이라는 3개의 숫자로 표현이 가능하다. 

 

예를 들어 1, 2번을 뽑을꺼다?! -> 110

3번만 뽑겠다? -> 001

 

그렇다면, 1, 2, 3의 3가지 수에 대해 모든 가능한 카드를 뽑는 방법 즉 조합은, 000 ~ 111 까지의 8개의 경우의 수로 표현 할 수 있는 것이다.

 

000 ~ 111 까지의 0과 1로만 표현되어 있는 모든 수에서 1이라고 표현되어 있는 곳의 자리수가 결국 뽑는 인덱스와 같은거다

 

예를 들어. 위에서 뽑을 때와 마찬가지로

 

110 에서는, 1번과 2번을 뽑는거고

001 에서는 , 3번의 카드만 뽑는 조합이 나오는 것이다.

 

이를 코드로 나타내 보면,

 

def bitnum(n):
    combinations = []
    # n이 3이면, 1<<n 은 3을 비트로 바꾼 것으로 2^3이 된다.
    for mask in range(1 << n):
        combination = []
        # 3개의 자리 중, 해당 자리가 1인지 0인지 확인해보는 것
        for j in range(n):
          # 이 값이 1이라면, 해당 자리는 0이 아닌 1으로 조합에 추가해준다
            if (mask & (1 << j)) != 0:
                combination.append(j)
        combinations.append(combination)

    return combinations


combi = bitnum(3)
combi.sort(key=lambda x: len(x))
print(combi)

결과: [[], [0], [1], [2], [0, 1], [0, 2], [1, 2], [0, 1, 2]]

 

 

모든 조합 구하기 완성!

 

 

관련 문제는 요 문제 추천한다!!

https://www.acmicpc.net/problem/17471

17471번: 게리맨더링

 

끘!!