No. 15663
1. Problem
2. My Solution
- 첫 번째 방법
- 수열을 구한 뒤 res 에 이미 해당 수열이 존재하면 넘어감
- not in 연산 시간 -> 시간초과
import sys
def permutation(level):
if level >= m:
if arr not in res:
res.append(arr.copy())
else:
for i in range(n):
if visited[i] == True:
continue
else:
arr[level] = nums[i]
visited[i] = True
permutation(level+1)
visited[i] = False
n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))
arr = [0] * m
visited = [False] * n
res = []
permutation(0)
for i in res:
print(' '.join(map(str,i)))
- 두 번째 방법
- itertools permutation 이용 (반환 값은 iterable tuple)
- set 자료형으로 변환하여 중복된 값을 제거
import sys
from itertools import permutations
n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))
for i in sorted(set(permutations(nums,m))):
print(*i)- 세 번째 방법
- set 자료형은 안에 요소로 값 또는 튜플만을 가질 수 있음
- 첫 번째 방법에서 수열을 저장하는 자료형을 튜플로 지정
- 튜플은 값을 변경할 수 없으니 리스트 자료형으로 arr 지정
import sys
def permutation(level):
if level >= m:
res.add(tuple(arr))
else:
for i in range(n):
if visited[i] == True:
continue
else:
arr[level] = nums[i]
visited[i] = True
permutation(level+1)
visited[i] = False
n, m = map(int,sys.stdin.readline().rstrip().split())
nums = sorted(list(map(int,sys.stdin.readline().rstrip().split())))
arr = [0] * m
visited = [False] * n
res = set()
permutation(0)
for i in sorted(res):
print(*i)
3. Learned
- tuple 자료형은 값을 변경할 수 없음 (변경하기 위해서는 + 연산)
- set 자료형은 요소로 값 또는 튜플만을 가질 수 있음 (list불가)
- print(*i) 에서 * 연산자는 여러 값을 갖는 자료형의 요소들을 ',' 으로 구분해서 인자로 보냄
- 함수의 매개변수로 (value, *args, **kargs) 받을 수 있고 *args 는 튜플로 감싸서 받음
No. 1759
1. Problem
2. My Solution
- 첫 번째 방법
- itertools 모듈의 combinations 함수 사용 (조합)
- 만약 알파벳이 자음이 아니면 -> 모음
import sys
from itertools import combinations
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))
for i in combinations(alphabet,l):
count = 0
for a in ['a','e','i','o','u']:
if a in i:
count += 1
if l - count >= 2 and count > 0:
print(*i,sep='')- 두 번째 방법
- 오름차순의 수열만을 출력하도록 함 = 백트래킹을 이용한 조합
import sys
def permutation(level, pre):
if level >= l:
count = 0
for i in arr:
if i in 'aeiou':
count += 1
if l - count >= 2 and count > 0:
res.append(arr.copy())
else:
for i in range(c):
if visited[i] == True:
continue
else:
if str(pre) < alphabet[i]:
arr[level] = alphabet[i]
visited[i] = True
permutation(level+1, alphabet[i])
visited[i] = False
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))
arr = [''] * l
visited = [False] * c
res = []
permutation(0,0)
for i in res:
print(*i, sep='')
3. Others' Solutions
- 백트래킹을 이용한 조합
- 주어진 수를 왼쪽에서 오른쪽으로만 조합해야함
- 해당 숫자에서 오른쪽에 있는 숫자만을 이용하기 위해 i 정보를 인자로 넘김
import sys
def permutation(level, index):
if level >= l:
count = 0
for i in arr:
if i in 'aeiou':
count += 1
if l - count >= 2 and count > 0:
res.append(arr.copy())
else:
for i in range(index, c):
if visited[i] == True:
continue
else:
arr[level] = alphabet[i]
visited[i] = True
permutation(level+1, i+1)
visited[i] = False
l, c = map(int,sys.stdin.readline().rstrip().split())
alphabet = sorted(list(sys.stdin.readline().rstrip().split()))
arr = [''] * l
visited = [False] * c
res = []
permutation(0,0)
for i in res:
print(*i, sep='')
4. Learned
- 조합은 순서가 없는 수열이므로 오름차순으로 나열한다면 순열을 오름차순으로만 출력하도록 백트래킹한 것과 동일함
No. 11723
1. Problem
2. My Solution
- 파이썬의 장점을 이용하여 간단히 구현 (메모리 제약이 까다롭지 않음)
import sys
n = int(sys.stdin.readline())
arr = set()
for _ in range(n):
op = sys.stdin.readline().rstrip().split()
if op[0] == 'add':
arr.add(op[1])
elif op[0] == 'remove':
arr.discard(op[1])
elif op[0] == 'check':
if op[1] in arr:
print(1)
else:
print(0)
elif op[0] == 'toggle':
if op[1] in arr:
arr.discard(op[1])
else:
arr.add(op[1])
elif op[0] == 'all':
arr = set(['1','2','3','4','5','6','7','8','9','10','11','12','13','14','15','16','17','18','19','20'])
else: # empty
arr = set()
3. Others' Solutions
- 비트 마스크를 이용하여 해결
- 0~20, n을 표현하기 위해 21개의 bit 가 필요함 (여기선 1부터 시작이니까 첫 번째 bit는 0 고정)
- 모든 비트를 1로 만들기 위해서 (1 << 21) -1
- (1<<21) = 100000000000000000000
- (1 << 21) -1 = 111111111111111111111
import sys
n = int(sys.stdin.readline())
bit = 0
for _ in range(n):
op = sys.stdin.readline().rstrip().split()
if op[0] == 'add':
bit |= (1 << int(op[1]))
elif op[0] == 'remove':
bit &= ~(1 << int(op[1]))
elif op[0] == 'check':
if bit & (1 << int(op[1])) == 0:
print(0)
else:
print(1)
elif op[0] == 'toggle':
bit ^= (1 << int(op[1]))
elif op[0] == 'all':
bit = (1 << 21) -1
else: # empty
bit = 0
4. Learned
- 비트마스크에 대해 알게됨 (참고 블로그)
- 비트마스크
- bit(0/1)로 구성된 이진수 정수를 이용하여 자료구조처럼 사용하는 기법으로 집합, 부분집합, 요소 구성 여부에 대한 문제 해결에 적용되는 알고리즘 기법
- 집합에 존재하는 모든 요소의 수가 특정 수 n 보다 작다면 (n<30) 직접 접근하여 요소 존재 여부 판단가능 (1 << 0, 1<<20 -> 0이 있는지, 20이 있는지)
- 보통의 경우에는 이미 존재하는 배열(리스트)에서 해당 index 번째 요소가 포함되었는지 판단하는 경우가 많음
- 비트마스크를 이용하여 계산 속도, 메모리 사용 공간에 대한 효율성을 높일 수 있음
- set 자료형 연산자 중에 discard() 함수는 요소가 존재하면 삭제하고 없으면 무시
