덱Deque

4. 덱Deque#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

  • 선형 자료구조

  • 덱 자료구조

  • 덱 활용

4.1. 선형 자료구조#

선형 자료구조linear data structure는 여러 개의 항목을 순서에 맞춰 추가하고 삭제할 수 있는 자료구조를 가리킨다. 항목의 추가/삭제 방식에 따라 서로 다르게 작동하며 일반적으로 다음 선형 자료구조가 활용된다.

  • 리스트list

  • 덱deque

  • 큐queue

  • 스택stack

  • 연결 리스트linked list

  • 정렬 리스트sorted list

선형 자료구조의 양 끝인 머리와 꼬리를 부르는 이름이 자료구조마다 다를 수 있다.

양 끝

별칭

머리

헤드(head), 위(top), 앞(front)

꼬리

테일(tail), 아래(bottom), 뒤(rear)

프로그래밍 언어에 따라 언급된 선형 자료구조의 일부가 지원된다. 파이썬은 큐, 스택, 덱 자료구조를 제공한다.

  • 덱: collections 모듈의 deque 클래스

  • 큐와 스택: queue 모듈의 Queue 클래스와 LifoQueue 클래스

여기서는 덱, 큐, 스택을 추상 자료형으로 선언한 뒤에 직접 파이썬 클래스로 구현해본다.

4.2. 덱 추상 자료형#

덱deque은 double-ended queue의 줄임말이며, 항목의 빠른 추가와 삭제를 지원하는 선형 모음 자료형이다. 덱은 리스트와 유사한 자료구조이지만 다음 측면에서 차이점이 존재한다.

  • 항목 추가와 삭제가 기본적으로 머리head와 꼬리tail에서만 이루어진다.

  • 항목의 추가와 삭제가 리스트의 append(), pop() 메서드보다 빠르다.

4.2.1. Deque 추상 클래스#

덱 추상 클래스에 기본으로 포함되어야 하는 메서드는 다음과 같다.

정의

기능

Deque

덱 추상 클래스

append()

머리에 새로운 항목 추가. 반환값 없음.

appendleft()

꼬리에 새로운 항목 추가. 반환값 없음.

pop()

머리 항목 삭제. 삭제된 항목 반환

popleft()

꼬리 항목 삭제. 삭제된 항목 반환.

아래 코드의 Deque 클래스는 덱 추상 자료형을 구현한 추상 클래스다.

  • _items 인스턴스 변수: 덱에 포함되는 항목들을 리스트로 저장.

  • append(), pop() 인스턴스 메서드: 리스트의 append(), pop() 메서드 그대로 활용.

  • appendleft(), popleft() 인스턴스 메서드: 추상 메서드 상태로 둠.

class Deque:
    """리스트를 활용한 덱 구현"""

    def __init__(self, items=[]):
        self._items = items

    def __len__(self):
        return len(self._items)
        
    def append(self, item):
        """머리에 항목 추가"""
        self._items.append(item)

    def appendleft(self, item):
        """꼬리에 항목 추가"""
        raise NotImplementedError

    def pop(self):
        """머리 항목 삭제"""
        return self._items.pop()

    def popleft(self):
        """꼬리 항목 삭제"""
        raise NotImplementedError

4.2.2. 추상 클래스 vs 구상 클래스#

추상 클래스 또한 인스터를 생성하는 데에 활용할 수 있다. 하지만 아직 정의되지 않은 메서드를 실행하면 NotImplementedError가 발생한다.

deque_adt = Deque()

deque_adt.appendleft("덱 항목")

---------------------------------------------------------------------------
NotImplementedError                       Traceback (most recent call last)
Cell In[2], line 3
      1 deque_adt = Deque()
----> 3 deque_adt.appendleft("덱 항목")

Cell In[1], line 16, in Deque.appendleft(self, item)
     14 def appendleft(self, item):
     15     """꼬리에 항목 추가"""
---> 16     raise NotImplementedError

NotImplementedError:

이렇듯 추상 자료형을 구체화시킨 객체를 추상 클래스의 인스턴스로 정의해서는 제대로 활용할 수 없다. 이유는 추상 클래스에 포함된 추상 메서드가 제대로 구현되지 않았기 때문이다. 따라서 포함된 모든 추상 메서드가 제대로 구현된 구상 클래스를 먼저 구현해야 한다. 구상 클래스concrete class는 포함된 모든 메서드의 본문이 제대로 구현된 클래스를 가리킨다.

4.3. 덱 자료구조 구현#

리스트를 선형 자료구조로 활용할 때 가장 중요한 요소는 머리와 꼬리의 지정이다. 앞서 Deque 추상 클래스를 정의할 때 리스트를 이용하여 항목들을 저장하는 방식을 선택하였으며, 덱의 머리에서 항목의 추가와 삭제를 실행하기 위해 리스트의 append()와 pop() 메서드를 이용하였다. 즉, 덱의 머리는 리스트 마지막 인덱스가 가리키는 위치를, 즉 보통 리스트의 오른편 끝으로 그려지는 곳으로 지정하였다.

반면에 덱의 꼬리에서의 항목 추가와 삭제는 구현하지 않은채로 두었기에 덱 자료구조를 클래스로 선언하려면 appendleft()와 popleft() 메서드가 리스트의 꼬리로 지정된 위치에서 항목의 추가와 삭제를 처리하는 방식을 구현하면서 Deque를 상속해야 한다.

아래 정의에서 꼬리는 리스트의 0번 인덱스에 해당하는 위치를 가리킨다. 따라서 덱의 머리에서의 항목의 추가와 삭제는 각각 insert()와 pop() 함수를 적절한 인자와 함께 호출되는 방식으로 처리된다.

class myDeque(Deque):
    """리스트를 활용한 덱 구현"""

    def __init__(self, items=[]):
        """새로운 덱 생성"""
        super().__init__(items)

    def __repr__(self):
        """덱 표기법: dqque([1, 2, 3]) 등"""
        return f"deque({self._items})"
    
    def appendleft(self, item):
        """꼬리에 항목 추가"""
        self._items.insert(0, item)

    def popleft(self):
        """꼬리 항목 삭제"""
        return self._items.pop(0)

아래 코드는 비어 있는 덱을 선언한 후에 4, 'dog', 'cat', True, 8.4 등을 머리와 꼬리에 추가하거나 삭제하는 과정을 묘사한다.

d=myDeque([])
d.append(4)
d.appendleft('dog')
d.append('cat')
d.append(True)
print(d)
d.appendleft(8.4)
print(d.popleft())
print(d.pop())
print(d)

deque(['dog', 4, 'cat', True])
8.4
True
deque(['dog', 4, 'cat'])

4.4. collections.deque 클래스#

파이썬 collections 모듈이 덱 추상 자료형을 자료구조로 구현한 deque 클래스를 지원한다. 그런데 앞서 직접 정의된 myDeque 보다 항목의 추가와 삭제가 빠르다. 특히 appendleft()는 20 배 정도, popleft()는 2천배 이상 deque 클래스의 메서드가 빠르게 작동한다.

from collections import deque

  • append() 메서드 속도 비교

%%time

n = 100_000
dec1 = myDeque([])

for k in range(n):
    dec1.append(k)

CPU times: user 4.08 ms, sys: 190 μs, total: 4.27 ms
Wall time: 4.27 ms

%%time

n = 100_000
dec1 = deque([])

for k in range(n):
    dec1.append(k)

CPU times: user 3.24 ms, sys: 151 μs, total: 3.4 ms
Wall time: 3.4 ms

  • appendleft() 메서드 속도 비교

%%time

n = 100_000
dec1 = myDeque([])

for k in range(n):
    dec1.appendleft(k)

CPU times: user 552 ms, sys: 0 ns, total: 552 ms
Wall time: 551 ms

%%time

n = 100_000
dec1 = deque([])

for k in range(n):
    dec1.appendleft(k)

CPU times: user 2.93 ms, sys: 0 ns, total: 2.93 ms
Wall time: 2.93 ms

  • pop() 메서드 속도 비교

%%time

n = 100_000
dec1 = myDeque(list(range(n)))

for _ in range(n):
    dec1.pop()

CPU times: user 5.21 ms, sys: 0 ns, total: 5.21 ms
Wall time: 5.18 ms

%%time

n = 100_000
dec1 = deque(list(range(n)))

for _ in range(n):
    dec1.pop()

CPU times: user 3.12 ms, sys: 0 ns, total: 3.12 ms
Wall time: 3.12 ms

  • popleft() 메서드 속도 비교

%%time

n = 100_000
dec1 = myDeque(list(range(n)))

for _ in range(n):
    dec1.popleft()

CPU times: user 7.7 s, sys: 0 ns, total: 7.7 s
Wall time: 7.7 s

%%time

n = 100_000
dec1 = deque(list(range(n)))

for _ in range(n):
    dec1.popleft()

CPU times: user 3.44 ms, sys: 0 ns, total: 3.44 ms
Wall time: 3.44 ms

myDeque 클래스가 지원하는 appendleft()와 popleft()는 리스트의 0번 인덱스에서 항목을 추가하거나 삭제한다. 그런데 이를 위해 사용되는 리스트의 insert(0, item)와 pop(0)은 실행시간이 리스트의 길이에 의존한다. 따라서 myDeque 객체의 꼬리에서 항목을 추가하고 삭제하는 시간은 항목의 개수가 많아질 수록 점점 더 오래 걸리게 된다.

반면에 collections.deque 클래스는 항목을 저장할 때 리스트가 아닌 다른 방식으로 항목을 저장하며, 머리와 꼬리에서 항목을 저장하고 삭제하는 일이 리스트의 길이에 무관하게 일정한 시간이 걸린다. 즉, 덱에 포함된 항목의 개수에 상관없이 일정한 시간이 걸린다.

그렇다고 해서 collections.deque의 메서드가 항상 리스트의 메서드보다 빠른 것은 아니기에 필요에 따라 리스트 또는 collections.deque 중에 하나의 자료구조를 선택할 필요가 있다.

4.5. 덱 활용: 회문palindrome 판별기#

앞으로 읽어도, 뒤로 읽어도 동일한 단어 또는 문장을 회문palindrome이라 부른다. 한글과 영어의 회문 예제는 다음과 같다. 단, 쉼표, 느낌표, 물음표, 공백, 대소문자 여부 등은 무시한다.

  • 한글 회문 예제: ‘기러기’, ‘우영우’, ‘토마토’, “인싸 의사의 싸인”, “여보게, 저기 저게 보여?” 등등

  • 영어 회문 예제: ‘mom’, ‘radar’, ‘Yo! Banana boy.’, ‘I did, did I?’, ‘No lemon, no melon’ 등등

아래 pal_checker() 함수는 인자로 입력된 문자열의 문자열의 회문 여부를 myDeque 클래스의 인스턴스를 이용하여 판별한다.

def pal_checker(text):
    # 덱 객체 생성
    char_deque = myDeque([])
    for ch in text:
        char_deque.appendleft(ch)

    # 머리와 꼬리 항목 비교
    while len(char_deque) > 1:
        first = char_deque.pop()
        last = char_deque.popleft()
        # 대칭 문자가 다를 경우 회문 아님 판정
        if first != last:
            return False

    # 이전 반복문을 무사히 통과하면 회문 판정
    return True

공백이나 특수 기호가 없는 단어의 경우에 회문 판별이 잘 작동한다.

assert pal_checker("기러기") == True
assert pal_checker("사이다") == False
assert pal_checker("radar") == True
assert pal_checker("tomato") == False

반면에 아래 주장 어느 것도 참으로 인정받지 못한다. 이유는 대소문자가 구분되거나 쉼표, 물음표, 느낌표 등의 기호가 무시되지 않기 때문이다.

assert pal_checker("Bob") == True
assert pal_checker("인싸 의사의 싸인") == True
assert pal_checker("여보게, 저기 저게 보여?") == True
assert pal_checker('I did, did I?') == True
assert pal_checker('No lemon, no melon') == True

---------------------------------------------------------------------------
AssertionError                            Traceback (most recent call last)
Cell In[7], line 1
----> 1 assert pal_checker("Bob") == True
      2 assert pal_checker("인싸 의사의 싸인") == True
      3 assert pal_checker("여보게, 저기 저게 보여?") == True

AssertionError:

이전의 주장 모두 참으로 인정받을 수 있도록 pal_checker() 함수를 수정할 수 있다. 이를 위해 연습문제를 참고한다.

4.6. 연습문제#

  1. (실습) 덱

Contents