덱은 double-ended queue를 줄인것이다. 이름에서 알 수 있듯이 양쪽으로 넣고 뺄 수 있는 큐를 의미한다. 기초 자료구조이지만 여기에 숨어있는 신기한 사실이 있다. 시간복잡도 덱의 장점은 앞, 뒤 어디서든지 삽입삭제가 $O(1)$이라는 것이다. 보통 학부 과정에서 덱을 구현하라는 과제를 받으면 리스트로 구현하여 삽입삭제를 $O(1)$로 끝내고 random access를 $O(N)$에 동작하도록 구현하게 된다. 하지만 실제로 내장된 deque를 사용해보면 어떨까? # python from collections import deque import time N = 1000000 arr = [i for i in range(N)] s = 0 start = time.time() for i in rang..
