from bitmasking 정리..
bitmasking만 사용했을 때 재일 좋다고 생각되는 programmers/kakao의 양궁대회 문제에 대한 소개를 먼저 해본다.
이 문제의 경우 라이언이 점수를 얻는 모든 케이스를 탐색할 필요가 있는, 말 그대로 bitmasking을 가장 잘 쓰게 되는 케이스의 문제였다.
문제에 대한 조건이 상당히 길어 자세하게 설명할 생각은 없고 만약 보고싶을 경우 위 링크를 클릭해서 읽고 오시길..
간단한 설명으로는 라이언이 get_score[i] 갯수만큼의 과녁에 화살을 쏘았을 때 10-i점을 얻고, 나머지의 경우 info[i]가 0이 아니면 어피치가 10-i점을 얻으며, 이 때 라이언이 가장 높은 점수차로(추가 조건이 더 있음) 이기는 케이스를 반환하는 함수를 구현하는 문제였다.
우선 풀이를 먼저 써놓고 설명한다.
def solution(n, info):
answer = []
get_score = [i+1 for i in info]
diff_score = 0
for subset in range(1,1<<10):
ryan = 0
apeach = 0
arr = [0 for _ in range(11)]
for i in range(10):
if subset & (1<<i):
ryan += 10-i
arr[i] = get_score[i]
elif info[i] != 0:
apeach += 10-i
if sum(arr) > n:
continue
arr[10] = n-sum(arr)
if ryan-apeach == diff_score:
answer.append(arr)
elif ryan-apeach > diff_score:
answer = [arr]
diff_score = ryan-apeach
if diff_score == 0:
return [-1]
return answer[-1]여기서 bitmasking이 쓰이는 경우는 2가지로
for subset in range(1,1<<10):if subset & (1<<i):
부분이다. 조금 더 자세한 설명으로
subset의range가0b0000000001 # == 0b1부터0b1111111111까지 돌 때,- subset의 index에 따라 숫자가 1인 모든 index를 고른 후 라이언의 점수와 쏘는 화살의 갯수를 카운팅하는 방법이다.
이것이 어떻게 성립되는지는 아래 예시, 혹은 위에 링크를 걸어놓은 이전 포스팅을 참고하자.
# example. subset == 0b0100100010 인 경우.
lst = []
for i in range(10):
if subset & (1<<i):
lst.append(i)
print(lst) # == [1, 4, 8]다음으로 소개할 문제는 백준 12813번 문제로 bitmasking을 정말 원시적으로 구현할 수 있는지에 대해 묻는 문제이다.
(워낙 백준 2098번을 소개할까도 고민했지만, DP가 섞여있어서 설명이 난해해지고 bitmasking만을 소개하는 글로는 적절치 못하다 판단되서 + 다 쓰고나서 보니 이전 글에 써놓은 해당 블로그의 풀이와 정말 매우 유사하게 되서 해당 문제는 따로 설명 없이 맨 아래 풀이만 남겨놓는다.)
백준 12813의 풀이는 다음과 같다.
예시에서는 길이가 10인 예시를 들었기 때문에 for i in ragne(100000)에 10만 대신 10이 들어가면 된다.(모든 채점용 문제는 input인 a, b의 길이가 10만이라는 조건이 명시되어있었기 때문에 따로 len을 쓰지 않고 10만을 그대로 넣어줌.)
처음 input에는 차례대로 10만 단위의 두 bit a, b가 string 형태로 주어진다.
우리가 output으로 내야할 것은 a & b, a | b, a ^ b, ~a, ~b였고,
풀이 자체는 단순히 index에 따른 a, b에 숫자만 비교해주면 되는 것이었기 때문에 각 조건에 맞춰 이름지어진 string을 뽑아주는 문제였다.
from sys import stdin
a = stdin.readline().strip()
b = stdin.readline().strip()
op_and = ''
op_or = ''
op_xor = ''
maxi = min(a.index('1'),b.index('1'))
not_a = ''
not_b = ''
for i in range(100000):
op_and += '1' if a[i] == b[i] and a[i] == '1' else '0'
op_or += '1' if a[i] == '1' or b[i] == '1' else '0'
not_a += '0' if a[i] == '1' else '1'
not_b += '0' if b[i] == '1' else '1'
if maxi>i:
op_xor += '0'
elif a[i] != b[i]:
op_xor += '1'
else:
op_xor += '0'
print(op_and)
print(op_or)
print(op_xor)
print(not_a)
print(not_b)마지막으로 아래 풀이는 백준 2098번 문제의 풀이이다.
n = int(input())
graph = [tuple(map(int,input().strip().split())) for _ in range(n)]
visited_all = (1<<n) - 1
num = 15000001 #input으로 들어가는 최댓값을 항상 넘는 수.
weight_subtree = [[None]*((1<<n)-1) for _ in range(n)]
def get_min_weight(last,visited):
if visited == visited_all:
return graph[last][0] if graph[last][0] != 0 else num
# graph[last][0] : 마지막 고려사항. but 이게 0일 경우 num을 return하도록 함.
if weight_subtree[last][visited] != None:
return weight_subtree[last][visited]
tmp = num
for city in range(n):
if visited & (1<<city) == 0 and graph[last][city] != 0:
tmp = min(tmp, get_min_weight(city,visited | (1<<city))+graph[last][city])
weight_subtree[last][visited] = tmp
return tmp
print(get_min_weight(0,1))end.
