[자료구조/알고리즘] - Queue/Deque

큐는 FIFO, First-In-First-Out 선입선출로 처리됩니다. 지난번에 스택을 정리할 때 테니스공, 셔틀콕을 넣는 통에 스택을 비유 했었는데, 큐의 경우에는 다른 예시 보다 책 예시가 좋은 거 같아서 적어본다. 우리가 흔히 식당에 들어가기 위해서 대기줄을 서는 경우가 있는데 그 때 제일 먼저 대기줄에 선 손님분들 부터 입장을 하게 된다. 이런 식으로 작동을 하는게 큐라고 보면 된다.

스택의 거의 모든 연산을 파이썬에서 지원해 주듯이 리스트는 큐의 모든 연산을 지원해줍니다. 주의할 점은 리스트는 동적 배열로 구현되어져 있어서 큐의 연산을 수행하기에는 효율적이지 않아, Deque라는 별도의 자료형을 사용해야 좋은 성능을 낼 수 있다. 어제오늘 큐 문제를 최대한 많이 풀려고 했는데 파이썬으로 푼 문제들의 대부분을... 큐에서 Deque로 바꿔야 시간 초과가 안나는 경우가 정말 많았었다. 

백준 문제를 푼다거나 코테를 보는 경우 처럼 제한 시간이 걸려있지 않다면, 성능을 고려 안해도 되서 그냥 큐를 써도 될거 같지만, 그런 상황에 있다면 queue를 사용하는 것 때문에 시간 초과가 나는 경우가 많을 것 같다. 

queue 시간초과만 검색해도 나오는 질문

리스트를 통해서 queue를 문제 풀이에 적용시키게 되면, pop()과 같은 파이썬이 제공해주는 연산을 사용하게 되는데 이게 실제로 사용을 하게 되면 상황에 따라서 O(1) 이상의 시간복잡도로 적용해서 사용하는 경우가 많아서 시간 초과나 런타임에러 같은 에러가 많이 일어나는 것 같다. 

스택, 큐, 데크(deque)를 비교하는 좋은 예시

그래서 그런 문제를 피하기 위해서 Deque를 사용하는 것이 좋은 것 같다. Deque는 양쪽에서 삭제와 삽입을 모두 처리할 수 있고, 스택과 큐의 특징을 모두 가지고 있다. 구현을 연결 리스트로 하게 되면 이중 연결 리스트로 해주는 것이 제일 적절하다고 한다. 

파이썬에서 Deque를 사용하기 위해서는 다음과 같이 "collections"에서 불러와서 사용해주면 된다.

from collecitons import deque

d = deque()

위와 같이 선언을 해주는 식으로 사용을 해주면 되고, 백준을 풀 때 사용했던 방식은 다음과 같다. 

from collecitons import deque

d = deque([i for i in range(2,10)])

이렇게 사용을 해주면 2에서 부터 10까지의 수가 들어가 있는 list [ ]를 Deque로 만들어주게 된다. 

출력을 할 때 조금 신경을 써줘야 되는데 그냥 출력을 하게 되면 "deque([ ~ ~ ~ ])" 이런 식으로 출력이 되서 list(), 리스트로 만들어주는 것이 좋다. 

문제를 풀면서도 여러 이슈가 많았는데 그 부분에 대해서도 주말 중에 정리해서 올리는 걸로!

[참고자료]

참고 서적 : 파이썬 알고리즘 인터뷰

파이썬 알고리즘 인터뷰