[바킹독: 알고리즘] 덱(Deque)

※ (링크) 바킹독 유튜브 영상을 통해

학습한 내용을 정리한 것입니다.

 

본인은 JAVA를 활용해 학습하였습니다

비상업적 목적이며, 개인 복습을 위해 업로드한 글임을 다시 한 번 더 이야기드립니다.

 

본문의 모든 내용의 출처는 아래 명시된 링크와 같습니다.

 

[목차] 정의와 성질, 기능과 구현, STL Deque, 연습문제

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

출처: blog.encrypted.gg/935?category=773649

---

정의와 성질

(1) 정의

덱은 Restricted Structure(제한된 구조)의 끝판왕과 같은 느낌의 자료구조입니다. 양쪽 끝에서 삽입과 삭제가 전부 가능한 구조입니다. 덱은 영어로 Deque이며, Double Ended Queue라는 뜻을 갖고 있습니다. 

 

(2) 성질

1. 원소 추가, O(1)
   
   
2. 원소 제거, O(1)
   
   
3. 원소의 제일 앞/뒤 확인, O(1)
   
   
4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가함
   허나 STL Deque에서는 인덱스로 원소에 접근할 수 있음

---

구현

스택과 큐처럼 배열 혹은 연결리스트로 구현할 수 있습니다. 하지만 배열을 이용해 구현하는 것이 더 효율적입니다.

구현에 필요한 요소 [ 원소를 담을 배열, 앞쪽(head)/뒤쪽(tail)를 나타낼 변수 ] 이렇게 세 가지가 필요합니다.

 

1. 필요 요소: 원소를 담을 배열, 앞쪽(head)/뒤쪽(tail)
   
   
2. head는 가장 앞에 존재하는 원소의 인덱스
   tail은 가장 뒤에 있는 원소 인덱스 + 1
   
   
3. head와 tail의 초기값은 MAX
   
   큐에서는 앞쪽에서 제거만 발생하고, 뒤에서 삽입만 발생해 배열 내에 실제 큐에 들어간 원소들이 차지하는 공간이 오른쪽으로 이동하며 확장하는 모양입니다.
   
   덱(Deque)에서는 양쪽에서 삽입이 가능하기에 여의봉처럼 양쪽으로 확장되어야 합니다. 시작지점을 0번지로 할 경우, 왼쪽으로 확장할 수 없기에, 시작 지점을 배열의 중간으로 두는 것입니다. 그렇기에 배열의 크기는 [ 2 * MAX + 1 ]이며, head와 tail의 초기값은 중간 값인 MAX가 되는 것입니다.

구현에 필요한 함수는 아래와 같습니다.

 

• push_front : 앞으로 원소 삽입
  
  
• push_back : 뒤로 원소 삽입
  
  
• pop_front : 앞의 원소 리턴 후 삭제
  
  
• pop_back : 뒤의 원소 리턴 후 삭제
  
  
• front
  
  
• back

 

내용 정정(2021.04.13)

JAVA에서 Deque 구현은 LinkedList<E> 을 활용하는 것이 더 좋을 것으로 보임! 값을 통해 인덱스 번호를 반환할 수 있기 때문.

덱 자료구조 메서드 정리가 잘 된 블로그 링크 

soft.plusblog.co.kr/24

[Java(자바)] Deque(덱/데크) 자료구조

 

앞쪽과 뒤쪽에서 모두 추가/제거가 필요하다면 덱을 사용하는 것이 효율적이지만, 굳이 배열로만 해결이 가능하다면 배열로 해결하는 것도 괜찮습니다.

---

연습 문제

(1) BOJ 10866번: 덱

 

github.com/encrypted-def/basic-algo-lecture/blob/master/workbook.md

encrypted-def/basic-algo-lecture

www.acmicpc.net/workbook/view/7311

문제집: 0x07강 - 덱 (BaaaaaaaaaaarkingDog)

 

 

BOJ 5430 다시 풀어보기