파이썬은 인터프리터 언어로 기본적인 성능 면에서 여러 페널티를 안고 가게 된다. 대신 구현에서 복잡한 메모리 구현 등을 생각하지 않고 알고리즘 자체만 집중해서 구현할 수 있다는 장점도 있다. 하지만 알고리즘을 잘 짜더라도 입출력, 연산 등에서 시간이 너무 오래 걸려 버리는 일이 있는데, 이런 경우를 미리 방지하는 것이 중요하다.
pypy3가 python3에 비해 일반적으로 빠르지만, 일부 약점이 되는 부분도 있다.
조금 더 bare metal에 가까운 메소드를 이용해보자. sys.stdin.readline()을 하면 끝에 \n까지 입력이 되므로, strip()을 해 주는 것이 필요할 수 있다. 여러 수를 한 줄에서 바로 파싱하는 것이 가능하다.
a = int(input()) # slow
b = int(sys.stdin.readline().strip()) # fast
# multiple numbers (use map)
p, q, r = map(int, sys.stdin.readline().strip().split())
# multiple numbers as list (use list comprehension)
numbers = [int(x) for x in sys.stdin.readline().strip().split()]
출력의 경우 보통 “한 개만 출력”하는 등의 조건이 많기 때문에 큰 문제는 되지 않지만, 대안이 되는 메소드도 존재한다. 출력을 많이 하는 경우에 생각해볼 수 있다. 또 여러 줄을 하나의 string으로 만든 뒤 출력하는 것도 생각해볼 수 있다. 이를 위해서는 join 함수를 쓸 수 있다. 다만 가장 빠른 것은 for 문에 바로 sys.stdout.write를 쓰는 것이라고 한다.
print("answer") # slow
sys.stdout.write("answer\n") # fast
strings = ["first", "second", "third", "fourth", "fifth"]
print("\n".join(strings)) # 여러 줄에 걸쳐 strings의 각 원소를 출력
num = [1, 2, 3, 4, 5]
print(" ".join(map(str, num))) # 한 줄에 \s로 나누어 num의 각 원소를 출력
파이썬의 기본 재귀 깊이는 1000이다(sys.getrecrusionlimit()). 재귀 깊이가 1000번을 넘어가면 터지게 되어 있다. sys.setrecursionlimit(10 ** 9) 같은 식으로 재귀 깊이를 늘릴 수 있지만 애초에 함수 스택을 이용한 재귀를 구현하기에는 파이썬이 느리다고 생각한다. 일반적인 재귀 방식이면 차라리 deque를 이용해서 직접 재귀 스택을 만드는 쪽이 낫다. pypy3의 경우 제한이 10만 정도라고 하는데, 여기서 더 늘릴 수 없다는 것이 함정이다. 그러니 백트래킹 같은 경우가 아니면 deque 자료구조를 이용하도록 하자.
파이썬의 장점 중 하나는 다양한 패키지가 존재한다는 것이다. 기본적으로 패키지에서 제공하는 기능을 직접 구현할 수 없다면 한 번 만들어 보는 것이 공부가 될 것이고, 직접 만들 수 있다면 효율적인 구현을 위해 패키지를 가져다 쓰는 것이 도움이 될 것이다. 다만 각 패키지의 특성과 장단점을 이해해야 할 것이다.
파이썬 리스트 및 다른 자료구조의 시간 복잡도를 여기서 확인할 수 있다. 리스트에 대해 몇 가지 중요한 점을 살펴보자.
from collections import deque
queue = deque()
queue.appendleft(1) # O(1)
queue.appendleft(2) # O(1)
queue.appendleft(3) # O(1)
print(queue.pop()) # 1
print(queue.pop()) # 2
print(queue.pop()) # 3
또 중복이 없는 경우, x in s 식의 구문을 자주 써야 하는 경우에는 set 자료구조를 이용할 수 있다. 순서도 저장해야 하면, 그냥 리스트와 set을 같이 운용하면 된다. 원한다면 클래스로 만들어도 좋다. 한편 자료구조가 비어 있는 경우 evaluate를 하면 None –> False로 판정된다. 따라서 if list: 같은 식으로 쓰는 것이 가능하다.
이분탐색의 경우 bisect 패키지를 이용할 수 있다. bisect.bisect(s, a)는 원소 a가 들어갈 자리에 해당하는 index를 반환하며, 동일한 원소가 있을 때는 그 원소보다 오른쪽 index를 반환한다. bisect.bisect_left(s, a)의 경우 왼쪽 index를 반환한다. C++의 lower_bound(), upper_bound()와 비슷하다. 이분탐색이 필요할 경우 여러 방법으로 (a와 동일한 원소의 갯수라던가) 응용할 수 있다.
import bisect
numbers = [1, 2, 4, 5, 8, 10, 12]
bisect.bisect_left(numbers, 4) # 2
bisect.bisect(numbers, 4) # 3
다만 정렬된 리스트를 만들기 위해서는 빈 리스트에 삽입을 한 뒤(O(1)) 마지막에 정렬을 하는 쪽이(O(n log(n))) 삽입시 정렬된 위치에 넣는 것보다(O(n)) 시간복잡도 면에서 유리하다. 마찬가지로 리스트에서 삭제를 하는 연산은 시간복잡도가 크다는 것을 유의하자.
최소 힙을 구현한 heapq 패키지를 이용할 수 있다. 별도의 자료구조를 만든 것이 아니라, 기존의 자료구조를 변수로 받는 일련의 함수들을 제공한다.
import heapq
numbers = [6, 3, 4, 7, 10, 2]
heapq.heapify(numbers) # O(n)으로 numbers를 최소 힙으로 만든다
# numbers = [2, 3, 4, 7, 10, 6]
# numbers[0]이 최소라는 것만 보장되며, 다른 원소에 대해서는 정렬이 보장되지 않는다.
print(heapq.heappop(numbers)) # 2
# numbers = [3, 6, 4, 7, 10], 내부 순서는 바뀔 수 있다.
heapq.heappush(numbers, 5)
# numbers = [3, 6, 4, 7, 10, 5]
heapq는 최소 힙만을 지원하지만, 튜플의 첫 번째 값을 key로 사용한다는 특성을 이용해 간단하게 최대 힙으로 바꿀 수 있다(N을 넣는 대신, (-N, N)을 넣으면 된다). 또한 힙을 만들 때에는 매번 heappush()를 하기 보다 일단 넣은 뒤 heapify하는 것이 속도 면에서 유리하다.
물론 직접 구현할 수도 있지만, itertools 패키지를 이용해 쉽게 원하는 길이의 순열과 조합을 얻을 수 있다. 이름답게 iterable이 반환되므로 적절히 이용하도록 하자.
import itertools
num = [1, 2, 3, 4, 5]
itertools.combinations(num, 3)
# 123 124 125 134 135 145 234 235 245 345
itertools.permutations(num, 3)
# 123 124 125 132 134 135 142 143 145 152 153 154 213 214 ... 541 542 543
itertools의 다른 용도는 패키지 공식 문서를 찾아보자.
몇몇 자료구조의 경우 직접 만들어 주어야 한다. 클래스를 이용하면 된다.
자료구조에서 일종의 원소 컨테이너로 많이 쓰인다고 할 수 있다.
class Node:
def __init__(self, element):
self.element = element
self.visited = False # 방문 여부, DFS/BFS/길찾기 등에 쓰인다
self.connected = [] # 연결된 다른 노드, DFS/BFS/길찾기 등에 쓰인다
self.parent = None # 부모 노드, Tree 구현
self.left = None
self.right = None # 좌 우 자식 노드, binary tree 구현
self.rank = 0 # Rank, tree height, ranked disjoint set에 쓰인다
def __str__(self):
return str(element) # str(Node)를 했을 때, print(Node)를 했을 때 출력하고 싶은 값.
# ...
여기에 각종 메소드들을 추가할 수 있다.
파이썬에는 여러 자료구조가 존재하지만, 분리 집합의 경우 PL 환경에서는 직접 구현해줘야 한다. 분리 집합이란 집합 내의 원소들이 서로 같은 집합에 속하거나, 속하지 않는 것을 구현하는 자료구조로 다음과 같은 연산이 필요하다.
Union(a, b): a와 b가 같은 집합에 속하도록 만든다.Find(a): 원소 a가 속한 집합의 head를 찾는다. 다른 집합에 속하지 않는다면 자기 자신을 반환한다.add(a) 같은 메소드를 추가로 구현해서, 나중에 원소를 추가할 수 있게 만든다.Same_group(a, b) 를 Find(a)를 이용해 구현할 수도 있다.이 자료구조는 Tree를 이용해 만든다. 생성될 때는 각 원소마다 Node를 만들고, 자기 자신을 parent로 놓는다. Union 연산에서는 둘 중 앞에 있는 것의 parent를 뒤에 있는 것의 parent로 만들거나, 그 반대로 할 수 있다. 여기서 앞에 있는 것의 parent를 타고 올라가면서, 그 parent들을 맨 위에 존재하는 parent로 갱신하는 것도 가능하다. 또 어느 것을 parent로 할 지에 대해 rank를 이용하는 것도 가능한데, rank는 tree의 높이로 계산해서 갱신하면 된다. rank가 낮은 쪽에 추가해주는 방식을 이용하면 tree들의 rank를 고르게 유지할 수 있다. Find 연산에서는 parent를 타고 올라가서 맨 위의 parent를 반환하면 된다. 맨 위의 parent인지 판별하려면, parent가 자기 자신과 같은지 판단하면 된다. 어떻게 구현해야 할지는 문제마다 차이가 있으므로 한 번 만들어 두고 조금씩 바꿔서 쓰면 된다.
DP를 위해서는 (보통) 2차원 배열을 사용한다. 파이썬에서 배열을 제대로 초기화하려면 list comprehension을 이용하면 된다. 많은 DP 풀이에서 1부터 N까지의 범위를 이용하는데, 굳이 0부터 N-1의 범위로 바꾸려 머리 싸매는 것보다 그냥 크기를 1씩 높여서 초기화는 것이 편하다. 2차원 배열에 대해, 내부까지 복사한 deep copy를 만드려면 copy.deepcopy()를 이용해야 한다(출처). 커스텀 클래스의 경우 __copy__(), __deepcopy__() 메소드를 구현해야 할 수 있다.
import copy
N = int(input()) # N = 3
dp = [[0 for _ in range(N)] for _ in range(N)]
print(dp) # dp = [[0, 0, 0], [0, 0, 0], [0, 0, 0]]
dp2 = [[0 for _ in range(N+1)] for _ in range(N+1)]
print(dp[N][N]) # 0 (오류나지 않음)
dp3 = copy(dp2) # 내부 배열의 내용은 복사되지 않고 dp2 내부의 동일한 대상을 가리킴
dp4 = copy.deepcopy(dp2) # 이렇게 해야 내부 배열까지 제대로 복사됨