[실전 알고리즘] 0x07강 - 덱

안녕하세요, 오늘도 반갑습니다. 스택과 큐에 이어 이번에는 덱을 다루겠습니다.

 

목차가 0x02만 바뀌고 계속 똑같습니다. 한 번 눈으로 슥 훑고 넘어가겠습니다.

 

덱은 Restricted Structure의 끝판왕과 같은 느낌의 자료구조인데, 양쪽 끝에서 삽입과 삭제가 전부 가능합니다. 참고로 자료구조의 덱은 deque고 Double Ended Queue라는 뜻을 가지고 있습니다. 우리가 하스스톤이나 유희왕에서 얘기하는 덱은 Deck라서 발음은 둘 다 덱으로 똑같긴 해도 다른 단어입니다.

 

아무튼 덱은 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조이니 스택과 큐를 덱의 특수한 예시라고 생각해도 괜찮겠습니다.

 

덱에서도 삽입, 삭제, 제일 앞/뒤 원소의 확인이 다 O(1)입니다. 그리고 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 원칙적으로 불가능한데 독특하게도 STL deque에서는 인덱스로 원소에 접근할 수 있습니다. STL stack, queue에서 불가능했던걸 생각하면 꽤 독특한 일입니다.

 

덱도 스택이나 큐처럼 배열 혹은 연결 리스트 둘 다를 가지고 구현할 수 있지만 배열을 이용하는게 구현이 더 쉽기 때문에 배열을 이용한 구현만 같이 다룰 것입니다.

 

일단 필요한 변수는 큐랑 똑같이 원소를 담을 큰 배열 한 개와 앞쪽, 뒤쪽을 가리킬 변수 두 개입니다. 이 때 head와 tail을 두는 방식도 큐와 똑같습니다. head는 가장 앞에 있는 원소의 인덱스이고 tail을 가장 뒤에 있는 원소의 인덱스 + 1입니다. 그리고 head와 tail의 초기값이 0이 아니라 MX인데 이 부분을 좀 짚고 넘어가겠습니다.

 

왜 저렇게 두는거냐면, 큐에서는 앞쪽에서는 제거만 발생하고 뒷쪽에서는 삽입만 발생하다보니 배열 내에서 실제 큐에 들어간 원소들이 차지하는 공간이 점점 오른쪽으로 이동하면서 확장하는 모양이었습니다.

 

하지만 덱에서는 양쪽에서 모두 삽입이 가능합니다. 그렇기 때문에 마치 여의봉처럼 양쪽으로 확장해야 합니다. 그러면 별 생각 없이 시작 지점이 0번지로 뒀을 경우 왼쪽으로 확장을 할 수가 없게 됩니다. 대신에 시작 지점을 배열의 중간으로 둬야 합니다. 중간으로 두면 중앙에서 양쪽으로 확장이 가능합니다. 그래서 배열의 크기는 2*MX+1이고 head와 tail의 초기값은 MX인 것입니다.

 

덱도 원형으로 구현을 할 수 있지만 코딩테스트에서는 그냥 배열을 충분히 크게 잡으면 되니까 그냥 선형으로만 구현을 하겠습니다. 우리가 구현해야 할 함수는 push_front, push_back, pop_front, pop_back, front, back 함수입니다.

 

설령 앞의 스택과 큐 강의는 직접 구현을 하지 않고 그냥 슬라이드에 적힌 코드를 눈으로 본게 다라고 하더라도, 이번 덱만큼은 연습을 하는 차원에서 꼭 직접 짜봤으면 좋겠습니다. 스택과 큐를 구현했던 그 느낌을 가지고 배열의 어디에 값을 넣어야 하고 어떤걸 반환해줘야 하는지 잘 생각해보면 크게 어렵지는 않을 것입니다.(템플릿 링크)

 

다 짜보셨나요? 제가 작성한 각 함수들을 차근차근 설명을 드리려면 드릴 수 있긴 한데 이미 스택이나 큐에서 했던 것들의 반복이라 그냥 코드만 보여드리겠습니다. head와 tail이 어디를 가리키고 있는지 잘 생각해보면 저 코드들이 왜 저렇게 되는지 알 수 있을 것입니다. 전체 코드는 깃헙에서 확인할 수 있습니다.

 

물론 STL에 덱이 있어서 그냥 가져다쓰면 되는데, STL deque은 매우 독특하게도 double ended queue라는 느낌보다는 vector랑 비슷한데 front에서도 O(1)에 추가와 제거가 가능한 느낌이 강합니다. pop_front, push_front, pop_back, push_back 함수야 당연히 덱이니 있어야 정상인데, 이외에도 19-25번째 줄을 보면 insert도 있고 erase도 있고 인덱스로 원소에 접근도 할 수 있습니다.

이와 같이 STL vector에서 제공되는 기능을 STL deque에서도 다 제공해주고 심지어 deque은 front에서도 O(1)에 추가와 제거가 가능하니 deque이 vector보다 상위호환이 아닌가 하는 생각이 들 수 있겠지만, vector와 달리 deque은 모든 원소들이 메모리 상에 연속하게 배치되어 있지 않습니다. 구조에 대해 자세히 설명을 드리고 싶지만 강의의 난이도를 많이 벗어나는 내용인 것 같아서 궁금하시다면 스스로 c++ deque vs vector와 같은 검색으로 찾아보시면 되겠습니다.

 

다만 어떤 것 하나만 알고 가시면 되냐면, 앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하면 당연히 STL deque을 사용하는게 효율적이지만 굳이 앞쪽에서의 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 쓰고싶을 땐 STL deque말고 STL vector를 쓰면 됩니다. 참고로 deque 레퍼런스 문서에도 4번째 문단에 "Both vectors and deques provide a very similar interface" 어쩌구저쩌구 하면서 관련 얘기가 나와있어서 한 번 읽어보시는 것도 좋습니다.(레퍼런스 링크, 예제 링크)

 

이제 덱의 구현을 연습해볼 수 있는 연습문제를 풀어보겠습니다(BOJ 10866번: 덱).먼저 STL을 써서 풀어본 코드입니다. 그냥 멤버 함수들을 적재적소에 잘 쓰면 됩니다.

 

그 다음으로는 직접 구현한 덱을 이용한 코드입니다. 이것도 예외처리만 좀 신경써주고 크기를 tail-head로 계산할 수 있다는 점만 이용하면 됩니다.

 

이번 단원을 끝으로 스택 큐 덱 3부작이 끝이 났습니다. 뭔가 구현 방식도 비슷하고 강의의 흐름 자체가 다 동일했어서 수월했을 것 같습니다.

 

다음 단원에서는 스택의 응용을 다루고 그 뒤로는 BFS와 DFS를 들어갈거라 STL로 스택과 큐를 쓰는 것에 충분히 익숙해질 필요가 있습니다. 연습문제에 들어있는 문제들은 그럭저럭 생각을 필요로 하고 구현 난이도도 좀 있는 편이라 도전을 해보면 좋은 훈련이 될 것입니다. 잘 감이 안잡히면 풀이를 찾아보셔도 되지만 구현은 꼭 직접 해보셔야 합니다.

그러면 다음 시간에 만나요~