[실전 알고리즘] 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_front 함수야 당연히 덱이니 있어야 정상인데, 이외에도 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로 스택과 큐를 쓰는 것에 충분히 익숙해질 필요가 있습니다. 연습문제에 들어있는 문제들은 그럭저럭 생각을 필요로 하고 구현 난이도도 좀 있는 편이라 도전을 해보면 좋은 훈련이 될 것입니다. 잘 감이 안잡히면 풀이를 찾아보셔도 되지만 구현은 꼭 직접 해보세요.


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

 

  Comments
  • 알린이
    vector와 deque와의 큰 차이점 중 하나가, 연속의 유무라서
    vector의 경우 공간이 부족하면, memory reallocate 과정을 거쳐야 하는데
    deque의 경우 연속되지 않으니, 그냥 새로운 memory block 을 하나 할당하면 되니 평균적인 성능을 보장하네요.

    그래서 그런지 deque에는 capacity와 reserve 가 존재하지 않군요.

    또 원소에 어느방향이던 "iterate"은 가능하나, 연속적이지 않으니 당연히 vector간 포인터간 연산은 불가능할꺼구요.

    그리고 중간에서의 삽입 삭제 연산은 list 에 비해서 굉장히 구리네요.

    이 부분에 대해서 생각을 해본적이 없었는데 덕분에 찾아서 공부하고 가용

    역시 킹갓독 ㄷㄷ
    • 저도 insert/erase 함수가 있는지는 몰랐는데 있길래 찾아보다가 deque랑 vector랑 비교하는 내용을 알게 됐네요. 혹시 면접 질문으로 얻어걸리면 완전 꿀일 것 같아요
    • 알린이
      각 상황마다 시퀀스 컨테이너의 어떤것을 사용하는것이 좋을까요? 의
      답변을 이제 명확히 할 수 있을꺼 같아요 ㅎㅎㅎ
    • 컨테이너 얘기를 들어가려면 써야할 말이 너무 많아서 본문에는 안넣었는데 deque이 vector/list에 비해 컨테이너 생성에 시간이 좀 많이 오래걸려요. 1000만번 생성하는 코드를 작성해보면 시간차이가 확실히 많이 나요. 그래서 문제풀 때 이 점을 조금 주의해야해요.
    • 알린이
      꿀팁 감사합니당.

      사실 바킹독님 문제집 제외하고, deque를 사용해서 푼 문제는 진짜 몇개 없는것 같아요 ㅋㅋ;

      삼성 기출의 2048, 뱀 문제정도만 deque로 푼거같아요.
      게다가 2048은 풀고나니 그냥 똑같이 queue로도 풀수 있었던...
  • jm_kim
    바킹독님 질문이 있습니다.
    스택, 큐, 덱를 지금까지 배웠는데 매번 구현파트에서 약간 망설였습니다, 왜냐면 제가 준비하고 있는 삼성 SW역량 테스트 a는 STL을 사용 할 수 있는걸로 알고 있습니다. 이런경우에도 제가 평소에 STL하고 바킹독님이 알려주신 구현방법을 둘다 연습해야 할까요? 배우는자로서 이런질문이 좋다고 생각은 안하지만, 궁금해서 질문 드립니다.
    • 스택/큐/덱을 직접 구현해보는건 동작 원리와 구현 방법을 이해하고자 하는 이유이고 코딩테스트에서 STL을 쓸 수 있다면 무조건 STL을 쓰는게 낫습니다.

      시간이 넉넉하다면 직접 구현도 해보고 STL 사용법도 익히면 좋지만 코딩테스트까지 시간이 촉박하다면 STL 사용법만 익히고 넘어가시면 되겠습니다.
    • ㅇㅇ
      stl이 속도면에서 직접구현보다 좋은 경우가 많습니다.
  • jm_kim
    빠른답변 감사합니다,
    제가 7월에 인턴실습 중에 a형을 볼거라고 담당자가 알려 주었는데, 코딩테스트를 처음 준비 해보다 보니 시간을 얼만큼 잡을지 모르겠네요 ㅎ 일단 저번주에 학기 끝나자 마자 준비중입니다.
    BFS 이 후 진도들은 아직 업데이트가 안되었는데 옛날 버전을 들어도 문제는 없겠죠?
댓글 쓰기