오뚝이개발자

deque(double ended queue)는 양방향 연결리스트로 구현되어 있어 양 끝단에 접근이 가능하고 데이터의 삽입, 삭제가 용이하다.(단, 중간 데이터는 제외) 여기선 대표적으로 많이 쓰이는 5가지 operation에 대해 사용법을 정리하려고 한다. 아, 참고로 deque를 사용하려면 import collections.deque를 해주어야 한다. append(x), appendleft(x) append(x)는 오른쪽 끝에 데이터 x를 추가, appendleft(x)는 왼쪽 끝에 데이터 x를 추가한다. 리스트와 달리 deque는 doubly linked list라 둘의 시간복잡도는 모두 O(1)이다. pop(), popleft() pop()은 일반적으로 알고있는 그 pop 연산이 맞다. 즉, st..

시간복잡도 아래는 자주 등장하는 시간복잡도 표기들이다. 표에서 아래로 갈수록 수행시간이 오래 걸린다. list 리스트는 배열이다. 그렇기 때문에 사이즈가 커질수록 삽입과 삭제 연산이 비효율적으로 된다. 이럴 땐 차라리 deque를 쓰는 것이 효율적이다. Operation Average Worst Copy O(n) O(n) Append O(1) O(1) Pop last O(1) O(1) Pop intermediate O(k) O(k) Get item O(1) O(1) Set item O(1) O(1) Delete item O(n) O(n) sort O(nlogn) O(nlogn) min,max O(n) O(n) len O(1) O(1) collections.deque deque(double ended qu..