[Python] 알고리즘을 위한 주요 라이브러리와 유의점

이번 포스팅에서는 Python으로 알고리즘 문제를 해결할 때 주로 사용하는 라이브러리와 유의점에 대해 알아보려고 한다. 해당 라이브러리들을 적절히 사용하면 손쉽게 문제를 해결할 때가 종종 있다고 한다.

 

Python 주요 라이브러리를 알아보자.

---

해당 포스팅에서 소개하는 주요 라이브러리들 이외에는 여기를 참고해서 확인해보자. 이외의 라이브러리들도 사용해서 문제를 해결하는 경우도 자주 있다고 하니 해당 링크를 참고해서 찾아 사용하는 습관을 기르는 것을 권장한다.

1. 내장함수

내장함수란, print 문이나 input 문 같은 기본 입출력 기능부터 sorted 같은 정렬 기능을 포함하는 기본 내장 라이브러리다. 

1-1. sum

sum 함수는 iterable한 객체(리스트, 딕셔너리, 튜플, 집합자료)가 입력으로 주어졌을 때, 모든 원소의 합을 반환한다. 

 

import sys

array = [1, 2, 3, 4]
res = sum(array)
print(res)

1-2. min

min 함수는 파라미터가 2개 이상으로 들어왔을 때 가장 작은 값을 반환한다. 반대의 함수로는 max 함수가 존재한다.

 

import sys

array = [1, 3, 5, 7, 9]
print(min(array))

print(min(0, 2, 5, 7)) # 0 출력

1-3. eval

인자로 수학 수식이 문자열 형식으로 들어오면 해당 수식을 자동으로 계산해 결과를 반환한다.

 

import sys

equation = "(3 + 5) * 2"
res = eval(equation)
print(res)

2. itertools

2-1. permutations, combinations

itertools 라이브러리는 파이썬에서 반복되는 데이터를 처리하는 기능을 포함한다. 대표적으로 자주 사용되는 함수는 permutations, combinations 이다. 즉, 순열과 조합이다. 참고로 순열은 원소가 동일해도 순서가 다른 것도 서로 다른 것으로 간주하지만 조합은 그렇지 않다. 순열, 조합 라이브러리는 클래스이므로 객체 초기화 이후에는 리스트 자료형으로 변환해 사용한다. 그리고 반환되는 순열, 조합 결과는 튜플로 구성되어 있다. 입력, 출력 예시는 다음과 같다.

 

from itertools import permutations, combinations

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

permut = list(permutations(elements, 2))
print('순열:', permut)

comb = list(combinations(elements, 2))
print('조합:', comb)

 

순열과 조합 결과 화면

2-2. product

product는 인자로 받은 iterable 객체에서 r개의 데이터를 뽑아 일렬로 나열하는 모든 경우의 수를 계산한다. 단, 원소를 중복하여 뽑을 수 있다. 뽑고자 하는 데이터 수는 repeat 인자로 넣어줄 수 있다. 즉, 중복을 허용한 순열(permutations)라고 보면 된다.

 

from itertools import product

elements = {'A', 'B', 'C'}  # 집합자료형도 iterable한 객체이다

res = list(product(elements, repeat=2))
print(res)

 

출력 화면

2-3. combinations_with_replacement

조합을 계산하는 combinations 라이브러리와 유사하지만 차이점은 원소를 중복해서 뽑을 수 있다는 것이다. 즉, 중복을 허용한 조합(combinations) 이다. 이 라이브러리도 클래스 이므로 객체 초기화 시 리스트로 감싸주어서 결과를 반환할 수 있다. 코드 입출력은 combinations 라이브러리와 비교해서 살펴보자. 

 

from itertools import combinations_with_replacement, combinations

elements = ('A', 'B', 'C')

res = list(combinations_with_replacement(elements, 2))
print('combinations_with_replacement:\n', res)
print('-'*50)

res2 = list(combinations(elements, 2))
print('combinations:\n', res2)

 

출력 화면

 

보다시피 원소를 중복해서 뽑느냐 여부에 따라 결과가 달라지는 것을 볼 수 있다.

3. bisect

파이썬에서는 이진 탐색을 쉽게 구현할 수 있도록 해주는 bisect 라이브러리를 제공한다. 이진 탐색은 이미 정렬된 데이터에서만 사용이 가능한데, '정렬된 배열'에서 특정한 원소를 찾아야 할 때 매우 효과적으로 사용이 가능하다. 가장 중요하게 사용되는 함수 2가지는 bisect_left() 함수와 bisect_right() 함수이다. 두 함수의 쓰임과 결과는 예시 코드로 확인하는 것이 가장 직관적이다.

 

from bisect import bisect_left, bisect_right

array = [1, 2, 4, 4, 8]
x = 4

print(bisect_left(array, x))   # 인덱스 번호 2 출력
print(bisect_right(array, x))  # 인덱스 번호 4 출력

 

위 코드를 해석하자면, 이미 정렬된 array 배열에다가 4인 x 원소를 삽입하려고 한다. 이 때 bisect_left 는 x를 array에 삽입이 가능한 가장 왼쪽의 인덱스 번호를 반환하고, bisect_right는 x를 array에 삽입이 가능한 가장 오른쪽의 인덱스 번호를 반환하게 된다. 이 함수들을 응용하게 되면 이미 정렬된 데이터에서 특정 범위에 속하는 원소의 개수를 구하는 데 큰 도움이 된다. 아래의 함수를 살펴보자.(착각하기 쉬운 점은 특정 원소가 있는 가장 왼쪽의 인덱스를 반환하는 것이 아닌 그 인덱스보다 1이 작은 인덱스를 반환한다. 반대로 가장 오른쪽의 인덱스를 반환하는 것이 아닌 그 인덱스보다 1이 큰 인덱스를 반환한다. 헷갈린다면 아래 그림을 꼭 보자.)

 

bisect 함수들이 반환하는 인덱스 값들

 

from bisect import bisect_left, bisect_right

def count_by_range(array, left_val, right_val):
    left_idx = bisect_left(array, left_val)
    right_idx = bisect_right(array, right_val)
    print(left_idx, right_idx)
    return right_idx - left_idx


a = [1, 2, 3, 3, 3, 3, 4, 4, 8, 9]

print(count_by_range(a, 4, 4))  # 2반환
# -1 은 주어진 배열의 가장 작은 값보다 작으므로 0번 인덱스를 반환함!
print(count_by_range(a, -1, 3)) # 6반환

4. collections

4-1. deque

deque 라이브러리는 기존에 우리가 배웠던 BFS(너비우선탐색)를 구현하기 위해 사용했던 적이 있다. deque는 파이썬에서 기본적으로 제공하는 리스트와는 달리 원소를 앞/뒤에 추가 또는 제거 모두 가능하며 스택과 큐 자료구조의 기능을 모두 갖고있다고 할 수 있다. 하지만 리스트 자료형과는 달리 슬라이싱이나 인덱싱 기능이 불가능하다. deque 라이브러리 사용 예시는 BFS 글에서 찾아볼 수 있으니 여기서는 생략하겠다.

4-2. Counter

Counter은 원소의 등장 횟수를 세는 기능을 한다. 리스트, 튜플과 같은 iterable한 객체가 주어졌을 때, 해당 객체 내부의 원소가 몇 번씩 등장하는지를 알려준다.(집합 자료형은 중복되는 값이 자동으로 제거되므로 애초에 입력으로 주어질 리 없음을 기억하자.) 원소별 등장 횟수를 셀 때 매우 유용하다. 그리고 인상적인 점은 Counter 객체를 딕셔너리로 감싸주면 자동으로 {'원소': 발생횟수} 형태로 반환해준다. 구체적인 예시는 다음을 살펴보자.

 

from collections import Counter

e_lst = ['red', 'blue', 'green', 'red', 'blue', 'yellow']
e_tuple = tuple(e_lst)

lst_cnt = Counter(e_lst)
tuple_cnt = Counter(e_tuple)

# red 원소의 발생횟수 조회 -> 딕셔너리처럼 key값으로 조회
print('Red:', lst_cnt['red'], tuple_cnt['red'])
print('Blue:', lst_cnt['blue'], tuple_cnt['blue'])
print('-'*50)

# 딕셔너리로 Counter 객체를 감싸면 자동으로 원소별 발생 횟수를 딕셔너리 자료구조로 만들어줌
print(dict(lst_cnt))
print(dict(tuple_cnt))

5. math

math 라이브러리는 자주 사용되는 수학적 기능을 포함하고 있다. 대표적으로 여기서는 팩토리얼, 제곱근, 최대공약수(GCD, Greatest Common Divisor)를 계산할 수 있다. 최소공배수(Least Common Multiple)은 lcm 함수를 사용할 수 있다. 단, 최소공배수 구하는 math.lcm() 함수는 현재 파이썬 3.9버전에 새롭게 나온 것이므로 그 이전의 버전에 대해서는 아래와 같이 최대공약수를 활용해 직접 구현해주자.(다양한 파이썬 버전일 때 최소공배수를 구하는 방법은 여기를 참고하자)

 

import math

print('Factorial:', math.factorial(5))
print('제곱근:', math.sqrt(81))
print('최대공약수(GCD):', math.gcd(10, 19))
print('최소공배수(LCM):', math.lcm(10, 19))

# 파이썬 3.8이하일 때 최소공배수(LCM) 구하는 방법
def lcm(a, b):
    return (a * b) // math.gcd(a, b)

6. heapq

파이썬에서는 힙 기능을 위해 heapq 라이브러리를 제공한다. heapq는 개선된 다익스트라 최단 경로 알고리즘 뿐만 아니라 다른 알고리즘에서도 우선순위 큐 기능을 구현하고자 할 때 자주 사용된다. heapq 이외에 PriorityQueue 라이브러리를 사용할 수도 있지만, heapq가 더 빠르게 동작한다는 점에서 heapq 라이브러리를 더 자주 사용한다. 파이썬의 힙은 최소 힙으로 구성되어 있다. 최소 힙은 저장되는 데이터 중 첫 번째 원소가 가장 낮은 값 기준으로 정렬(오름차순 정렬)된다. 단순히 원소를 힙에 전부 넣었다가 빼는 것만으로도 시간 복잡도가 $O(NlogN)$이 된다.

 

힙에 원소를 삽입할 때는 heapq.heappush() 함수를 원소를 꺼내고자 할 때는 heapq.heappop() 함수를 사용한다. 이 때 사용하는 방법은 heapq.heappush(list, value)로 사용한다. heappop은 heapq.heappop(list)로 사용한다. 참고로 파이썬의 리스트 자료구조를 활용해 힙 정렬을 구현할 수 있긴 하지만 삭제할 때마다 모든 원소를 확인해서 우선순위를 고려해야 하기 때문에 최악의 경우 시간 복잡도 $O(N)$ 시간이 소요된다. 힙 정렬을 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


array = [1, 3, 5, 7, 9, 0, 2, 4, 8, 6]
res = heapsort(array)
print(res)

 

그렇다면 최대 힙을 heapq로 구현할 수는 없을까? 구현할 수 있다. heapq가 원초적으로 오름차순 정렬로 구현하기 때문에 정렬 기준의 원소값 부호만 적절히 바꾸어 준다면 최대 힙을 구현할 수 있다. 즉, 원소를 힙 자료구조에 넣을 때 부호를 바꾼 후 삽입 후, 다시 힙에서 꺼낼 때 부호를 다시 바꾸어준 후 빼주어 반환하게 되면 최대 힙을 구현할 수 있다.

 

import heapq

array = [1, 3, 5, 7, 9, 0, 2, 4, 8, 6]


def heapsort(iterable):
    h = []
    res = []
    for value in iterable:
        heapq.heappush(h, -value)
    for i in range(len(h)):
        res.append(-heapq.heappop(h))
    return res


res = heapsort(array)
print(res)

 

코드 2개를 잘 비교해보면 부호만 바뀐 것을 볼 수 있다.