[TIL][240805] 알고리즘 나머지 공부 Circular Queue, deque

어떤 문제가 있었나?

지난주 스쿼드 3 알고리즘을 따라가기가 생각보다 벅차다 보니, 주요 내용인 그래프와 BFS, DFS에 집중하여 학습했다. 그래서인지 BFS 관련 문제를 풀 때, 지난주 스쿼드에서 살짝 언급된 deque를 사용하지 못해 찜찜함을 남기곤 했다. 풀이에 지장이 가진 않았지만 다양한 방법으로 풀기 위해서는 꼭 정리를 하고 가야겠다는 생각이 들었다.

---

무엇을 시도했나?

먼저 튜터님이 지난 스쿼드 세션에서 살짝 언급하신 원형 큐(Circular Queue)와 데크(deque) 필기를 보면서 정리하고, 추가 교재로 관련 부분을 복습했다. 마무리고 BFS 관련 문제를 풀어 내가 얼마큼 이해했는지 확인해 봤다.

---

어떻게 해결됐는가?

백준 2606번: 바이러스 문제를 BFS를 이용하여 풀어봤다. DFS로만 문제를 풀다가 BFS로 풀려고 하니 알고리즘 구현에 살짝 애먹었지만 쉬운 문제라 나름대로 잘 풀었다. deque를 사용해 보니 

 

import sys
from collections import deque

sys.stdin = open('input2.txt', 'r')

# 입력
vertax = int(input())
edge = int(input())
graph = {}
for i in range(1, vertax + 1):
    graph[i] = []
for _ in range(edge):
    start_v, end_v = map(int, input().split())
    graph[start_v].append(end_v)
    graph[end_v].append(start_v)

def bfs(graph, start_v):
    visited = []
    queue = deque([start_v])
    while queue:
        curr_v = queue.popleft()
        if curr_v not in visited:
            visited.append(curr_v)
            for v in graph[curr_v]:
                queue.append(v)
    return visited

visited = bfs(graph, 1)
print(visited)
print(len(visited)-1)

---

새로 알게 된 점은 무엇인가?

원형 큐 Circular Queue

환형 큐라고도 불리는 Circular Queue는 FIFO 구조를 지니는 점에서 큐와 동일하지만, 마지막과 시작이 연결되어 있는 원형 구조를 띄고 있어 Ring Buffer라고도 부른다.

 

why?

• 기존 큐는 공간이 꽉 차게 되면 더 이상 요소를 추가할 수 없다.
• deQueue()로 앞 요소를 제거하여 충분한 공간이 남아도 추가할 수 없다.
• 앞 공간이 남아있다면 시작과 끝을 연결하여 동그랗게 만들어 앞쪽을 추가할 수 있다.

https://www.geeksforgeeks.org/introduction-to-circular-queue/

• 마지막 위치와 시작 위치를 연결하는 원형 구조에 투 포인터 Front, Rear가 움직인다.
• enQueue()를 하면 Rear가 앞으로 이동, deQueue()를 하면 Front가 앞으로 이동한다.
• 원형으로 이어져 있기 때문에 enQueue()와 deQueue를 반복하면 돌면서 이동하는 구조가 된다.
• Front와 Rear가 만났다면, 여유공간이 없으므로 공간 부족 에러가 발생한다.

구현

초기화할 때 큐의 크기 k를 입력값으로 받고, 최대 길이 maxlen으로 정해준다. 그리고 Front, Rear 둘 다 초기값은 0으로 설정한다.

def __init__(self, k: int):
    self.q = [None] * k
    self.maxlen = k
    self.front = 0
    self.rear = 0

rear 포인터 위치가 None이라면 rear 포인터 위치에 값을 넣고, 포인터를 한 칸 앞으로 이동한다. 이때 전체 길이만큼 나눠 전체 길이를 넘지 않도록 한다. rear 포인터 위치가 None이라면 공간이 가득 찼으므로 False를 리턴한다. 

def enQueue(self, value: int) -> bool:
    if self.q[self.rear] is None:
        self.q[self.rear] = value
        self.rear = (self.rear + 1) % self.maxlen
        return True
    else:
        return False

반대로 front 포인터 위치가 None이라면 False를 리턴하고, None이 아니라면 front 포인터 위치에 None을 넣어 삭제한 후 포인터를 한 칸 이동한다. 마찬가지로 전체 길이를 넘지 않도록 전체 길이를 나눠준다.

def deQueue(self) -> bool:
    if self.q[self.front] is None:
        return False
    else:
        self.q[self.front] = None
        self.front = (self.front + 1) % self.maxlen
        return True

원형 큐(Circular Queue)의 전체 구현 코드는 아래와 같다.

class CircularQueue:
    def __init__(self, k: int):
        self.q = [None] * k
        self.maxlen = k
        self.front = 0
        self.rear = 0

    def enQueue(self, value: int) -> bool:
        if self.q[self.rear] is None:
            self.q[self.rear] = value
            self.rear = (self.rear + 1) % self.maxlen
            return True
        else:
            return False

    def deQueue(self) -> bool:
        if self.q[self.front] is None:
            return False
        else:
            self.q[self.front] = None
            self.front = (self.front + 1) % self.maxlen
            return True

    def Front(self) -> int:
        return -1 if self.q[self.front] is None else self.q[self.front]

    def Rear(self) -> int:
        return -1 if self.q[self.rear - 1] is None else self.q[self.rear - 1]

    def isEmpty(self) -> bool:
        return self.front == self.rear and self.q[self.front] is None

    def isFull(self) -> bool:
        return self.front == self.rear and self.q[self.front] is not None

한 줄 요약: enQueue는 rear 포인터를 이동하고, deQueue는 front 포인터를 이동한다.

 

Deque: Double-Ended Queue

사실 Front()는 큐의 연산이 맞지만, Rear()는 큐에서 정의되지 않는 연산이다. 엄밀히 따지면 Rear()는 데크(deque)에 존재하는 연산이다. 데크는 양쪽 끝을 모두 추출할 수 있는 추상 자료형이며, 큐의 일반화한 형태라 볼 수 있다. 파이썬은 데크를 collections 모듈에서 deque라는 이름으로 제공한다.

데크는 큐와 스택의 성질을 다 가지고 있어서 유용해 보이지만, deque에서 제공하는 대부분의 메서드는 리스트로 다 구현이 가능하다. 아래에 deque의 메서드들이다. 밑줄 친 메서드는 list에서도 사용 가능하다. 결국 deque는 데이터를 왼쪽에서 넣을 수 있는 메서드 appendleft, extendleft, popleft와 rotate(n=1), maxlen 메서드 정도가 리스트와의 차이점이라 할 수 있겠다. 그나마 appendleft(x)는 리스트의 insert(0, x)와 같고, popleft는 pop(0)와 같다.

• append(x): 데크 오른쪽에 x를 추가한다.
• appendleft(x): 데크 왼쪽에 x를 추가한다.
• clear(): 데크에서 모든 요소를 제거하고 길이가 0인 상태를 만든다.
• copy(): 데크의 얕은 복사본을 만든다.
• count(x): x와 같은 데크 요소의 수를 센다.
• extend(iterable): iterable 인자에서 온 요소를 추가하여 데크의 오른쪽에 확장한다.
• extendleft(iterable): iterable에서 온 요소를 추가하여 데크의 왼쪽을 확장한다. 일련의 왼쪽 추가는 iterable 인자에 있는 요소의 순서를 뒤집는 결과를 준다.
• index(x,[, start[, stop]]): 데크에 있는 x의 위치를 반환한다.
• insert(i, x): x 데크의 i위치에 삽입한다.
• pop(): 데크의 오른쪽에서 요소를 제거하고 반환한다. 
• popleft(): 데크의 왼쪽에서 요소를 제거하고 반환한다.
• remove(value): value의 첫 번째 항목을 제거한다.
• reverse(): 데크의 요소들을 제자리에서 순서를 뒤집고 None을 반환한다.
• rotate(n=1): 데크를 n단계 오른쪽으로 회전한다. n<0 이면 왼쪽으로 회전한다.
• maxlen: 데크의 최대 크기 또는 제한이 없으면 None

그럼에도 불구하고 deque를 쓰는 이유는 O(1) 복잡도의 삽입과 삭제에 있다. 리스트에서 삽입, 삭제 시 모든 원소를 이동시키기 때문에 시간 복잡도가 O(N)이 되고, deque에서 삽입 삭제 시 위 그림과 같이 양끝 원소를 삭제만 하기 때문에 O(1)의 시간 복잡도를 갖게 된다.

---

무엇을 느꼈고 내일은 무엇을 할까?

중요하다고 생각한 것만 공부하고, 간단히 공부만 하려고 했던 부분에 생각보다 많은 내용이 담겨 있어서 놀랐다. 또한 이론을 하고 문제에 적용시켜 가는 게 어렵더라도 이해도를 올리기 괜찮은 방법이라고 다시 한번 생각이 들었다. 내일은 CS 기술 면접 대비 CS 복습을 할 계획이다.