[바킹독의 실전 알고리즘] 0x07 덱 복습 -C++

앞으로 작성할 내용들은 유튜브에서 바킹독님의 알고리즘 강의를 들은 내용을 토대로 하여,

필요할 경우 전공으로 배운 내용을 조금씩 엮어 복습한 내용입니다.

바킹독의 실전 알고리즘 0x07강 링크

 

강의내용 복습

덱의 정의와 성질

덱 : 양쪽 끝에서 삽입과 삭제가 전부 가능한 자료구조

*자료구조에서 덱은 deque(Double End Queue)를 의미

 

덱의 성질

1. 원소의 추가가 O(1)

2. 원소의 제거가 O(1)

3. 제일 앞/뒤의 원소 확인이 O(1)

4. 제일 앞/뒤가 아닌 나머지 원소들의 확인/변경은 원칙적으로 불가능

     *STL deque에서는 인덱스로 원소에 접근 가능

 

덱의 기능과 구현

배열과 연결리스트 두개 모두 구현 가능하나, 배열을 이용하는게 구현하기 쉽다.

const int MX = 1000005;
int dat[2*MX+1];	//원소를 담을 큰 배열
int head = MX, tail = MX;	//가장 앞쪽, 가장 뒤쪽+1을 가리킬 변수

head와 tail의 초기값이 0이 아닌 MX인 이유

queue에서 왼쪽에서 삭제, 오른쪽에서 삽입이 이루어질 경우 실제 배열에서 원소들이 저장된 공간은 점점 오른쪽으로 이동하게 된다.

하지만 deque는 양쪽에서 삽입과 삭제를 모두 할 수 있기 때문에 시작점 MX를 중심으로 하여 양쪽으로 저장공간이 확장되는 모양이다. 시작점을 0으로 잡으면 왼쪽으로는 확장이 불가하기 때문에 초기값을 MX로 잡는다.

 

선형 덱 예시

#include <bits/stdc++.h>
using namespace std;

const int MX = 1000005;
int dat[2*MX+1];
int head = MX, tail = MX;

void push_front(int x){
    head--;
    dat[head] = x;
}

void push_back(int x){
    dat[tail] = x;
    tail++;
}

void pop_front(){
    head++;
}

void pop_back(){
    tail--;
}

int front(){
    return dat[head];
}

int back(){
    return dat[tail-1];
}

void test(){
  push_back(30); // 30
  cout << front() << '\n'; // 30
  cout << back() << '\n'; // 30
  push_front(25); // 25 30
  push_back(12); // 25 30 12
  cout << back() << '\n'; // 12
  push_back(62); // 25 30 12 62
  pop_front(); // 30 12 62
  cout << front() << '\n'; // 30
  pop_front(); // 12 62
  cout << back() << '\n'; // 62
}

int main(void){
  test();
}

 

STL deque

STL vector와 유사...

앞쪽과 뒷쪽에서의 추가와 제거가 모두 필요하다면 STL deque를,

앞쪽에서의 추가와 제거가 필요하지 않고 배열같은 느낌으로 쓰고 싶다면 STL vector를 쓰면된다.

단, STL deque는 vector와 달리 모든 원소들이 메모리 상에 연속하게 존재하는 것이 아니다.

 

STL deque 기본 사용법

1. Deque 선언

#include <deque>

deque<자료형> 이름; 으로 선언한다.

deque<int> DQ;

 

2. 제일 앞/뒤 데이터 추가

이름.push_front(데이터); 으로 데이터를 앞에 추가한다.

이름.push_back(데이터); 으로 데이터를 뒤에 추가한다.

  DQ.push_front(10); // 10
  DQ.push_back(50); // 10 50
  DQ.push_front(24); // 24 10 50

 

3. 제일 앞/뒤 데이터 삭제

이름.pop_front(); 으로 맨앞의 데이터를 삭제한다.

이름.pop_back(); 으로 맨뒤의 데이터를 삭제한다. 

  DQ.pop_front(); // 10 50
  DQ.pop_back(); // 10

 

4. 제일 앞/뒤 데이터 접근

이름.front() 으로 맨 앞의 데이터를 반환한다.

이름.back() 으로 맨 뒤의 데이터를 반환한다.

DQ.front()
DQ.back()

 

5. Deque의 사이즈 반환

이름.size() 로 Deque의 사이즈를 반환한다.

DQ.size()

 

6. Deque가 비어있는지 확인

이름.empty() 는 dque가 비어있으면 true를 반환한다.

DQ.empty()

 

7. 모든 원소 제거

이름.clear(); 으로 Deque의 모든 원소를 삭제한다.

DQ.clear();

 

8. 인덱스로 원소에 삽입/삭제/접근

이름.insert(위치, 데이터); 으로 중간에 데이터를 추가한다.

이름.erase(위치); 으로 해당 위치에 있는 데이터를 삭제한다.

  DQ.insert(DQ.begin()+1, 33); //begin()+1 위치에 33 삽입
  DQ.erase(DQ.begin()+2); //begin()+2 위치의 데이터 제거

 

이름[인덱스] 로 중간에 있는 데이터에 접근한다.

DQ[index] //index 위치의 원소

 

연습문제 복습

강의 후반부 및 아래 링크로 들어가면 나오는 문제들 중 해당 강의에 맞는 연습문제들을 풀고

정답코드와 비교하며 얻은 내용들을 간단히 정리한 내용입니다.

연습문제 링크

 

deque나 vector 등에서 주어진 범위 안에 원하는 값을 찾는 함수

find(InputIterator first, InputIterator last, const T& val);

첫 번째로 일치하는 원소를 가리키는 반복자를 반환한다. 일치하는 원소가 없을 경우 last 가 리턴된다.

first, last : 원소들의 시작과 끝을 가리키는 반복자들. 이 때 확인하는 범위는 first 가 가리키는 원소는 포함, last 가 가리키는 원소는 포함되지 않음에 주의. [first, last)

val : 비교할 값

 

 

*푸는중