_8_ 자료구조 — 덱
Published in
3 min readMay 9, 2022
덱 자료구조와 연산, 시간복잡도
덱(Deque)
덱은 어려운 자료구조가 아니고 여러가지 연산을 지원합니다.
사실 덱은 동적 배열+스택+큐 입니다(?).
세 가지 자료구조가 지원하는 모든 연산을 다 지원해버리는 사기적인 자료구조입니다.
게다가 시간복잡도도 각 자료구조들이 지원하는 시간복잡도와 동일합니다.
front에서 넣고 빼는 것도 O(1) back에서 넣고 빼는 것도 O(1) 심지어 인덱스를 이용한 Random Access까지 O(1)에 가능합니다.
아니 그럼 대체 왜 덱만 안쓰고 배열+스택+큐를 쓰는걸까요?
그건 내부적인 구현이 약간 복잡하기 때문에 연산들에 상수가 붙기 때문입니다.
고인물들은 이걸 덱 상수라고 따로 표현하기도 합니다.
덱의 활용
사실상 덱도 현재로썬 더 볼 필요가 없는 자료구조입니다. 지원하는 연산과 시간복잡도만 숙지해두면 됩니다.
왜냐하면 덱을 전문적으로 활용하는 문제들은 대체로 복잡하고 이런 것들이 코딩테스트에 나온다는 이야기는 듣도 보도 못했습니다. 예를 들어 다음과 같은 것들이 있습니다. 당장 알 필요가 없는 것들입니다.
- 0–1 BFS — BFS가 이루어질 때 간선의 가중치가 항상 0 혹은 1이라면 최단 거리가 계산되는 방식이 정해져있기 때문에 BFS의 시간복잡도를 최적화 할 수 있는 테크닉입니다. 하지만 일반적인 BFS를 써서도 거의 다 풀리고 저도 이걸 실제로 활용해본 적은 없습니다.
- 덱을 활용한 다이나믹 프로그래밍 — 동적 계획법(DP)의 최적화 기법 중 하나입니다. 보통 Monotone Stack 테크닉처럼 Monotone Deque을 활용하여 점화식을 수행합니다.
하지만 양방향으로 뭔가 데이터를 넣고 빼고 하는 자료구조가 필요한 문제들에서 덱을 활용하는 것은 옳습니다.
