Python에는 많은 내장 함수들과 모듈들이 있습니다. 이는 많은 경우에 사용자가 직접 만든 것들보다 빠르며, 사용도 간편합니다. 특히 알고리즘 문제를 해결할 때에도 매우 유용합니다. 많은 자료 구조들을 제공하며, 문제를 해결하는데 최소한의 시간 복잡도로 문제들을 해결 해 줍니다. C++의 STL(Standard Template Library) 같은 느낌으로 생각하면 되겠습니다. 또한, 자료 구조 뿐만 아니라, 최대 공약수, 최댓값, 최솟값, 팩토리얼 값들을 구해주는 여러 가지 함수들을 제공 해 줍니다.
알고리즘 문제를 해결 하는데 자료 구조는 매우 중요한 역할을 합니다. 어떤 문제에 어떤 자료 구조를 쓰느냐에 따라 시간 복잡도는 천차 만별이기 때문입니다. 그 뿐만 아니라, 특정 알고리즘 문제는 특정 자료 구조 로만 시간 내에 해결 할 수 있기 때문에, Python에 있는 여러 가지 자료 구조들에 대한 이해는 알고리즘 문제를 해결 하는데에 필수적입니다.
deque는 양방향 큐로, 큐로도 사용 가능하고, 스택으로도 사용 가능하고, 양방향 큐로도 사용 가능합니다. collections 모듈에 있으며, deque 객체의 더 많은 method들이 궁금하면 해당 Python Document에서 확인 해 주시기 바랍니다.
from collections import deque
d = deque([1, 2, 3])
d.append(4) # deque의 오른쪽에 4를 더함.
d.append(0) # deque의 왼쪽에 0을 더함.
d.pop() # deque의 가장 오른쪽 값을 지우고 반환함.
d.popleft() # deque의 가장 왼쪽 값을 지우고 반환함.
d.extend([4, 5, 6]) # deque의 오른쪽에 iterable 한 객체의 원소들을 더함.
d.extendleft([-2, -1, 0]) # deque의 왼쪽에 iterable 한 객체의 원소들을 더함.
d.reverse() # deque의 원소들의 순서를 뒤집음.
d.rotate(1) # deque의 원소들의 순서를 한 칸씩 회전 시킴.
d[3] # deque의 3번째 원소를 반환함.
d.clear() # deque의 값을 비움.heapq 모듈은 일반 list를 heap처럼 사용할 수 있도록 도와주는 모듈입니다. 기본적으로 Python에 내장 되어 있는 heapq 모듈은 최소 힙을 위해 만들어 졌기 때문에 최대 힙을 만들기 위해서는 데이터의 처리가 필요합니다. (숫자라면 -를 붙이는 방볍이 대표적입니다.) 우선순위 큐를 만드는 데에 주로 사용합니다. 삽입, 제거의 시간 복잡도는 O(log n) 입니다.
list 객체에서 heap 사용하기.import heapq
h = []
heapq.heappush(h, 3) # 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, 9) # 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, 7)
heapq.heappush(h, 8)
heapq.heappush(h, 5)
heapq.heappush(h, 1)
for _ in range(6):
print(heapq.heappop(h)) # 작은 값부터 출력된다.
import heapq
h = []
heapq.heappush(h, -3) # 첫 번째 파라미터에는 list 객체가
heapq.heappush(h, -9) # 두 번째 파라미터에는 삽입하려는 객체가 들어간다.
heapq.heappush(h, -7) # 단, 원래 넣으려는 값에 -를 붙여주고
heapq.heappush(h, -8) # 출력시에도 -을 붙여준다.
heapq.heappush(h, -5)
heapq.heappush(h, -1)
for _ in range(6):
print(-heapq.heappop(h)) # 큰 값부터 출력된다.import heapq
h = [3, 9, 1, 4, 2]
heapq.heapify(h) # 파라미터로 list 객체를 받는다.
for _ in range(6):
print(-heapq.heappop(h)) # 작은 값부터 출력된다.더 자세한 사용법은 해당 Python Document에서 확인해 주시기 바랍니다.
아쉽게도 Python 내장 모듈 중에는 Tree, Linked List를 구현한 구현체는 없습니다. 직접 만들어야 하죠.
또한, 여러 가지 자료 구조들의 시간 복잡도를 궁금해 하시는 분들은 Time Complexity 문서를 참고 해 주세요!
Python 내부에는 탐색, 계산, 삽입 등을 위한 여러 가지 함수들이 있습니다. 알고리즘 문제를 풀 때 필요한 몇 개의 것들만 예시로 보여 드리겠습니다.
bisect 모듈은 이미 정렬되어 있는 list의 정렬 상태를 유지하기 위해 사용되는 모듈입니다. 이를 이용해서, 기존에 있는 list의 정렬 상태를 유지 할 수 있고, 이를 응용해서 Binary Search 또한 구현할 수 있습니다.
index 찾기import bisect
arr = [1, 2, 3, 3, 4, 5]
print(bisect.bisect_left(arr, 6)) # 6이 들어가야 하는 Index인 6을 반환
print(bisect.bisect_right(arr, 6)) # arr에 6이 없기 때문에 위와 똑같은 값을 반환한다.
print(bisect.bisect_left(arr, 3)) # 중복 되는 값 제일 왼쪽, 2를 반환한다.
print(bisect.bisect_right(arr, 3)) # 중복 되는 값 제일 오른쪽 + 1, 4를 반환한다.
bisect.insort_left(arr, 3) # 중복 되는 값 왼쪽에 삽입
bisect.insort_right(arr, 3) # 중복 되는 값 오른쪽에 삽입
print(arr)Binary Search 구현from bisect import bisect_left
arr = [1, 2, 3, 3, 4, 5]
def bs(arr, x):
i = bisect_left(arr, x) # 들어가야 하는 '제일 왼쪽' index 반환
if i != len(arr) and arr[i] == x: # 들어가야 하는 index가
return i # 마지막 index + 1 이라면, arr에 x가 없는 것
else: # arr[i] == x가 아니라면, arr에 x가 없는 것
return -1
a = [1, 2, 4, 4, 8]
x = 4
res = bs(a, x)
if res == -1:
print(x, "는 없습니다!")
else:
print("첫번째", x, "가 등장한 위치는", res) 더 자세한 사용법은 해당 Python Document에서 확인해 주시기 바랍니다.
math 모듈은 많은 수학 계산과 관련된 함수들을 가지고 있습니다.
import math
print(math.factorial(5)) # 5! = 120 반환
print(math.gcd(40, 30)) # 40과 30의 공약수 반환
print(math.floor(2.5)) # 2.5의 내림 반환 (2)
print(math.ceil(2.5)) # 2.5의 올림 반환 (3)
print(math.fabs(-5)) # -5의 절댓값 반환 (5)더 자세한 사용법은 해당 Python Document에서 확인해 주시기 바랍니다.
사실, 이 글의 분량으로 담을 수 없는 내용들이 많습니다. 예를 들어 collections 모듈에는 이 글에서 설명하지 않은 구현 상에 도움을 주는 구조체들이 많다던지, math 모듈에 Python 3.8 버전에 업데이트 된 함수들 이라던지.. 딱히 몰라도 알고리즘 문제를 푸는데 문제는 없지만, 한 번쯤은 알아 보는 것도 괜찮은 것 같습니다!
다음 시간에는 Python으로 여러 가지 유형의 알고리즘 문제를 풀 때 필요한 간단한 팁들로 돌아 오겠습니다!