[Python] 주요 라이브러리의 문법과 유의점 : 내장 함수, itertools, heapq, bisect, collections, math

이것이 취업을 위한 코딩 테스트다 with 파이썬 - 나동빈 저
APPENDIX A. 코딩 테스트를 위한 파이썬 문법 정리 내용

표준 라이브러리

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

 

코딩 테스트에서는 대부분 표준 라이브러리를 사용할 수 있도록 허용한다. 표준 라이브러리를 사용하면 소스코드 작성량에 대한 부담을 줄일 수 있다.

 

파이썬을 이용한다면 파이썬 표준 라이브러리를, C++를 이용한다면 C++ STL(Standard Template Library)를 이용할 수 있다.

+) 라이브러리(Library)란?

주로 소프트웨어를 개발할 때 컴퓨터 프로그램이 사용하는 비휘발성 자원의 모임으로,
여기에는 구성 데이터, 문서, 도움말 자료, 메시지 틀, 미리 작성된 코드, 서브루틴(함수), 클래스, 값, 자료형 사양을 포함할 수 있다.

2023.03.22 - [read about···💭📓👀🧠/IT 5분 잡학사전] - [IT 5분 잡학사전]Ep.11~15 요약 및 TIL

[IT 5분 잡학사전]Ep.11~15 요약 및 TIL

파이썬 표준 라이브러리

필요한 기능이 있다면 공식 문서에서 찾아 사용하자.

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

The Python Standard Library

아래의 6가지 라이브러리는 코딩테스트를 준비한다면 반드시 알아야 한다.

 

• 내장 함수 : print(), input()과 같은 기본 입출력 기능부터 sorted()와 같은 정렬 기능을 포함하고 있는 기본 내장 라이브러리.
• itertools : 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리로, 순열과 조합 라이브러리를 제공.
• heapq : 힙(Heap) 기능을 제공하는 라이브러리. 우선순위 큐 기능 구현을 위해 사용.
• bisect : 이진 탐색(Binary Search) 기능을 제공하는 라이브러리.
• collections : 덱(deque), 카운터(Counter) 등의 유용한 자료구조를 포함하고 있는 라이브러리. 
• math : 필수적인 수학적 기능을 제공하는 라이브러리. 팩토리얼, 제곱근, 최대공약수(GCD), 삼각함수 관련 한수부터 파이(pi)와 같은 상수를 포함.

내장 함수

내장 함수는 프로그램 작성에 있어 가장 기본적이면서 필수적인 기능을 포함하고 있으며,
별도의 import 명령어 없이 바로 사용할 수 있다. 

 

대표적인 내장 함수는 input(), print()이다.

2023.10.03 - [Programming language/Python] - [Python] 입출력 : input(), sys.stdin.readline(), print(), 줄 바꿈

[Python] 입출력 : input(), sys.stdin.readline(), print(), 줄 바꿈

그 외의 내장 함수로는 sum(), min(), max(), eval(), sorted() 등이 있다.

sum()

iterable 객체가 입력으로 주어졌을 때, 모든 원소의 합을 반환하는 함수.

+) 파이썬에서 iterable 객체란 반복 가능한 객체를 뜻하며, 리스트, 사전 자료형, 튜플 자료형 등이 이에 해당한다.

result = sum([1, 2, 3, 4, 5])
print(result)	# 15

min(), max()

min() 함수는 파라미터가 2개 이상 들어왔을 때 가장 작은 값을 반환하고, max() 함수는 파라미터가 2개 이상 들어왔을 때 가장 큰 값을 반환한다.

result1 = min(7, 3, 5, 2)
result2 = max(7, 3, 5, 2)
print(result1, result2)	# 2 7

eval()

수학 수식이 문자열 형식으로 들어오면 해당 수식의 계산 결과를 반환하는 함수.

result = eval("(6 + 5) * 7")
print(result)	# 77

sorted()

iterable 객체가 들어왔을 때 정렬된 결과를 반환하는 함수.

 

reverse 속성으로 내림차순 정렬을 할 수 있다. (default는 오름차순 정렬 결과를 반환)

result = sorted([9, 1, 8, 5, 4])	# default : 오름차순
print(result)	# [1, 4, 5, 8, 9]
result = sorted([9, 1, 8, 5, 4], reverse = True)	# 내림차순으로 정렬
print(result)	# [9, 8, 5, 4, 1]

파이썬에서는 리스트의 원소로 리스트나 튜플이 존재할 때 특정 기준에 따라 정렬을 수행할 수 있는데,

key 속성으로 정렬 기준을 명시할 수 있다.

# 리스트의 원소로 튜플이 존재할 때
# 원소를 튜플의 두 번째 원소(수)를 기준으로 내림차순 정렬
result = sorted([('김', 15), ('이', 64), ('박', 38)], key = lambda x: x[1], reverse = True)
print(result)	# [('이', 64), ('박', 38), ('김', 15)]

 

리스트와 같은 iterable 객체는 기본으로 sort() 함수를 내장하고 있기 때문에 sorted()를 사용하지 않고도 정렬할 수 있다.
이 경우 리스트 객체의 내부 값이 정렬된 값으로 바로 변경된다.

data = [9, 1, 8, 5, 4]
print(sorted(data))	# [1, 4, 5, 8, 9]
print(data)	# [9, 1, 8, 5, 4]

data.sort()
print(data)	# [1, 4, 5, 8, 9]

자세한 내용은 아래 포스팅 참고 !

2023.10.04 - [Programming language/Python] - [Python] 리스트 정렬, 역순 정렬 : sort()와 sorted(), reverse()와 reversed(), 슬라이싱, range()

[Python] 리스트 정렬, 역순 정렬 : sort()와 sorted(), reverse()와 reversed(), 슬라이싱, range()

itertools

itertools는 파이썬에서 반복되는 형태의 데이터를 처리하는 기능을 제공하는 라이브러리로,
제공하는 클래스는 매우 다양하지만 코딩테스트에서 가장 유용하게 사용할 수 있는 클래스는 permutations, combinations이다.

permutations

리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(= 순열)를 계산해준다.

 

permutations는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.

# 리스트에서 3개(r = 3)를 뽑아 나열하는 모든 경우 출력하기
from itertools import permutations

data = ['A', 'B', 'C']
result = list(permutations(data, 3))	# 모든 순열 구하기
print(result)	# [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')]

combinations

리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 순서를 고려하지 않고 나열하는 모든 경우(= 조합)를 계산해준다.

# 리스트에서 2개(r = 2)를 뽑아 순서 상관없이 나열하는 모든 경우 출력하기
from itertools import combinations

data = ['A', 'B', 'C']
result = list(combinations(data, 2))
print(result)	# [('A', 'B'), ('A', 'C'), ('B', 'C')]

product

permutations와 같이 리스트와 같은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우(= 순열)를 계산해주는데, 다만 r개의 데이터를 뽑을 때 원소를 중복하여 뽑는다.

 

product 객체를 초기화할 때는 뽑고자 하는 데이터의 수를 repeat 속성값으로 넣어준다.

product는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환하여 사용한다.

# 리스트에서 중복을 포함해 2개(r = 2)를 뽑아 나열하는 모든 경우 출력하기
from itertools import product

data = ['A', 'B', 'C']
result = list(product(data, repeat = 2))
print(result)	# [('A', 'A'), ('A', 'B'), ('A', 'C'), ('B', 'B'), ('B', 'C'), ('C', 'C')]

heapq

파이썬에서는 힙(Heap) 기능을 위해 heapq 라이브러리를 제공한다.

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

PriorityQueue 라이브러리를 사용할 수 있으나, 코딩 테스트 환경에서는 보통 heapq가 더 빠르게 동작하므로 heapq를 이용하자.

최소 힙

파이썬의 힙은 최소 힙(Min Heap)으로 구성되어 있다.

보통 최소 힙 자료구조의 최상단 원소는 항상 '가장 작은' 원소이기 때문에 단순히 원소를 힙에 전부 넣었다 빼는 것만으로도 시간 복잡도 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])
print(result)	# [1, 2, 3, 4, 5, 6, 7, 8, 9, 0]

최대 힙

파이썬에서는 최대 힙(Max Heap)을 제공하지 않기 때문에,
heapq 라이브러리를 이용해 최대 힙을 구현해야 할 때는 원소의 부호를 변경하는 방식을 사용한다.

힙에 원소를 삽입하기 전에 잠시 반대로 바꾸었다가, 힙에서 원소를 꺼낸 뒤에 다시 원소의 부호를 바꾸어 최대 힙을 구현해 내림차순 힙 정렬을 구현한다.

# 내림차순 힙 정렬을 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])
print(result)	# [9, 8, 7, 6, 5, 4, 3, 2, 1, 0]

bisect

파이썬에서 이진 탐색을 쉽게 구현할 수 있도록 제공하는 라이브러리로,

'정렬된 배열'에서 특정 원소를 찾아야 할 때 매우 효과적으로 사용된다.

bisect 라이브러리에서 가장 중요하게 사용되는 함수는 아래와 같다. 이 두 함수는 시간 복잡도 O(logN)에 동작한다.

 

• bisect_left(a, x) : 정렬된 순서 유지하면서 리스트 a에 데이터 x를 삽입할 가장 왼쪽 인덱스를 찾는 메서드.
• bisect_right(a, x) : 정렬된 순서 유지하면서 리스트 a에 데이터 x를 삽입할 가장 오른쪽 인덱스를 찾는 메서드.

# 정렬된 리스트 [1, 2, 4, 4, 8]에 데이터 4 삽입하기
from bisect import bisect_left, bisect_right

a = [1, 2, 4, 4, 8]
x = 4
print(bisect_left(a, x), bisect_right(a, x))	# 인덱스값 반환. 2 4

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

# 정렬된 리스트에서 값이 특정 범위에 속하는 원소의 개수 구하기
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_right(a, left_value)
    	return right_value - left_value
    
# 리스트 선언
a = [1, 2, 3, 3, 3, 3, 4, 4, 8 9]

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

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

count_by_range(a, left_value, right_value) 함수는 정렬된 리스트에서 값이 [left_value, right_value]에 속하는 데이터의 개수를 반환한다.
다시 말해, 원소의 값을 x라 할 때, left_value ≤ x ≤ right_value 인 원소의 개수를 O(logN)으로 빠르게 계산할 수 있다.

collections

유용한 라이브러리를 제공하는 표준 라이브러리이다.

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

deque

보통 파이썬에서는 deque를 사용해 큐를 구현한다. 별도로 제공되는 Queue 라이브러리는 일반적인 큐 자료구조를 구현하는 라이브러리가 아니다.

 

기본 리스트 자료형은 데이터 삽입, 삭제 등의 다양한 기능을 제공하며, 리스트가 있을 때 중간에 특정 원소를 삽입할 수도 있으나,

리스트 자료형은 append() 메서드로 데이터를 추가하거나 pop() 메서드로 데이터를 삭제할 때 '가장 뒤쪽 원소'를 기준으로 수행되기 때문에, 앞쪽에 있는 원소를 처리할 때에는 리스트에 포함된 데이터의 개수에 따라 많은 시간이 소요될 수 있다. 리스트에서 앞쪽에 있는 원소를 삭제하거나 앞쪽에 새 원소를 삽입할 때의 시간복잡도는 O(N)

deque에서는 리스트 자료형과 다르게 인덱싱, 슬라이싱 등의 기능은 사용할 수 없으나,
연속적으로 나열된 데이터의 시작 부분이나 끝 부분에 데이터를 삽입이나 삭제할 때에는 매우 효과적으로 사용될 수 있다. 

 

	리스트	deque
가장 앞쪽에 원소 추가	O(N)	O(1)
가장 뒤쪽에 원소 추가	O(1)	O(1)
가장 앞쪽에 있는 원소 제거	O(N)	O(1)
가장 뒤쪽에 있는 원소 제거	O(1)	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]

Counter

collections 라이브러리의 Counter는 등장 횟수를 세는 기능을 제공한다.

iterable 객체(리스트 등)가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장했는지를 알려주기 때문에 원소별 등장 횟수를 세는 기능이 필요할 때 사용된다.

from collections import Counter

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

print(counter['blue'], counter['green'])	# 3 1
print(dict(counter))	# 사전 자료형으로 변환. {'red': 2, 'blue': 3, 'green': 1}

math

자주 사용되는 수학적 기능을 포함하고 있는 라이브러리이다.

factorial()

factorial(x) 함수는 x! 값을 반환한다.

import math

print(math.factorial(5)	# 5 팩토리얼 출력. 120

sqrt()

sqrt(x) 함수는 x의 제곱근을 반환한다.

import math

print(math.sqrt(7))	# 7의 제곱근 출력. 2.6457513110645907
x = math.sqrt(7) ** 2
print(x)	# 7

gcd()

최대 공약수를 구하기 위해 a와 b의 최대 공약수를 반환하는 gcd(a, b) 함수를 이용할 수 있다.

import math

print(gcd(21, 14))	# 21과 14의 최대 공약수 출력. 7

상수 pi, 자연상수 e

math 라이브러리는 수학 공식에서 자주 등장하는 상수인 파이(pi)나 자연상수 e를 제공한다.

import math

print(math.pi)	# 파이(pi) 출력. 3.141592653589793
print(math.e)	# 자연상수 e 출력. 2.718281828459045