[파이썬 모듈 collections] - deque와 친해지기

kimminjunnn·2025년 4월 5일

목록 보기

16/311

파이썬으로 코딩테스트 문제를 풀다가

from collections import deque

에 대해 마주했고 꽤 자주 마주쳐서
이제는 좀 친해져야겠다 생각이 들어 정리해본다.

우선 deque 는 '덱' 이라 발음되고, "double-ended-queue" 에 줄임말이다.
양쪽에서 추가, 제거할 수 있는 자료구조이다.

1.deque 생성

from collections import deque

# 비어있는 deque 생성
d = deque()

# 초기 요소를 가진 deque 생성
d = deque([10, 20, 30])

2.요소 추가하기

append(x) : deque 의 오른쪽 끝에 요소 x를 추가한다.
appendleft(x) : deque의 왼쪽 끝에 요소 x를 추가한다.

오 양쪽에서 추가할 수 있다더니 왼쪽도 추가가 가능하네 실제로?

from collections import deque

MJdeque = deque([3,4,5]);

print(MJdeque);

MJdeque.append(6);
MJdeque.appendleft(2);
print(MJdeque);

하면 실제로

deque([3, 4, 5])
deque([2, 3, 4, 5, 6])

가 출력됨을 확인했다.

3.요소 제거하기

마찬가지로 pop() 과 popleft() 가 존재한다.
이는 검증을 하지 않겠다.

추가로 extend(iterable), extendleft(iterable) 과
rotate(n) 에 대해 알아보겠다.

그 전 iterable 이란

iterable

이터러블은 반복 가능한 객체를 의미한다.
멤버들을 하나씩 차례로 반환할 수 있는 어떤 객체라고 할 수 있다. 파이썬에서는 리스트, 튜플, 딕셔너리, 세트, 문자열 등이 이터러블에 속한다. 이 객체들은 for 루프를 사용해서 그 내용을 순회할 수 있다.

extend(iterable), extendleft(iterable)

extend(iterable) 은 이터러블의 모든 요소를 deque의 오른쪽 끝에 추가한다.

MJdeque = deque([3,4,5]); # deque([3,4,5]) 
MJdeque.extend([6,7,8]);  # deque([3,4,5,6,7,8])

뭔가 append로도 할 수 있지 않을까? 싶지만 append를 하게 될 경우 이렇게 된다.

MJdeque = deque([3,4,5]); # deque([3, 4, 5])
MJdeque.append([6,7,8]);  # deque([3, 4, 5, [6, 7, 8]])

이렇게 리스트 자체가 들어가버린다. 그러니 extend 숙지해놓자.
extendleft는 동일하게 왼쪽으로 들어간다.

rotate(n)

이는 deque를 n만큼 회전시킨다. n이 양수면 오른쪽, 음수면 왼쪽으로 회전한다.

from collections import deque
d = deque([1, 2, 3, 4, 5])
d.rotate(2)  # 오른쪽으로 두 칸 회전
print(d)  # 출력: deque([4, 5, 1, 2, 3])

d.rotate(-3)  # 왼쪽으로 세 칸 회전
print(d)  # 출력: deque([2, 3, 4, 5, 1])

reverse(n)

deque의 모든 요소의 순서를 뒤집는다.

d = deque([1, 2, 3, 4, 5])
d.reverse()
print(d)  # 출력: deque([5, 4, 3, 2, 1])

maxlen

eque를 생성할 때 maxlen을 설정하면, deque의 최대 길이를 제한할 수 있다. 새로운 요소가 추가될 때 deque의 길이가 maxlen을 초과하면, 반대쪽 끝의 요소가 자동으로 제거된다.

d = deque([1, 2, 3, 4], maxlen=4)
d.append(5)  # 새로운 요소 5 추가
print(d)  # 출력: deque([2, 3, 4, 5], maxlen=4)

d.appendleft(6)  # 새로운 요소 6 추가
print(d)  # 출력: deque([6, 2, 3, 4], maxlen=4)

마지막으로 deque를 쓰면 장점 !

시간 복잡도가 낮아진다.

왜 deque가 시간 복잡도가 낮은가?

deque는 양 끝에서 아이템을 추가하거나 제거할 때 매우 빠르게 작동해. 이런 작업들이 데이터의 크기와 상관없이 항상 같은 시간이 걸리기 때문에, 이를 O(1) 작업이라고 해.

반면에, 리스트 같은 경우는 시작 부분에 아이템을 추가하거나 제거하려고 하면, 모든 아이템을 이동시켜야 하기 때문에 더 많은 시간이 필요해. 예를 들어, 첫 번째 위치에 새로운 아이템을 추가하려면, 기존의 모든 아이템을 한 칸씩 뒤로 밀어야 하니까 시간이 더 걸리는 거야. 이런 작업은 데이터의 양이 많아질수록 더 많은 시간이 걸리므로 O(1)이 아닌 O(n) 시간이 걸린다고 표현해.