- 표준라이브러리란 특정한 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리를 의미한다.
- 예를 들어 C++ 에는 STL(Standard Template Library)가 있다.
- iterable 객체가 입렵으로 주어졌을 때 활용할 수 있는 함수인 sum()가 있다.
array = [1,2,3,4,5]
result = sum(array)
- min() 함수는 파라미터가 2개 이상 들어왔을 때 가장 작은 값을 반환한다.
array = [1,2,3,4,5]
result = min(array)
- max() 함수는 파라미터가 2개 이상 들어왔을 때 가장 큰 값을 반환한다.
array = [1,2,3,4,5]
result = max(array)
- eval() 함수는 수학 수식이 문자열 형식으로 들어오면 해당 수식을 계산한 결과를 반환한다.
result = eval("(3+5) * 7")
print(result)
56
- 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다.
- 순열과 조합 등을 제공한다.
- 순열
import itertools
items = [1,2,3]
permutation = list(itertools.permutations(data,2))
print(permutation)
[(1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)]
- 조합 (순서를 고려하지 않고 데이터를 뽑을 때)
combination = list(itertools.combinations(items,2))
print(combination)
[(1,2), (1,3), (2,3)]
product = list(itertools.product(items, repeat = 2))
print(product)
[(1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3)]
combi_replacement = list(itertools.combinations_with_replacement(items,2))
print(combi_replacement)
[(1, 1), (1, 2), (1, 3), (2, 2), (2, 3), (3, 3)]
- heap은 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다.
- heapq 외에도 PriorityQueue 라이브러리를 사용할 수 있지만, 코딩 테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 heapq를 이용하는 것이 좋다.
- 파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다.
- 보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문이다.
- 힙에 원소를 삽입할 때는
heapq.heappus() 메서드를 사용하고, 힙에서 원소를 꺼내고자 할 떄는 heapq.heappop() 메서드를 이용한다.
- heap을 활용한 힙 정렬 구현 방식이다.
import heapq
def heapSort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h,value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ in range(len(h)):
result.append(heapq.heappop(h))
return result
beforeArray = [1,2,3461,23,5,547,5,2,6,85,6,84,2,1,4,5,3,42,5,7,3]
resultSort = heapSort(beforeArray)
print(resultSort)
[1, 1, 2, 2, 2, 3, 3, 4, 5, 5, 5, 5, 6, 6, 7, 23, 42, 84, 85, 547, 3461]
- 또한 파이썬에서 최대 힙을 제공하지 않는다. 따라서 heapq 라이브러리를 이용하여 최대힙을 구현해야 할 때는 원소의 부호를 임시로 변경하는 방식을 사용한다.
import heapq
def heapSort(iterable):
h = []
result = []
# 모든 원소를 차례대로 힙에 삽입
for value in iterable:
heapq.heappush(h,-value)
# 힙에 삽입된 모든 원소를 차례대로 꺼내어 담기
for _ in range(len(h)):
result.append(-heapq.heappop(h))
return result
beforeArray = [1,2,3461,23,5,547,5,2,6,85,6,84,2,1,4,5,3,42,5,7,3]
resultSort = heapSort(beforeArray)
print(resultSort)
[3461, 547, 85, 84, 42, 23, 7, 6, 6, 5, 5, 5, 5, 4, 3, 3, 2, 2, 2, 1, 1]
- 이진 탐색을 쉽게 구현할 수 있도록 bisect 라이브러리가 주어진다. bisect 라이브러리에서는
bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 시간 복잡도 O(logN)에 동작한다.
bisect.bisect_left(a, x): 정렬된 리스트 a에서 x를 삽입할 위치의 인덱스를 반환한다. 이미 리스트에 x가 존재할 경우 왼쪽의 위치를 반환한다.bisect.bisect_right(a, x): 정렬된 리스트 a에서 x를 삽입할 위치의 인덱스를 반환한다. 이미 리스트에 x가 존재할 경우 오른쪽의 위치를 반환한다.- 예시 1
import bisect
# 정렬된 리스트에서 삽입할 위치 찾기
a = [1, 2, 4, 4, 6]
position = bisect.bisect_left(a, 3)
print(position) # 출력: 2
# 정렬된 리스트에 요소 삽입하기
bisect.insort_left(a, 3)
print(a) # 출력: [1, 2, 3, 4, 4, 6]
- 예시 2
- 범위내 count 구하는 함수를 만들 때 위 메서드들을 활용할 수 있다.
import bisect
def count_by_range(a, left_value, right_value):
right_index = bisect.bisect_right(a, right_value)
left_index = bisect.bisect_left(a,left_value)
return right_index - left_index
# 리스트 선언
a = [1,2,3,3,3,3,4,4,8,9]
print(count_by_range(a,4,4))
print(count_by_range(a,-1,3))
# 2
# 6
- collections 라이브러리의 기능 중에서 코딩 테스트에서 유용하게 사용되는 클래스는
deque와 Counter이다.
deque는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없다. 다만, 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적으로 사용될 수 있다.deque는 스택이나 큐의 기능을 모두 포함한다고 볼 수 있기 때문에 스택 혹은 큐 자료구조의 대용으로 사용될 수 있다.
from collections import deque
data = deque([2,3,4])
data.append(1)
data.appendleft(55)
print(data)
print(list(data))
deque([55, 2, 3, 4, 1])
[55, 2, 3, 4, 1]
- Counter는 등장 횟수를 세는 기능을 제공한다. 구체적으로 리스트와 같은 iterable 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려준다.
- 따라서 원소별 등장 횟수를 세는 기능이 필요할 때 짧은 소스코드로 이를 구현할 수 있다.
from collections import Counter
counter = Counter([1,2,3,1,1,2,4,5,6])
print(counter)
print(dict(counter))
Counter({1: 3, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1})
{1: 3, 2: 2, 3: 1, 4: 1, 5: 1, 6: 1}
- math 라이브러리는 자주 사용되는 수학적인 기능을 포함하고 있는 라이브러리이다.
- 팩토리얼, 제곱근, 최대공약수(GCD) 등을 계산해주는 기능을 포함하고 있다.
import math
print(math.factorial(5))
print(math.sqrt(7))
print(math.gcd(21,15))
math.pi
math.e