[Python] 파이썬 자료구조의 꽃 deque에 대해 알아보자!

최근 알고리즘 테스트 공부를 위해서 파이썬을 꽤나 자주 이용하는데, 문제에서 빈번하게 사용되는 deque에 대해서 알아봅시다!

 

Deque, 왜 쓰나요?

먼저 주 언어가 Javascript였던 제가, 파이썬으로 알고리즘을 하게 된 가장 큰 이유가 바로 deque의 유무였습니다. 자바스크립트에서 후입선출 방식의 Queue나 양쪽에서 삽입 삭제가 가능한 Double-ended Queue 같은 자료구조를 구현하기 위해선, 링크드리스트를 거의 필수로 사용해야 했습니다. 

예를 들어 1, 2, 3이 있는 배열을 큐 방식으로 넣고 뺀다고 생각해 봅시다.

1, 2, 3에서 가장 먼저 들어왔던 1의 값만 뺀다고 생각 해봅시다. 그럼 1을 빼기 위해서, 뒤에 있는 모든 index들이 한 칸 앞으로 와야 하는 귀찮은 일이 발생합니다. 어차피 빠른 컴퓨터가 할 건데, 무슨 상관이냐?라고 생각 할 수 있지만, 우리는 코드를 효율적으로 짜야할 의무(?)가 있기 때문에, O(N)의 연산을 잡아먹지 않고, O(1)의 연산만에 1을 뽑아 버릴 수 있는 링크드리스트를 사용하는 것입니다. 

설명을 위해 단순 연결 리스트로 표현

링크드리스트는 자료를 저장 할 때, 그다음 자료의 위치 데이터를 포함하고 있는데, 이때 모든 index를 한 칸씩 옮기는 것이 아닌, 시작 주소를 1에서 2로 변경만 하면, 1의 값 자체는 무시하고 첫 데이터를 2로 할 수 있기 때문에 링크드리스트로 구현하는 것입니다. 물론 JS 및 다른 언어에서도 링크드리스트를 구현하여 사용할 수 있지만, 링크드리스트는 구현하기 복잡하고, 코드도 길어지기 때문에 파이썬 라이브러리에 구현되어 있는 deque을 사용하는 것입니다. 

 

List랑 무엇이 다른가요?

list는 앞서 설명 드렸던 일반적인 배열 구조와 같습니다. list에서 맨 앞의 값을 뺄 때 pop(0) 같은 메서드를 이용합니다. 해당 메서드는 O(N) 연산을 수행하게 됩니다. 반면, deque는 O(1) 연산을 수행합니다. 그리고 더 많은 메서드들을 제공합니다. Deque의 메서드들을 살펴봅시다.

메서드	설명	List에서 메서드 유무
append(item)	오른쪽 끝에 item을 삽입합니다	O
appendleft(item)	왼쪽 끝에 item을 삽입합니다	X
pop()	가장 오른쪽 item을 삭제하고 반환합니다	O
popleft()	가장 왼쪽 item을 삭제하고 반환합니다	X
extend(item)	원래 있던 list의 오른쪽에 item 넣어 확장시킵니다	O
extendleft(item)	원래 있던 list의 왼쪽에 item 넣어 확장시킵니다	X
insert(index, item)	list의 index 위치에 item을 삽입합니다	O
remove(item)	list 안에 item 항목을 삭제합니다(1개)	O
rotate(number)	number 만큼 list를 회전합니다	X
reverse()	list를 반대로 뒤집습니다	O
clear()	list를 전체를 비웁니다	O

 

Deque의 중요 기능 살펴보기

먼저 파이썬에서 collections.deque 모듈을 불러와야합니다. 

from collections import deque

 

1. append, appendleft 메서드

q = deque([1,2,3,4,5])
q.append(6)
# 1, 2, 3, 4, 5, 6

q = deque([1,2,3,4,5,6])
q.appendleft(0)
# 0, 1, 2, 3, 4, 5, 6

list와 매우 유사하지만 왼쪽에서 삽입 할 수 있는 appendleft도 존재합니다. 

 

2. pop, popleft 메서드

q = deque([1,2,3,4,5])
data = q.pop() # 5
# q = [1, 2, 3, 4]

q = deque([1,2,3,4,5])
data = q.popleft() # 1
# q = [2, 3, 4, 5]

list와 매우 유사하지만 왼쪽에서 요소를 제거할 수 있는 popleft도 존재합니다.

 

3. rotate 메서드

q = deque([1,2,3,4,5])
q.rotate(1)
# 5, 1, 2, 3, 4

q = deque([1,2,3,4,5])
q.rotate(-1)
# 2, 3, 4, 5, 1

숫자만큼 배열을 회전시킨다. 양수인 경우 시계방향으로 회전, 음수인 경우 반시계방향으로 회전합니다.

 

4. 최대 크기 지정하기

q = deque([1,2,3,4,5], maxlen=5)
q.append(6)
# 2, 3, 4, 5, 6

q = deque([1,2,3,4,5], maxlen=5)
q.appendleft(0)
# 0, 1, 2, 3, 4

maxlen을 통해 최대 크기를 정할 수 있는데, 최대 크기 이상으로 값이 들어오게 되면 가장 반대에 있는 값을 자동으로 삭제시킵니다. 

 

간단하게 파이썬으로 알고리즘을 해결 하는 이유 중 하나인 deque에 대해 알아보았습니다. 감사합니다.