알고리즘 Tips / python

정지원·2020년 6월 24일
0

입력 빠르게 받자

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline()))

def input(): return sys.stdin.readline().rstrip()
n = int(input())

input()을 overwrite해서 사용하자

dictionary의 value에 list 넣을 때 초기화

dict.setdefault(key, []).append(value)

딕셔너리(dict)의 키(key)에 해당하는 값(list)에 value를 추가한다. 없으면 []. 즉, 초기화하지 않았을 때 list의 메소드를 사용하고 싶어서.

재귀 깊이 늘이기

import sys sys.setrecursionlimit(10**6) # 10^6 까지 늘린다

다만, 이 방법은 PyPy에서는 먹히지 않는다.

리스트 정렬(중복 제거 + 순서 유지)

arr = sorted(set(arr), key=lambda x:(len(x), x))

리스트에 있는 값을 길이 순서대로 정렬하고, 같은 길이인 경우 사전순으로 정렬한다.

몫과 나머지 구하기

q, r = divmod(10,3) # q=3, r=1

zip, itertools.zip_longest

list(zip('abc', 'xy'))  # 원소의 갯수가 작은 부분의 기준
# [('a', 'x'), ('b', 'y')]
itertools.zip_longest('abc', 'xy', fillvalue='X') # 원소의 갯수가 큰 부분의 기준

set

set은 중복 없이, 순서 없는 집합. 즉, hashable한 값만 매개변수로 올 수 있으며, 합집합, 교집합, 차집합을 각각 |, &, - 연산을 이용하여 구할 수 있다.

set([1,2,3,3]) # {1,2,3} 
set([1,2]).issubset(set([1,2,3]))  # 집합 (1,2)는 (1,2,3)의 부분집합 True

itertools

combinations

주어진 iterable 객체에서 주어진 길이에 대한 모든 중복되지 않은 조합을 리턴.

for c in itertools.combinations([1,2,3], 2):  # 1,2,3 세 개의 원소 중 두 개를 뽑는 경우의 수 = 3가지
  print(c)  # (1, 2) / (1, 3) / (2, 3)

combinations_with_replacement

주어진 iterable 객체에서 주어진 길이에 대한 모든 중복된 조합을 리턴.

for c in itertools.combinations_with_replacement([1,2,3], 2):
	print(p)

permutations

주어진 iterable 객체에서 주어진 길이에 대한 모든 중복되지 않은 순열을 리턴.

for p in itertools.permutations([1,2,3], 2):  # 1,2,3 세 개의 원소 중 두 개로 만들 수 있는 순열의 수 = 6가지
  print(p)  # (1, 2) / (1, 3) / (2, 1) / (2, 3) / (3, 1) / (3, 2)

product

주어진 iterable 객체에서 주어진 길이에 대한 모든 중복된 순열을 리턴. repeat 옵션을 설정해주어야 한다.

for p in itertools.product([1,2,3], repeat=2):
	print(p)

compress

주어진 iterable 객체에서 selectors 인덱스의 원소가 참인 것만 뽑아 iterator 리턴.

list(itertools.compress('HELLO', [1,0,0,0,1]))
#  ['H', 'O']
list(itertools.compress('HELLO', [1,0,1]))  # selectors가 iterable 객체보다 짧다면 앞에서부터.
#  ['H', 'L']

0개의 댓글