[패스트캠퍼스][환급 챌린지]Chapter 2. 딥러닝을 위한 자료구조 02-07 덱

 

02-07 덱

덱은 스택과 큐의 장점만 버무려놓은 자료구조로, 스택과 큐 대신에 덱만 사용해도 괜찮을 정도라고 합니다. 이번 포스트에서는 덱의 특성을 알아보고 파이썬에서의 구현을 해보겠습니다.

덱의 특성

def) 덱 (deque, double-ended queue의 약자): 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료구조
덱의 특성이라 하면 스택과 큐의 기능을 모두 가지고 있다는 점입니다. 다만, 스택이나 큐와 달리 포인터 변수가 더 많이 필요하기 때문에, 메모리는 상대적으로 더 많이 필요로 합니다. 파이썬에서는 큐의 기능이 필요할 때 간단히 덱 라이브러리를 사용하곤 합니다(다만, 큐 라이브러리도 따로 구현되어 있기는 합니다). 이에 대해서는 아래에서 다시 알아보겠습니다.

덱 연산 예제

덱에 여러 개의 데이터를 삽입하고 삭제하는 예시를 확인해보겠습니다. 전체 연산은 아래와 같이 총 12단계로 구성되어 있습니다. 스택과 큐에서의 연산과 달리 삽입과 삭제를 할 때, 연산을 하는 포인터가 좌측인지 우측인지를 추가로 지정해주는 것을 알 수 있습니다.

좌측 삽입 4 - 좌측 삽입 3 - 좌측 삽입 2 - 좌측 삽입 1 - 우측 삽입 5 - 우측 삽입 6 - 우측 삽입 7 - 우측 삽입 8 - 우측 삭제 - 좌측 삭제 - 우측 삭제 - 좌측 삭제

좌측 및 우측 삽입 연산을 모두 마친 상태.

우측 삭제 (1).

좌측 삭제 (1).

우측 삭제 (2).

좌측 삭제 (2).

덱의 시간 복잡도

덱 자료구조에 데이터를 삽입하고 삭제할 때는 두 경우 모두 $O\left(1\right)$의 시간복잡도를 갖습니다.

	연산	시간 복잡도	설명
1	좌측 삽입(Append left)	$O\left(1\right)$	덱의 맨 왼쪽에 데이터 삽입
2	좌측 삭제(Pop left)	$O\left(1\right)$	덱의 맨 왼쪽에서 데이터 추출
3	우측 삽입(Append right)	$O\left(1\right)$	덱의 맨 오른쪽에 데이터 삽입
4	우측 삭제(Pop right)	$O\left(1\right)$	덱의 맨 오른쪽에서 데이터 추출

 

파이썬의 덱 라이브러리

파이썬에는 아예 덱(deque) 라이브러리가 존재합니다. 게다가 이 라이브러리 중 자주 사용되는 아래의 메서드들은 최악의 경우의 시간복잡도가 $O\left(1\right)$가 되도록 만들어져 있습니다.

• 우측 삽입: append()
• 좌측 삽입: appendleft()
• 우측 추출: pop()
• 좌측 추출: popleft()

연결 리스트로 덱 구현하기

라이브러리를 사용하기에 앞서 덱도 연결 리스트로 구현해보겠습니다. 삽입과 삭제에 있어서 $O\left(1\right)$를 보장할 수 있습니다. 여기서 포인트는 앞과 뒤라는 두 개의 포인터를 갖는 겁니다.

• def) 앞 (front): 가장 좌측에 있는 데이터를 가리키는 포인터
• def) 뒤 (rear): 가장 우측에 있는 데이터를 가리키는 포인터

스택과 큐의 특성을 버무려놓은 자료구조답게, 덱에서의 삽입과 삭제 구현 방법은 스택과 큐에서와 유사합니다. 앞과 뒤에 대하여 대칭적으로 구현할 수 있다는 점이 핵심입니다.

좌측 삽입 연산

좌측 삽입할 때는 앞(front) 위치에 데이터를 삽입합니다.

좌측 삭제 연산

반대로 좌측 삭제할 때는 앞(front) 위치에 데이터를 삭제합니다.

위 예시에서 좌측 연산에는 모두 앞(front) 포인터를 사용했습니다. 반대로 우측 연산을 할 때는 삽입과 삭제 모두 뒤(rear) 포인터를 이용하면 되겠습니다.

파이썬에서 덱을 사용하는 경우

큐(queue)에 대해 설명한 지난 포스트에서 설명했다시피, 파이썬의 리스트는 큐의 기능을 제공하지 않습니다. 이를 연결 리스트로 구현하는 방법도 있지만, 실무에서는 파이썬에서 제공하는 덱 라이브러리를 사용해 큐의 기능을 구현하는 것을 추천합니다. 삽입과 삭제 연산에 모두 시간복잡도 $O\left(1\right)$가 요구되기 때문입니다.

deque 라이브러리를 이용한 구현

deque 라이브러리는 collections라는 상위 라이브러리에 포함되어 있습니다. 라이브러리를 import할 때 참고해주세요.

from collections import deque

d = deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)

arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
print(d)

while d:
    print(d.popleft())
arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
print(d)

while True:
    print(d.pop())
    if not d:
        break

연결 리스트를 이용한 구현

class Node:
    def __init__(self, data):
        self.data = data
        self.prev = None
        self.next = None


class Deque:
    def __init__(self):
        self.front = None
        self.rear = None
        self.size = 0

    def appendleft(self, data):
        node = Node(data)
        if self.front == None:
            self.front = node
            self.rear = node
        else:
            node.next = self.front
            self.front.prev = node
            self.front = node
        self.size += 1

    def append(self, data):
        node = Node(data)
        if self.rear == None:
            self.front = node
            self.rear = node
        else:
            node.prev = self.rear
            self.rear.next = node
            self.rear = node
        self.size += 1

    def popleft(self):
        if self.size == 0:
            return None
        data = self.front.data
        self.front = self.front.next
        if self.front == None:
            self.rear = None
        else:
            self.front.prev = None
        self.size -= 1
        return data

    def pop(self):
        if self.size == 0:
            return None
        data = self.rear.data
        self.rear = self.rear.prev
        if self.rear == None:
            self.front = None
        else:
            self.rear.next = None
        self.size -= 1
        return data

    def front(self):
        if self.size == 0:
            return None
        return self.front.size

    def rear(self):
        if self.size == 0:
            return None
        return self.rear.size

    def show(self):
        cur = self.front
        while cur:
            print(cur.data, end= " ")
            cur = cur.next

라이브러리를 이용했을 때와 동일한 연산을 수행해보겠습니다. 단, 라이브러리 예제 코드에서의 print(d) 등의 부분은 클래스를 정의한 방식의 차이로 인해 Deque 클래스 내의 d.show() 등의 메서드로 대체되었습니다. 그걸 제외하면, 출력되는 결과는 라이브러리를 이용했을 때와 동일합니다.

d = Deque()
arr = [5, 6, 7, 8]
for x in arr:
    d.append(x)

arr = [4, 3, 2, 1]
for x in arr:
    d.appendleft(x)
d.show()

print()
while d.size != 0:
    print(d.popleft())

arr = [1, 2, 3, 4, 5, 6, 7, 8]
for x in arr:
    d.appendleft(x)
d.show()

print()
while True:
    print(d.pop())
    if d.size == 0:
        break

24일차 후기

포인터 몇 개 더해졌을 뿐인데 뭔가 어제보다 정리할 게 늘어난 느낌.... 기분 탓이겠죠??

http://bit.ly/3Y34pE0

패스트캠퍼스 [직장인 실무교육]

* 본 포스팅은 패스트캠퍼스 환급 챌린지 참여를 위해 작성되었습니다.