minzzl
덱을 써야하는 이유? 본문
안녕하세요!
오랜만에 글을 쓰네요 :)
이런 저런 핑계들로 미루어왔다가.. 다시 돌아왔습니다 ^^
거부해봐야 뭐하겠습니까 ~
해야죠 ...
본론으로 들어가보겠습니다.
저는 지난번 이어나가던 프로그래머스 스택/큐 부분의 문제를 풀고 있습니다.
덱이 좋다라는것을 익히 들어왔지만, 뭔가 그냥 리스트를 써서도 queue 나 stack 의 형태로 문제를 풀 수 있었기 때문에 귀찮아서 굳이 덱을 쓰지 않았었습니다.
그런데 ...
문제의 난의도가 올라가니, 시간 초과나 효율성 부분에서 큰 차이를 보이는 것을 몸소 느꼈습니다 ...^^
그래서 오늘은 덱에 대한 정리를 해보겠습니다!
dequeue
이름은 큐와 비슷해보입니다.
Dequeue 는 A Double-ended Queue 입니다.
Double-ended 는 양끝에 element 를 추가/삭제를 지원한다는 의미입니다.
덱은 내부적으로 Double-linked list 로 구현되어있습니다.
그래서 양끝의 요소의 추가/삭제가 O(1)을 만족하게됩니다.
| append() | deque의 right end에 요소 추가 |
| appendleft() | deque의 left end에 요소 추가 |
| pop() | deque의 right end의 요소 삭제 |
| popleft() | deque의 left end의 요소 삭제 |
위의 함수들을 통해서, deque를 통해서 stack과 queue를 모두 사용할 수 있습니다.
그런데 Python의 리스트를 통해서도 stack 과 queue를 모두 사용할 수 있는데요,
queue를 사용할 때는 deque를 사용하는 것이 좋습니다.
그 이유는 무엇일까요?
list를 이용한다면 list.append(), list.pop()을 통해 stack 자료구조를 사용할 수 있습니다.
또한 list.append(), list.pop(0)를 사용하여 리스트를 queue 자료구조로 사용할 수 있습니다.
그러나 단순 pop()의 경우 time complexity는 O(1)이지만, pop(0)의 time complexity는 O(N)이기 때문에 시간이 오래걸립니다.
이는 Python의 list가 fixed size memory blocks(array)로 구현되어 있기 때문입니다. 즉 고정된 사이즈의 메모리를 갖습니다.
자료구조 뒤에서 추가/삭제는 O(1)이지만, 맨 첫번째 요소를 추가/삭제한다면 O(N)이 걸리는 것입니다.
앞서 deque의 경우 내부적으로 double-linked list로 구현되어 있기에 양끝의 요소 추가/삭제는 O(1)을 만족합니다.
따라서 시간 복잡도를 고려해 queue 자료구조를 사용할 때는 list를 사용하지 않는 것이 좋습니다.
이처럼 queue 자료구조를 사용할 때는 deque 를 사용하는 것이 효율적입니다.
그러나 어떤 상황이냐에 따라 적절히 사용하는 것이 중요합니다.
아래는 덱과 리스트의 시간 복잡도를 비교한 테이블입니다.
| Deque | List |
 |
 |
위의 표를 보면 알 수 있듯이, 고정된 길이 내에서 접근, 슬라이싱을 하는데에는 list가 유리합니다.
그러나 데이터를 추가/삭제할 때는 deque가 유리합니다.
* 다음의 글을 참고하여 작성하였습니다.
https://wellsw.tistory.com/122
https://yongjoonseo.dev/computer%20science/algorithm%20concepts/swea-intermediate21/
