비트마스크

11723번 집합 https://www.acmicpc.net/problem/11723

11723번: 집합

 - 원래코드

import sys

s = set([])

for i in range(int(input())):
    cmds = list(sys.stdin.readline().split())

    if cmds[0] == "add":
        s.add(int(cmds[1]))
    elif cmds[0] == "remove":
        try:
            s.remove(int(cmds[1]))
        except:
            continue
    elif cmds[0] == "check":
        print(int(int(cmds[1]) in s))

    elif cmds[0] == "toggle":
        try:
            s.remove(int(cmds[1]))
        except:
            s.add(int(cmds[1]))
    elif cmds[0] == "all":
        s = set([x for x in range(1, 21)])
    elif cmds[0] == "empty":
        s = set([])

 

- 비트마스크

import sys

bit = 0b0

for i in range(int(input())):
    cmds = list(sys.stdin.readline().split())

    if cmds[0] == "add":
        bit = bit | (0b1 << int(cmds[1]))
    elif cmds[0] == "remove":
        bit = bit & ~(0b1 << int(cmds[1]))
    elif cmds[0] == "check":
        print(1 if bit & (0b1 << int(cmds[1])) else 0)
    elif cmds[0] == "toggle":
        bit = bit ^ (0b1 << int(cmds[1]))
    elif cmds[0] == "all":
        bit = 0b111111111111111111111
    elif cmds[0] == "empty":
        bit = 0b0

비트연산자를 사용하는 과정 자체는 중요하지 않다고 생각한다.

단 비트를 논리값으로 사용하면 편리한 경우가 있다. 

 

#14391번 종이 조각 https://www.acmicpc.net/problem/14391

14391번: 종이 조각

골드 레벨의 문제부터는 내장 라이브러리를 잘 사용하는게 좋을 듯 하다.

나중에는 itertools라는 라이브러리를 자세히 들여다보고 싶다.

 

이 문제를 처음 봤을 때 떠올린 방법은

Matrix를 논리값으로 표현해 방문기록을 하고

해당 논리값을 기준으로 연계산을 진행하면 된다고 판단했다.

 

문제는 방문기록을 하는 matrix를 모든 경우의 수에 맞춰 표현해야 한다는 점.

2차원 리스트를 순열로 뽑아내야 한다는 점이 너무 어려웠다.

 

그래서 차용된 아이디어가 비트이다.

비트를 2진수가 아니라 논리형 자료의 압축처럼 사용하는 것이다.

 

itertools 라이브러리를 통해서 matrix 내부 원소의 수 만큼 논리의 순열을 만들어 내고

각 순열속 1과 0을 논리값으로 사용해 계산을 진행하면 된다.

 

계산하는 아이디어는 주석으로 달려있다.

 

import itertools

N, M = map(int, input().split())
matrix = [[int(x) for x in input()] for _ in range(N)]

# 어려운 문제는 그냥 itertools를 사용하는 듯 하다.
a = itertools.product([0, 1], repeat=N*M)
# 1과 0을 논리값으로 사용한 형태라고 생각하자. 찢어서 나눌 수 있는 모든 경우의 수를 순열로 생성한다.

# 2차원으로 변경해주는 함수. 그동안 이걸 구현 못해서 해멨었지..
def to_matrix(l, m):
    return [l[i:i+m] for i in range(0, len(l), m)]


answer = 0
for x in a:
    bit_mask = to_matrix(x, M)

    tmp_r = 0
    for r in range(N):
        tmp = 0
        for c in range(M):
            if bit_mask[r][c] == 0:
                tmp = 10 * tmp + matrix[r][c]  
                # 수가 연달아 이어지면 자릿수가 늘어난다.
                # 때문에 이 전 저장 값에 10을 곱해주면
                # 숫자들이 왼쪽으로 한 칸씩 가겠지
            if bit_mask[r][c] == 1 or c == M-1:
                # 일종의 종료조건이다. 옳지 않은 값이 나오거나
                # 끝에 도달하면 저장한다.
                tmp_r += tmp
                tmp = 0
            # 이렇게 설계해야만 다음과 같은 경우를 해결할 수 있다.
            # ex) [ 1, 2, 3, 4 ] 가 (1, 2) 3 (4) 형태로 묶인 경우.
            # 각각의 묶음을 별도로 계산 후 더해준다.
            
    tmp_c = 0
    for c in range(M):
        tmp = 0
        for r in range(N):
            if bit_mask[r][c] == 1:
                tmp = 10 * tmp + matrix[r][c]
            if bit_mask[r][c] == 0 or r == N-1:
                tmp_c += tmp
                tmp = 0
    result = tmp_r + tmp_c

    answer = max(answer, result)

print(answer)