5. 주요 라이브러리와 문법

1. itertools

 

itertools는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다.

 

코딩 테스트에서 가장 유용하게 사용할 수 있는 클래스는 permutations, combinations이다

 

순열을 사용하려면

from itertools import permutations
data = ['A','B','C']
result = list(permutations(data, 3))

조합을 사용하려면

from itertools import combinations

data = ['A','B','C']

result = list(combinations(data, 2))

처럼 작성하면 된다.

 

2. heapq

 

heapq는 다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현하고자 할 때 사용된다.

 

파이썬의 힙은 최소 힙으로 구성되어 있으므로 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도 O(NlogN)에 오름차순 정렬이 완료된다. 보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문이다.

 

힙에 원소를 삽입할 때는 heapq.heappush() 메서드를 이용하고, 힙에서 원소를 꺼내고자 할 때는 heapq.heappop() 메서드를 이용한다.

 

힙 정렬을 heapq로 구현하는 예제는 아래와 같다.

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])

3. bisect

 

bisect 라이브러리는 정렬된 배열에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용된다.

 

bisect_left() 함수와 bisect_right() 함수가 가장 중요하게 사용되며, 이 두 함수는 시간 복잡도 O(logN)에 동작한다.

 

이 함수들은 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수를 구하고자 할 때, 효과적으로 사용될 수 있다.

 

from bisect import bisect_left, bisect_right

# 값이 [left_value, right_value]인 데이터의 개수를 반환하는 함수
def count_by_range(a, left_value, right_value):
  right_index = bisect_right(a, right_value)
  left_index = bisect_left(a, left_value)
  return right_index - left_index

# 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

# 값이 4인 데이터 개수 출력
print(count_by_range(a, 4, 4))

# 값이 [-1, 3] 범위에 있는 데이터 개수 출력
print(count_by_range(a, -1, 3))

4. collections

 

collections 라이브러리의 기능 중에서 코딩 테스트에서 유용하게 사용되는 클래스는 deque와 Counter이다.

 

보통 파이썬에서는 deque를 사용해 큐를 구현한다. 따라서 deque를 이용해 큐를 구현해야 한다.

 

기본 리스트 자료형은 데이터 삽입, 삭제 등의 다양한 기능을 제공한다.

 

하지만 리스트 자료형은 append() 메서드로 데이터를 추가하거나, pop() 메서드로 데이터를 삭제할 때 '가장 뒤쪽 원소'를 기준으로 수행된다.

 

따라서 앞쪽에 있는 원소를 처리할 때는 리스트에 포함된 데이터의 개수에 따라서 많은 시간이 소요 될 수 있다.

 

deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없지만 연속적으로 나열된 데이터의 시작 부분이나 끝부분에 데이터를 삽입하거나 삭제할 때는 매우 효과적으로 사용될 수 있다. 모두 O(1)의 시간 복잡도를 가진다.

 

deque는 첫 번째 원소를 제거할 때 popleft()를 사용하며, 마지막 원소를 제거할 때 pop()을 사용한다. 또한 첫 번째 인덱스에 원소 x을 삽입할 때 appendleft(x)를 사용하며, 마지막 인덱스에 원소를 삽입할 때 append(x)를 사용한다.

 

따라서 deque를 큐 자료구조로 이용할 때, 원소를 삽입할 때에는 append()를 사용하고 원소를 삭제할 때에는 popleft()를 사용하면 된다. 그러면 먼저 들어온 원소가 항상 먼저 나가게 된다.

 

from collections import deque

data = deque([2,3,4])
data.appendleft(1)
data.append(5)

print(data) // deque([1,2,3,4,5])
print(list(data)) // [1,2,3,4,5]

파이썬 collections 라이브러리의 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}

5. math

 

math 라이브러리는 팩토리얼, 제곱근, 최대공약수(gcd), pi, 자연상수 e를 출력할 때 사용된다.