백준 1311번: 할 일 정하기 1 (Python, PyPy3)

접근

이번 문제를 풀면서 비트마스크, 비트연산이 무엇인지 공부해보는 계기가 되었다.

비트란 컴퓨터에서 다루는 최소 단위이며, 0과 1이 하나의 비트가 될 수 있다. 0과 1이 각각 False 와 True 를 의미하는 것을 이용하여 어떤 여러가지의 요소들이 True 와 False 상태인 것을 이진수로 표현함으로써, 비트 연산을 통해 문제를 해결해나가는 기술을 비트마스크라고 한다.. 고 한다.

예를 들어 5개의 요소가 있다고 할 때 2, 4 번째 요소를 이미 선택했다면 이를 01010 이라는 이진수로 표현할 수 있다. 이때 첫번째 요소를 추가로 선택했을 때 이를 비트연산으로 계산하여 11010 으로 쉽게 계산할 수 있다는 말이다.

비트연산에는 다음과 같은 것들이 있다.

연산자	기능	문법	설명
&	비트 AND	a & b	a 와 b 를 비트 AND 연산
|	비트 OR	a | b	a 와 b 를 비트 OR 연산
^	비트 XOR	a ^ b	a 와 b 를 비트 XOR 연산
~	비트 NOT	~a	a 의 비트를 뒤집음
<<	비트 왼쪽 시프트	a << b	a 의 비트를 b 번 왼쪽으로 이동
>>	비트 오른쪽 시프트	a >> b	a 의 비트를 b 번 오른쪽으로 이동

AND 연산: a 와 b 에서 대응하는 각 자리수를 AND 연산함 ( 1101 & 1001 = 1101 )

OR 연산: a 와 b 에서 대응하는 각 자리수를 OR 연산함 ( 1101 | 1001 = 1001 )

XOR 연산: a 와 b 에서 대응하는 각 자리수를 XOR (배타적 OR) 연산함 ( 1101 ^ 1001 = 0100 )

NOT 연산: a 의 비트를 뒤집음 ( ~1101 = 0010 )

이번 문제에서는 이러한 비트마스크, 비트연산과 dp(dynamic programming) 을 이용하여 문제를 좀 더 간략하게 해결할 수 있었다.

dp라는 리스트를 만들고 dp[x][visited] 에 현재 x번째 요소를 보고 있고, 그 전까지 방문한 조합이 visited일 때의 최소값을 갱신해준다. 이 때 이 visited 에 비트마스크를 사용하여 그 전까지 이미 일을 할당받은 사람들을 표시해준다.

Python 으로 시간 초과하여 PyPy3으로 풀었다.

코드

import sys

INF = float('inf')
n = int(sys.stdin.readline())
d = []
for _ in range(n):
    d.append(list(map(int, sys.stdin.readline().split())))
dp = [[-1] * (1 << n) for _ in range(20)]


def dfs(x, visited):
    if visited == (1 << n) - 1:
        return 0
    if dp[x][visited] != -1:
        return dp[x][visited]
    dp[x][visited] = INF
    for i in range(n):
        if visited & (1 << i):
            continue
        dp[x][visited] = min(dp[x][visited], dfs(x + 1, visited | (1 << i)) + d[x][i])
    return dp[x][visited]


print(dfs(0, 0))

더 생각해 볼 것?

오랜만에 dfs를 푸니까 다시 헤매게 되었다. dfs 관련 숙달이 더 필요할 것 같다.

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!