collections 모듈의 deque란?

어디서 문제가 생겼나?

python 소스 코드를 Ast 로 바꾸는 과정에서 deque 가 사용되었다.

 

 

 

 

---

무엇을 배웠나?

우리의 자전거 도둑을 막기 위한 자물쇠의 비밀번호 입력을 생각해보자. 비밀번호는, 만약 3자리 숫자라면, () () () 일 것이고, 각각의 () 에는 한 자리 숫자만 보인다. 하지만 그 한 자리 숫자가 0부터 1,2,3...9 까지 올 수 있기 때문에, 사실 원형으로 한 바퀴 둘러서, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 가 있는데 이 중에서 우리가 돌리는 것에 따라서

(0,1,2....9)

(1,2,3...0)

(2,3....1)

(3,4,...)

 

등등 이렇게 순서가 달라질 수 있다. deque 도 비슷한 기능이 있다. deque의 rotate 함수를 이용하면.

(1,2,3) --------> (2,3,1) -------> (3,1,2) 이런 식으로 돌려서 바꿔줄 수 있다.

 

또한, 서칭을 통해 알아본 deque의 장점은, deque는 가장 왼쪽, 그리고 가장 오른쪽의 값을 추가, 삭제하는 경우, 비용이 더 적게 든다.

deque는 O(1) 만큼의 시간 복잡도, 그렇지만 기존의 pop이나 append 는 O(N) 만큼의 시간이 걸린다고 한다.

 

 그 이유는, deque는 popleft, popright, appendleft, appendright이 따로 정의되어 있기 때문이다.

 

 

 

 

---

reference:

https://docs.python.org/ko/3/library/collections.html#collections.deque