코테에 필요한 Python 라이브러리 정리

코딩테스트를 준비하면서 알아야하는 python 라이브러리를 정리해보려 한다. (+ 자료구조 설명 살짝 추가!)

1. 내장 함수

• 기본 함수

  • print()
  • max(), min(), sum(), eval()

• 정렬

  • sort(), sorted()
    

2. itertools

• 반복되는 데이터를 처리하는 기능을 포함하고 있는 라이브러리이다.
• permutatitons : 순열
• combinations : 조합
• product : 중복을 포함하는 순열
• combinations_with_replacement : 중복을 포함하는 모든 조합
• 모두 클래스 객체이므로 사용할 때는 객체 초기화 이후 list 자료형으로 변환하여 사용한다.

from itertools import permutations, combinations, product, combinations_with_replacement

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

result = list(permutations(data_list, 3)) # 모든 순열

print(result)

result = list(combinations(data_list, 2)) # 2개를 뽑는 모든 조합

print(result)

result = list(product(data_list, repeat=2)) # 2개를 뽑는 모든 순열 구하기 (중복 허용)

print(result)

result = list(combinations_with_replacement(data_list, 2)) # 2개를 뽑는 모든 조합 (중복 허용)

print(result)

# 결과
[('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'C'), ('C', 'A'), ('C', 'B')]
[('A', 'B'), ('A', 'C'), ('B', 'C')]
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'A'), ('B', 'B'), ('B', 'C'), ('C', 'A'), ('C', 'B'), ('C', 'C')]
[('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

3. heapq (Min heap)

힙(Heap)은 특정한 규칙을 가지는 트리로, 최댓값과 최솟값을 찾는 연산을 빠르게 하기 위해 고안된 완전 이진트리를 기본으로 함.

• heap property : A가 B의 부모노드이면 A의 키 값과 B의 키 값 사이에는 대소관계가 성립한다.
  -- 최소힙 : 부모노드의 키 값이 자식 노드의 키 값 보다 항상 작은 힙
  -- 최대힙 : 부모노드의 키 값이 자식 노드의 키 값 보다 항상 큰 힙
  

  (출처 : https://www.geeksforgeeks.org/heap-data-structure/minheapandmaxheap/)

  이러한 속성으로 인해 힙에서는 가장 낮은(혹은 높은) 우선순위를 가지는 노드가 항상 루트에 오게 되고, 이를 이용해 우선순위 큐와 같은 추상적 자료형을 구현할 수 있다.
  이때, 키 값의 대소관계는 부모/자식 노드 간에만 성립, 형제 노드 사이에는 대소관계가 정해지지 않음

• 파이썬 heapq 모듈은 heapq (priority queue) 알고리즘을 제공한다.

• 다익스트라 최단 경로 알고리즘 등에서 우선순위 큐 기능을 구현하고자 할 때 사용한다.
  - PriorityQueue 라이브러리를 사용할 수 있지만 코딩테스트 환경에서는 heapq가 더빠르게 동작함으로 heapq를 사용한다고 한다.
  

• 최소 힙으로 구성되어 있으므로 넣었다 빼는 것만으로 O(NlogN)에 오름차순 정렬이 완료된다.

• 최소 힙을 사용하면 원소들이 항상 정렬된 상태로 추가되고 삭제되며, min heap에서 가장 작은값은 언제나 인덱스 0, 즉, 이진 트리의 루트에 위치한다.

• 내부적으로 최소 힙 내의 모든 원소(k)는 항상 자식 원소들(2k+1, 2k+2) 보다 크기가 작거나 같도록 원소가 추가되고 삭제된다.

• 힙 함수

  • heapq.heappush(heap, item) : item을 heap에 추가
  • heapq.heappop(heap) : heap에서 가장 작은 원소를 pop & return, 비어있는 경우 IndexError
  • heapq.heapify(x) : 리스트 x를 즉각적으로 heap으로 변환함 (O(N))

4. bisect

• 이진 탐색을 쉽게 구현할 수 있도록 하는 라이브러리
• 정렬된 배열에서 특정 원소를 찾아야 할 때 매우 효과적
• bisect_left(iterable, value) : 정렬된 순서를 유지하면서 iterable에 value를 삽입할 가장 왼쪽 인덱스 구하기
• bisect_right(iterable, value) : 정렬된 순서를 유지하면서 iterable에 value를 삽입할 가장 오른쪽 인덱스 구하기

from bisect import bisect_left, bisect_right

A = [1,1,2,3,5,7,8]

print(bisect_left(A, 5))  # 4
print(bisect_right(A, 5)) # 5

## 응용 : 특정 범위에 속하는 원소의 개수 구하기
def CountsByRange(nums, left, right) :
    right_range = bisect_right(nums, right)
    left_range = bisect_left(nums, left)

    return right_range-left_range

print(CountsByRange(A, -1, 4)) # 4

5. collections

• Counter
  • 등장 횟수를 세는 기능
  • iterable 객체가 주어졌을 때, 해당 객체 내부에 원소가 몇 번씩 등장 했는지 계산해준다.
  • cnt.element() : 요소 반환
  • cnt.update()
  • cnt.items() : 원소와 그 개수 반환
  • cnt.most_common(n) : 입력된 값의 요소들 중 빈도수(최빈값)을 n개 반환
  • cnt1.subtract(cnt2) : 말 그대로 요소를 빼줌. 만약, 요소가 없는 경우인데 subtract()를 진행했다면 음수의 값이 반환됨
  • counter 끼리 산술(덧셈/뺄셈) 연산, 집합(합집합, 교집합) 연산도 가능함

  		from collections import Counter
  		cnt = Counter(["hi", "hey", "hi", "hi", "hello", "hey"])
  		print(cnt)
    
    		>>> Counter({'hi': 3, 'hey': 2, 'hello': 1})
  
  	

• deque
  • 스택, 큐를 구현할 때 사용한다.
  • 가장 앞 원소 추가, 가장 앞 원소 제거에서 O(1)의 시간복잡도를 가진다.
  • 인덱싱, 슬라이싱 등은 사용할 수 없다.
  • pop(), popleft()
  • append(), appendleft()

6. 계산

(1) math

import math

print(math.sqrt(5)) # 제곱근
print(math.factorial(5)) # 팩토리얼
print(math.gcd(35,14)) # 최대공약수
print(math.pi) # pi
print(math.e) # 자연상수 e

# 내림
print(math.floor(3.14))  # 결과 : 3
print(math.floor(-3.14)) # 결과 : -4

# 올림
print(math.ceil(3.14))  # 결과 : 4
print(math.ceil(-3.14)) # 결과 : -3

# 반올림 -> 파이썬 내장함수 round()를 사용한다.
print(round(3.1415))      # 결과 : 3
print(round(3.1415, 2))   # 결과 : 3.14
print(round(31.415, -1))  # 결과 : 30.0

(2) reduce()

• python의 functools 내장 모듈의 reduce() 함수는 여러 개의 데이터를 대상으로 주로 누적 집계를 내기 위해서 사용한다.
  
• 기본 문법

  reduce(집계 함수, 순회 가능한 데이터[, 초기값])

  • 여기서 집계 함수는 두 개의 인자를 받아야 한다.
  • 첫번째 인자는 누적자(accumulator), 두번째 인자는 현재값(current value)이 넘어오게 된다.
  • 누적자는 함수 실행의 시작부터 끝까지 계속해서 재사용되는 값이고, 현재값은 루프를 돌면서 계속해서 바뀌는 값이다.