-
비트마스크 : 비트(bit) 연산을 사용해서 부분집합을 표현하는 방법
-
shift left(<<)
-
A << B의 결과 (A를 왼쪽으로 B비트만큼 민다) : A x 2**B
-
shift right(>>)
-
A >> B의 결과 (A를 오른쪽으로 B비트만큼 민다) : A / 2**B
-
(예: (A+B) / 2 는 (A+B) >> 1 와 같음)
-
현재 집합이 S일 때,
-
x를 추가 : S | (1 << x)
-
x를 검사 : S & (1 << x)
-
x를 제거 : S & ~(1 << x)
-
x를 토글(0을 1로, 1을 0으로) : S ^ (1 << x)
- add x: S에 x를 추가한다. (1 ≤ x ≤ 20) S에 x가 이미 있는 경우에는 연산을 무시한다.
- remove x: S에서 x를 제거한다. (1 ≤ x ≤ 20) S에 x가 없는 경우에는 연산을 무시한다.
- check x: S에 x가 있으면 1을, 없으면 0을 출력한다. (1 ≤ x ≤ 20)
- toggle x: S에 x가 있으면 x를 제거하고, 없으면 x를 추가한다. (1 ≤ x ≤ 20)
- all: S를 {1, 2, ..., 20} 으로 바꾼다.
- empty: S를 공집합으로 바꾼다.
## 11723번: 집합
#### 비어있는 공집합 S가 주어졌을 때, 아래 연산을 수행하는 프로그램을 작성하시오. (check 연산이 주어질때마다, 결과를 출력한다.)
import sys
n = 20
m = int(sys.stdin.readline())
s = 0
for _ in range(m):
op, *num = sys.stdin.readline().split()
if len(num) > 0:
x = int(num[0]) -1
if op == 'add':
s = (s | (1 << x))
elif op == 'remove':
s = (s & ~(1 << x))
elif op == 'check':
res = (s & (1 << x))
if res > 0:
sys.stdout.write('1\n')
else:
sys.stdout.write('0\n')
elif op == 'toggle':
s = (s ^ (1 << x))
elif op == 'all':
s = (1 << n) - 1
elif op == 'empty':
s = 0첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
## 1182번: 부분수열의 합
#### 첫째 줄에 정수의 개수를 나타내는 N과 정수 S가 주어진다. (1 ≤ N ≤ 20, |S| ≤ 1,000,000) 둘째 줄에 N개의 정수가 빈 칸을 사이에 두고 주어진다. 주어지는 정수의 절댓값은 100,000을 넘지 않는다.
#### 첫째 줄에 합이 S가 되는 부분수열의 개수를 출력한다.
n, s = map(int, input().split())
a = list(map(int, input().split()))
ans = 0
## 공집합(0) 부터 전체 집합(111...1 (1이 N개))까지 순회하며 검사
for i in range(1, (1 << n)): # 문제에서 '양의 부분수열'이라고 하였으니 공집합은 제외
s = sum(a[k] for k in range(n) if (i & (1<<k)) > 0) ## i번째 비트마스크에 k가 들어있다면, 해당되는 모든 a[k]에 대한 합을 구하여 조건만족 체크
if m == s:
ans += 1
print(ans)
## 14889번: 스타트와 링크
#### N명을 N/2명씩 두 팀으로 나누려고 한다. (4 <= N <= 20, N은 짝수)
#### 두 팀의 S[i][j]의 능력치의 합의 차이가 최솟값이 되는 경우를 찾아서, 그때의 최솟값을 출력하라.
# (644 ms)
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
ans = -1
for i in range(0, (1 << n)):
first = []
second = []
for j in range(n):
if (i & (1<< j)) > 0: # 현재의 ## i번째 비트마스크에 j번 번호가 들어있다면 (= 값이 '1'),
first += [j] # 1번 팀
else:
second += [j] # 0번 팀
if len(first) != n//2:
continue
t1 = 0
t2 = 0
for l1 in range(n//2):
for l2 in range(n//2):
if l1 == l2: # (없어도 되지만, 방어코드)
continue
t1 += s[first[l1]][first[l2]]
t2 += s[second[l1]][second[l2]]
diff = abs(t1-t2)
if ans == -1 or ans > diff:
ans = diff # 현재의 차이의 최솟값으로 교체
print(ans)## 두 팀에 배정할 때 다른 방법 (564 ms)
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
ans = -1
for i in range(0, (1 << n)):
cnt = 0
for j in range(n):
if (i & (1<< j)) > 0: ## 현재의 i번째 비트마스크에 j번 번호가 들어있다면 (= 값이 '1'),
cnt += 1
if cnt != n//2:
continue ## n//2 명씩 배정 불가한 경우 다음 비트마스크로 pass
# 팀에 배정
first = []
second = []
for j in range(n):
if (i & (1<<j)) > 0:
first += [j]
else:
second += [j]
#if len(first) != n//2:
# continue
t1 = 0
t2 = 0
for l1 in range(n//2):
for l2 in range(n//2):
#if l1 == l2: #(방어코드)
# continue
t1 += s[first[l1]][first[l2]]
t2 += s[second[l1]][second[l2]]
diff = abs(t1-t2)
if ans == -1 or ans > diff:
ans = diff # 현재의 차이의 최솟값으로 교체
print(ans)영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. (행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.)
영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다.(비트마스크 가능) 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
## 14391번: 종이 조각
#### 영선이는 숫자가 쓰여 있는 직사각형 종이를 가지고 있다. 종이는 1×1 크기의 정사각형 칸으로 나누어져 있고, 숫자는 각 칸에 하나씩 쓰여 있다. (행은 위에서부터 아래까지 번호가 매겨져 있고, 열은 왼쪽부터 오른쪽까지 번호가 매겨져 있다.)
#### 영선이는 직사각형을 겹치지 않는 조각으로 자르려고 한다. 각 조각은 크기가 세로나 가로 크기가 1인 직사각형 모양이다. 길이가 N인 조각은 N자리 수로 나타낼 수 있다.(비트마스크 가능) 가로 조각은 왼쪽부터 오른쪽까지 수를 이어 붙인 것이고, 세로 조각은 위에서부터 아래까지 수를 이어붙인 것이다.
#### 첫째 줄에 종이 조각의 세로 크기 N과 가로 크기 M이 주어진다. (1 ≤ N, M ≤ 4)
#### 둘째 줄부터 종이 조각이 주어진다. 각 칸에 쓰여 있는 숫자는 0부터 9까지 중 하나이다.
n, m = map(int, input().split())
a = [list(map(int, list(input()) )) for _ in range(n)]
ans = 0
for s in range(1<<(n*m)):
sum = 0
# 가로 조각 탐색
for i in range(n):
cur = 0
for j in range(m):
k = i*m + j
if (s & (1 << k)) == 0: ## 0 : 가로 조각에 해당
cur = cur * 10 + a[i][j]
else:
sum += cur # 세로 조각 만나기 전까지의 가로조각 최댓값 cur 점수에 더해줌
cur = 0 # 초기화
sum += cur # 현재 행의 마지막 열 칸에 1x1 크기짜리 가로 조각이 있으면 점수에 더해주기 위해
# 세로 조각 탐색
for j in range(m):
cur = 0
for i in range(n):
k = i*m + j
if (s & (1 << k)) != 0: ## 1 : 세로 조각에 해당
cur = cur * 10 + a[i][j]
else:
sum += cur # 가로 조각 만나기 전까지의 가로조각 최댓값 cur 점수에 더해줌
cur = 0 # 초기화
sum += cur # 현재 열의 마지막 행 칸에 1x1 크기짜리 "세로" 조각이 있으면 점수에 더해주기 위해
# 비교
ans = max(ans, sum)
print(ans)2 2
99
11
182
for s in range(1<<(n*m)):
print(s)
# 0 ~ (N-1)0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
for s in range(1<<(n*m)):
for i in range(n):
for j in range(m):
k = i*m + j
print( (s & (1 << k)))0
0
0
0
1
0
0
0
0
2
0
0
1
2
0
0
0
0
4
0
1
0
4
0
0
2
4
0
1
2
4
0
0
0
0
8
1
0
0
8
0
2
0
8
1
2
0
8
0
0
4
8
1
0
4
8
0
2
4
8
1
2
4
8