코딩테스트에서 사용되는 주요 라이브러리

✅ 표준 라이브러리

특정 프로그래밍 언어에서 자주 사용되는 표준 소스코드를 미리 구현해 놓은 라이브러리이다.

파이썬 표준 라이브러리는 다음 문서에서 자세히 확인할 수 있다!

https://docs.python.org/ko/3/library/index.html

The Python Standard Library

코테를 준비하면서 무조건 알아야 한다고 생각하는 라이브러리 6가지는 다음과 같다.

• 내장함수: print(), input()과 같은 기본 입출력부터 sorted()와 같은 정렬 기능을 가진 기본 라이브러리
• itertools: 순열 및 조합 라이브러리를 제공하며, 반복되는 형태의 데이터를 처리할 때 유용한 라이브러리
• heapq: 최단경로 알고리즘, 우선순위 큐 등을 구현할 때 유용한 라이브러리
• bisect: 이진탐색 기능을 제공하는 라이브러리
• collections: 덱(deque), 카운터(counter) 등의 쏠쏠한 자료구조를 포함하고 있는 라이브러리
• math: 팩토리얼, 최대공약수(GCD), 삼각함수 등 다양한 수학적 기능을 제공하는 라이브러리

각각의 라이브러리에 대한 상세 설명 (근데 내장함수는 PASS~)

⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️ ⬇️

 

✅ Itertools

위에도 말했듯이 반복되는 데이터를 처리할 때 유용한 라이브러리이다. 주로 코테에서 많이 사용하는 것은 permutations와 combinations가 있다.

📍permutations

리스트 등 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우의 수 즉, 순열을 계산해준다. 클래스이므로 객체 초기화 이후 리스트 자료형으로 변환해 사용한다. 예시로 이해해보장

from itertools import permutations

data = ['j', 'a', 'm']

result = list(permutations(data,3))

print(result)

# 출력은?
[('j', 'a', 'm'), ('j', 'm', 'a'), ('a', 'm', 'j'), ('a', 'j', 'm'), ('m', 'j', 'a'), ('m', 'a', 'j')]

📍combinations

리스트 등 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우의 수 즉, 조합을 계산해준다. 이것도 예시로 이해해보자

from itertools import combinations

data = ['j', 'a', 'm']

result = list(combinations(data,2))

print(result)

# 출력은?
[('j', 'a'), ('j', 'm'), ('a', 'm')]

📍combinations_with_combinations

combinations와 같이 조합을 계산해주는 것은 같지만, 원소를 중복해서 뽑는다는 차이점이 있다.

from itertools import combinations_with_replacement

data = ['j', 'a', 'm']

result = list(combinations_with_replacement(data,2))

print(result)

# 출력은?
[('j', 'j'), ('j', 'a'), ('j', 'm'), ('m', 'm'), ('a', 'm'), ('a', 'a')]

📍product

permutations와 같이 순열을 계산해주는 것은 같지만, 원소를 중복해서 뽑는다는 차이점이 있다. (예제는 생략...)

 

✅ heapq

다익스트라 최단 경로 알고리즘을 포함해 다양한 알고리즘에서 우선순위 큐 기능을 구현할 때 사용된다. heapq 대신 PriorityQueue 라이브러리를 사용할 수도 있는데, 시간초과가 날 수 있으니 그냥 heapq를 사용하자!

파이썬의 heapq(힙)은 최소 힙으로 구성되어 있어서 최대 힙을 사용하려면 역수(-;마이너스)를 해줘야 한다. 아무튼 최소 힙이 디폴트므로, 원소를 힙에 넣었다 빼기만 해도 시간 복잡도 O(NlogN)에 오름차순 정렬을 할 수 있다.

• 최소 힙(min-heap): 부모 노드의 값이 자식 노드의 값보다 작거나 같은 이진 트리로, 루트 노드에는 항상 최솟값이 위치
• 최대 힙(max-heap): 부모 노드의 값이 자식 노드의 값보다 크거나 같은 이진 트리로, 루트 노드에는 항상 최댓값이 위치 ==> 최대 힙을 구하려면 저장할 값을 음수로 변환하는 방법 사용
• heapq.heappush(heap, item): 힙에 원소 삽입
• heapq.heappop(heap): 힙에서 원소 꺼내기
• heapq.heapify(x): 리스트를 힙 자료구조로 변환
• heapq.heappushpop(heap, item): 힙에 새로운 항목을 추가하고 가장 작은 항목을 제거한 후 반환
• heapq.heapreplace(heap, item): 힙에서 가장 작은 항목을 제거하고 새로운 항목을 추가

흠..예제로 이해해보자.

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([2, 1, 3, 5, 7, 9, 4, 0, 6, 8])
print(result)

# 출력은??
[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]

 

최대 힙은 위에 말했듯이 마이너스 부호를 붙여주기만 하면 된다! 위와 같은 코드지만 -만 붙여줘도 내림차순 정렬이 된다.

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([2, 1, 3, 5, 7, 9, 4, 0, 6, 8])
print(result)

# 출력은??
[9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

 

✅ bisect

정렬된 리스트를 다루기 위한 효율적인 방법을 제공한다. 주로 이진 탐색 알고리즘을 사용하여 정렬된 리스트에 값을 삽입하거나 특정 값을 찾는 작업을 수행한다.

• bisect.bisect_left(a, x, lo=0, hi=len(a)):
  • 정렬된 리스트 a에 대해 값 x를 삽입할 위치를 찾음
  • 리스트 내의 값들이 x와 같은 경우, 그 값들의 가장 왼쪽 인덱스를 반환
• bisect.bisect_right(a, x, lo=0, hi=len(a)):
  • 정렬된 리스트 a에 대해 값 x를 삽입할 위치를 찾음
  • 리스트 내의 값들이 x와 같은 경우, 그 값들의 가장 오른쪽 인덱스를 반환
• bisect.insort_left(a, x, lo=0, hi=len(a)):
  • 값 x를 리스트 a에 삽입하여 정렬된 상태를 유지
  • 동일한 값이 있을 경우, 가장 왼쪽에 삽입
• bisect.insort_right(a, x, lo=0, hi=len(a)):
  • 값 x를 리스트 a에 삽입하여 정렬된 상태를 유지
  • 동일한 값이 있을 경우, 가장 오른쪽에 삽입

import bisect

# 정렬된 리스트
a = [1, 2, 4, 4, 8]

# 값 x를 삽입할 위치 찾기
x = 4
print(bisect.bisect_left(a, x))  # 출력: 2
print(bisect.bisect_right(a, x))  # 출력: 4
print(bisect.bisect(a, x))  # 출력: 4 (bisect_right와 동일)

import bisect

# 정렬된 리스트
a = [1, 2, 4, 4, 8]

# 값 x를 삽입하여 정렬된 상태 유지
x = 3
bisect.insort_left(a, x)
print(a)  # 출력: [1, 2, 3, 4, 4, 8]

a = [1, 2, 4, 4, 8]
bisect.insort_right(a, x)
print(a)  # 출력: [1, 2, 3, 4, 4, 8] (insort_left와 동일한 결과)

 

✅ collections

기본적인 데이터 구조인 리스트, 튜플, 딕셔너리 등의 기능을 확장하여 더 강력하고 사용하기 쉬운 데이터 구조를 제공한다. 그 중에서도 counter랑 deque를 많이 사용했던 것 같다..!

• Counter: 등장 횟수를 세는 기능을 제공하며 요소가 키(key)가 되고, 요소의 개수가 값(value)이 된다.

from collections import Counter

cnt = Counter(['a', 'b', 'c', 'a', 'b', 'b'])

print(cnt['b']) # 출력: 3
print(cnt)  # 출력: Counter({'b': 3, 'a': 2, 'c': 1})

• deque: 연속적으로 나열된 데이터의 시작부분이나 끝부분에 데이터를 삽입하거나 삭제할 때 유용하다. 리스트보다 효율적인 큐 자료구조를 제공하지만, 인덱싱이나 슬라이싱 등의 기능을 사용할 수 없다.

from collections import deque

d = deque([1, 2, 3])
d.append(4)
d.appendleft(0)
print(d)  # 출력: deque([0, 1, 2, 3, 4])
d.pop()
d.popleft()
print(d)  # 출력: deque([1, 2, 3])

• defaultdict: 기본 값을 지정할 수 있는 딕셔너리로, 존재하지 않는 키를 조회할 때 기본 값을 반환한다.

from collections import defaultdict

d = defaultdict(int)  # 기본 값으로 0을 설정
d['a'] += 1
print(d)  # 출력: defaultdict(<class 'int'>, {'a': 1})

• namedtuple:필드 이름을 가질 수 있는 불변의 순차 자료형으로, 튜플처럼 사용하면서 필드 이름으로 접근할 수 있다.

from collections import namedtuple

Point = namedtuple('Point', ['x', 'y'])
p = Point(11, y=22)
print(p.x, p.y)  # 출력: 11 22

 

 

 

[참고: 이것이 취업을 위한 코딩 테스트다 with 파이썬]