파이썬 코딩테스트 준비하기 - 라이브러리, 알아두면 좋은 것

 

 

코딩테스트를 준비하면서 언어를 파이썬으로 선택하는 이유는 단연코 편리함이다.

 

코딩테스트에서 편리하게 쓸수있는 라이브러리와 파이썬스러운 코딩문법 등을 정리하려고한다.

 

---

 

핵심 라이브러리

• 내장함수
• itertools
• collections
• heapq
• bisect
• math

 

내장함수

 

import 없이 기본적으로 쓸 수 있는 함수들

print(), sum(), sorted(), min(), max(), eval() 등

코딩을 한다면 이미 사용해봤고 알만한 것들이므로 설명은 패스

 

 

itertools

 

반복되는 데이터를 처리하기 위한 기능들 제공

iterable객체를 받음

클래스 객체이므로 list로 형변환해서 사용

 

 

permutations() : 순열계산 (n개의 선택지에서 r개를 뽑아 나열하는 경우의 수)

from itertools import permutations
li = ['1','2','3']
res = list(permutations(li,2))  
print(res)  # [('1', '2'), ('1', '3'), ('2', '1'), ('2', '3'), ('3', '1'), ('3', '2')]

 

combinations(): 조합계산 (n개에서 r개를 순서 상관없이 뽑는 경우의 수)

from itertools import combinations
li = ['1','2','3']
res = list(combinations(li,2))
print(res)  #  [('1', '2'), ('1', '3'), ('2', '3')]

 

product() : 중복순열 (같은 원소 중복가능한 순열)

뽑는 수를 repeat 속성으로 넣어준다.

from itertools import product
li = ['1','2','3']
res = list(product(li, repeat=2))
print(res)  # [('1', '1'), ('1', '2'), ('1', '3'), ('2', '1'), ('2', '2'), ('2', '3'), ('3', '1'), ('3', '2'), ('3', '3')]

 

 

combinations_with_replacement() : 중복조합

from itertools import combinations_with_replacement
li = ['1','2','3']
res = list(combinations_with_replacement(li,2))
print(res)  #  [('1', '1'), ('1', '2'), ('1', '3'), ('2', '2'), ('2', '3'), ('3', '3')]

 

compress() : 선택자에서 같은 인덱스의 원소가 참인 것을 뽑아냄

from itertools import compress
li = ['1','2','3']
res = list(compress(li, [1, 0, 1]))
print(res)  # ['1', '3']

 

 

collections

 

deque, counter 등 자료구조를 포함

 

deque : 큐 대신 deque를 사용하자 !! (속도가 빠름) 단 linkedList구조 이기때문에 인덱싱 안됨

from collections import deque

data = deque([2, 3, 4])
data.appenleft(1)  # 젤 앞 삽입
data.append(5)  # 젤 끝 삽입
data.pop()  # 끝에서 제거 (5)
data.popleft()  # 첫 번째 제거 (1)

 

 

counter() : 객체 내부 원소 숫자 세어줌, 딕셔너리 구조의 확장임. 산술연산자 가능

from collections import Counter

counter = Counter(['red','blue','red','green','blue','blue'])

print(counter['blue']) # 3
print(counter['green']) # 1
print(dict(counter)) # {'red' : 2, 'blue': 3, 'green': 1}

 

>>> Counter("hello world")
Counter({'l': 3, 'o': 2, 'h': 1, 'e': 1, ' ': 1, 'w': 1, 'r': 1, 'd': 1})

 

가장 흔한 값 찾기

from collections import Counter

Counter('hello world').most_common()  # 많은 순서로 정렬해서 리스트 반환
## [('l', 3), ('o', 2), ('h', 1), ('e', 1), (' ', 1), ('w', 1), ('r', 1), ('d', 1)]

print(Counter('hello world').most_common(1))  # [('l', 3)]

 

 

 

heapq

 

heap을 제공. 우선순위 큐 구현에 사용.

최소 힙으로 구현되어있음.

최대 힙이 필요하다면 push와 pop전에 부호를 바꿔서(-) 사용

 

heapq.heapify(list) : 최소힙 구조로 변경

heapq.heappush(list,n) : 힙구조 유지하며 n삽입

heapq.heappop(list) : 요소 꺼내기

 

O(nlogN)의 힙 정렬 예제

import heapq
def heapSort(iterable):
    h=[]
    result = []
    for value in iterable:
        heapq.heappush(h, value)
    for i in range(len(h)):
    	result.append(heapq.heappop(h))
    return result

result = heapSort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0])
print(result)  # [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

 

bisect

 

O(logN)시간 복잡도의 이진탐색 기능 제공

 

bisect_left(list,n) : list에서 정렬된 순서를 유지하면서 n을 삽입할 수 있는 가장 왼쪽 인덱스를 찾음

bisect_right(list,n) : 오른쪽 인덱스를 찾음

from bisect import bisect_left, bisect_right

li = [1, 2, 4, 4, 5, 6, 6, 6, 7, 8]
n = 6

print(bisect_left(li, n)) # 5
print(bisect_right(li, n)) # 8

 

특정 범위의 원소 개수를 구하는 예제

from bisect import bisect_left, bisect_right

def cnt_range(li,left,right):
    return bisect_right(li, right) - bisect_left(li, left)

li = [1, 2, 4, 4, 5, 6, 6, 6, 7, 8]

print(cnt_range(li, 4, 4))  # 2
print(cnt_range(li, 2, 6))  # 7

 

 

math

 

팩토리얼,제곱근,최대공약수 등 수학적 함수 제공

 

math.factorial(n) : n! 계산

math.sqrt(n) : n의 제곱근 계산

math.gcd(n,m) : n과 m의 최대 공약수 계산

math.floor(n) : 내림

math.ceil(n) : 올림

math.round(n) : 반올림

 

 

 

이외 유용한 함수 (추가 예정)

ord('A') # 65 #  아스키코드 문자 변환
chr(65) # A

q, r = divmod(10,3) # 3,1  # 몫,나머지 한번에 계산

list(zip('qwer','as')) # [('q','a'),('w','s')]  # 각 요소를 묶어 tuple (원소 개수가 적은 쪽에 맞춤)

set([1,2,3,2]) # [1,2,3] # 중복제거

 

 

 

list comprehension

 

라이브러리나 함수는 아니지만 파이썬스러운 코드를 만들기 좋은 기능.

>>> a = [8, 3, 2, 10, 15, 7, 1, 9, 0, 11]
>>> [i for i in a if i > 5 and i < 10]
[8, 7, 9]

 

 

---

 

아래는 백준에 나와있는 팁?이다

 

• BOJ는 numpy 등 외장모듈을 지원하지 않습니다. (사실 모든 언어가 그렇습니다.)
• 풀이가 분명히 맞고 시간복잡도도 충분히 작은데 시간 초과가 난다면 언어를 Pypy로 설정하고 제출하면 됩니다. 파이썬은 원래 편리성과 속도를 맞바꾼 언어이기 때문에, 맞아야 될 풀이가 시간 초과더라도 이상할 게 전혀 없습니다.
• 두 수를 입력받고 나서 비교할 때는 반드시 int로 변환을 합시다. 문자열의 비교는 사전 순 비교이기 때문에, 3은 10보다 작지만 "3"은 "10"보다 큽니다.
• is 키워드는 두 대상의 값이 같은지가 아니라 완전히 같은 대상을 가리키는지를 비교합니다. BOJ에서 이걸 쓸 일은 거의 없습니다. 같은 "hello"더라도 따로 정의하면 다른 대상이 됩니다. 이걸 쓰면 디버깅하기도 힘든 게, -5 이상 255 이하의 int는 미리 만들어 놓고 정의할 때마다 가져다 쓰기 때문에, 딱 그 범위까지는 is와 ==가 똑같은 동작을 합니다. 그래서 손으로 반례를 찾으려고 하면 찾아지지 않습니다.
• list.pop(0), list.index, list.insert, list.count, x in list, list[:-1] 등은 다 O(N)입니다. 이외에도 O(N)이 걸리는 list 연산이 굉장히 많습니다. https://wiki.python.org/moin/TimeComplexity
• 위의 이유로, list를 큐 또는 덱으로 사용하면 절대, 절대, 절대, 절대, 절대 안 됩니다!! 반드시 collections.deque를 써야 합니다.
• 아니요, queue.Queue도 안 됩니다. 이건 멀티스레딩을 위해 만들어진 큐이고 매우 느립니다.
• 파이썬의 재귀 깊이는 기본적으로 최대 1,000입니다. sys.setrecursionlimit으로 이 깊이를 조절할 수 있습니다.
• 두 개의 int를 나누면 float이 됩니다. int(a/b) 말고 a//b를 쓰는 것이 훨씬 안전합니다. 맨 위의 "부동소수점 자료형은 나타내는 수의 범위가 넓지만 ..."을 읽어보세요.
• 사실 Pypy가 시간 초과더라도 이상할 건 없습니다. 쉬운 문제들은 거의 다 Pypy로 충분히 풀리지만, solved.ac 플래티넘 정도의 문제부터는 조금씩 위험해지기 시작합니다. 상황에 맞는 언어를 사용하도록 합시다.
• Pypy의 재귀 깊이는 파이썬과 달리 딱 정해 놓은 제한이 없습니다. 하지만 10만 단위로 너무 깊이 들어가면 스택 오버플로가 나고, 그 제한은 파이썬보다 낮습니다. 또한 Pypy는 재귀에 굉장히 약합니다.
• print가 sys.stdout.write보다 많은 메모리를 차지합니다. 구체적으로, print를 많이 사용할 수록 메모리도 많이 사용됩니다. 2020년 8월 9일 현재 Atcoder에서도 같은 현상이 나는 것으로 확인했습니다.
• sys.setrecursionlimit에서 설정해 놓은 재귀 깊이가 클 수록 메모리 사용량도 큽니다. 2020년 8월 9일 현재 Codeforces에서도 같은 현상이 나는 것으로 확인했습니다.

​

출처 : https://www.acmicpc.net/blog/view/70