[Python] 자료구조 : 덱(deque()) 개념 및 사용

파이썬 코딩 테스트에서 자주 사용되는 데큐(deque)에 대해 알아보자.

 

---

◽ deque()

• Stack이나 queue처럼 한 방향에서 삽입과 삭제가 일어나는게 아니라 양방향에서 삽입과 삭제가 일어나는 자료구조이다.
• 리스트의 양쪽 끝에서 삽입과 삭제를 모두 허용하는 자료의 구조. 이것은 스택과 큐의 자료 구조를 복합한 형태이다.
• 파이썬에서 list를 사용하는 것과 유사하지만 deque를 사용하는 이유는 시간복잡도 때문이다.

 

• 리스트에서 0번 인덱스를 삭제한다고 생각해보자. 이때 리스트 내부에서는 0번 인덱스를 제거하고 끝이 아니라 뒤에있는 원소들을 앞으로 하나씩 당겨주는 연산을 더 수행하게된다. 따라서 list의 삭제연산은 O(n)이 걸리는데 반면 deque의 삭제연산은 O(1)이다. 따라서 push, pop이 빈번한 알고리즘의 경우 list보다 deque를 사용하는 것이 효율적이다.

---

 

 

from collections import deque

데큐는 위와 같이 불러올 수 있다.

---

deque를 사용하면 얻는 장점

• 엄격한 리스트를 만들 수 있다.
• 속도가 리스트에 비해 굉장히 빠르다. List = O(n), deque = O(1)
• 당연하지만 큐작업이 훨씬 편해진다.

---

1. 큐(QUEUE)에 대한 이해.

큐는 기본적으로 선입 선출 (FIFO : First In First Out)구조이다.

 

예시로는 다음이 있다.

• 프린터기 : 프린터기는 먼저 인쇄를 누른 것부터 차례대로 작동한다.
• 은행 대기표 : 은행에서는 먼저 대기표를 뽑은 사람부터 차례대로 서비스를 진행한다.

 

deque 함수는 큐에 제한되어 있는 선입선출 제한을 풀어서, 더 여러곳에 사용할 수 있도록 한 함수이다.

---

2. deque 사용하기

from collections import deque
data = [1, 2, 3, 4, 5]
d = deque(data)
print(d)

#출력
deque([1, 2, 3, 4, 5])

 

데큐의 함수 목록은 다음과 같다.

 

함수 목록:

• append
• appendleft
• clear
• copy
• count
• extend
• extendleft
• index
• insert
• maxlen
• pop
• popleft
• remove
• reverse
• rotate

 

여기서 눈여겨 볼 함수는 다음과 같다.

• appendleft : 왼쪽에 개체를 추가
• extendleft : 왼쪽에 리스트를 연장
• maxlen : 큐의 길이를 반환
• popleft : 큐의 맨 왼쪽에 있는 개체를 반환
• rotate : 큐를 회전

여기서 로테이트는 처음 접하면 생소할 것이다. 

 

그래서 간단한 예시 2개를 들어보자.

#1

 

d = deque([1, 2, 3, 4, 5])
print(d)
d.rotate(2)
print(d)
d.rotate(-2)
print(d)

#출력
deque([1, 2, 3, 4, 5])
deque([4, 5, 1, 2, 3])
deque([1, 2, 3, 4, 5])

큐 [1 ,2 ,3 ,4 ,5]가 오른쪽에서 왼쪽 방향으로 2 회전하여 [4, 5, 1, 2, 3]이 되었다.

이번에는 반대로 -2로 회전하여  [1 ,2 ,3 ,4 ,5]가 되었다.

 

#2

 from collections import deque
 test = [1, 2, 3, 4, 5, 6, 7, 8, 9]
 test = deque(test)
 test.rotate(2) 
 result = list(test)
 result
[8, 9, 1, 2, 3, 4, 5, 6, 7]

 

 

 

파이썬 알고리즘을 풀다보면 리스트를 회전하는 문제에 많이 직면하게 된다.

이는 python collection 모듈의 deque 자료형을 사용하면된다.

함수안에 음수 를 넣게 된다면 왼쪽회전 양수는 오른쪽회전이다.