Python 시간 복잡도 줄이는 팁

yejichoi·2023년 9월 21일
0

Algorithm

목록 보기
4/4
post-thumbnail

문제의 레벨이 올라갈수록 입력이 커지면서 시간 초과에 벽에 자주 부딪히는 일이 발생하였다.
그런 일들을 줄여가기 위해 모아온 자료들을 정리해서 올려본다.

입력 - sys 모듈의 readline() 메서드 사용

보통 입력을 받을 때 input() 메서드를 사용하지만, sys 모듈의 readline()을 사용하면 더 빠른 시간에 입력을 받을 수 있으며, 데이터가 많아질 수록 이 차이는 더 커진다.

리스트 컴프리헨션 - 곱셈 연산자 사용

똑같은 데이터를 반복적으로 리스트에 넣고 싶을 때, for 과 in range(n)을 사용할 수도 있지만, 곱셈 연산자를 사용하는 것이 더 빠르다.

그러나 여러 리스트를 만들 때에는 range 함수를 쓰도록 한다. 이는 리스트를 곱셈으로 만들 때에는 같은 참조를 하는 리스트 객체를 여러 개 만들기 때문에, 각 리스트가 다른 값을 담도록 하게 하고 싶을 때 한 리스트를 바꾸면 다른 모든 곱셈으로 만들어진 리스트들이 바뀌어지게 될 것이다.

import time

times = 100000000

start = time.time()

# for 과 in, range
i = [0 for _ in range(times)]
mid1 = time.time()
print(mid1-start)

# 곱셈 연산자
i = [0] * times
mid2 = time.time()
print(mid2-mid1)

출력

6.190709590911865
0.6791272163391113

큐와 우선순위 큐

큐를 구현할 때는 collections 모듈의 deque를 사용하고, 우선순위 큐를 구현할 때는 heapq

0개의 댓글