[COS PRO 1급 문제 회고] 비트마스크로 모든 부분집합의 합 구하기

Cos Pro 자격시험

MOS 공식 사이트, COS 공식 사이트, COS Pro 공식 사이트, DATA 공식 사이트

Cos Pro

Cos Pro에 비트연산 문제가 나왔는데, 굉장히 신박했다.

알고리즘 테스트에 이런게 나오다니... 대학교 중간, 기말고사에나 나올법한 문제다.

덕택에 시간과 점수를 오지게 깎였다. 900점 넘기는게 목표였는데 달성 실패 ㅅㅂ

그냥 나는 COS PRO라는 시험이랑 안맞는것 같다. 앞으로 다시는 안 볼것 같다.

이번에도 한문제인가 두문제 빼고 못풀었는데(이문제 때문에 시간 다깎아먹음 ㅡㅡ 이것만 없었어도 풀었음) 점수가 개판이다.

여하튼 비트마스크를 사용하면 Combination O(N^3) 대신 O(N^2)로 부분집합의 모든 합을 구할 수 있다.

 

원리는 아래와 같이 간단하다.

만약 배열 길이가 3이면

1 << 3의 범위는 0~2^4가 된다.

즉 0000~0111까지인데. 1인 경우 해당 인덱스를 사용한다 생각하면 된다.

그리고 마스크를 100 010 001 이렇게 3개를 적용해본다.

& 해서 1이 나오면 해당 인덱스를 사용하면 된다.

비트마스크의 원리

만약 비트연산을 써먹은지 오래됐다면, 위와 같은 생각을 떠올리는데만 꽤 많은 시간이 걸릴 것이다.

코드로 구현하는건 그 다음이다.

이걸 5분만에 해야 모든 문제 10개를 다풀수있다. 

무슨 생각으로 이런 문제를 내는지 모르겠다.

 

어쨌든, 위에 주절주절 적은걸 코드로 옮기면 아래와 같이 된다.

def solution(arr, N):
    answer = 0
    for bit in range(1 << N): # 2^N
        temp = 0
        for maskIdx in range(N):
            if ((bit & (1 << maskIdx)) >> maskIdx) == 1:
                temp += arr[maskIdx]
        answer += temp
    return answer



assert solution([1, 2, 3], 3) == (1+2+3+sum([1, 2]) +
                                  sum([1, 3])+sum([2, 3])+sum([1, 2, 3]))  # 24
assert solution([1, 2], 2) == (1 + 2 + sum([1, 2]))  # 5

효율적인 알고리즘을 하나 알았고 (O(n^3) > O(n^2))

비트연산에 대한 복습 & 심화학습을 할 수 있었던 시간이었다.