[바킹독 실전 알고리즘] 강의 노트_0x05강 스택~0x08강 스택의 활용

바킹독 실전 알고리즘 강의를 듣게 되어서 강의 필기를 할겸 정리용으로 글 씁니다. 문제시 삭제 하겠습니다.

 

 

 

제한된 자료구조 : 스택, 큐, 덱

 

0x05강 스택

스택: FILO(first in last out) 

ex) 엘리베이터 

 

스택의 성질

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

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

3. 제일 상단의 원소 확인이 O(1)

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

-> 만들 수는 있음.

 

 

1. 배열을 이용해 구현하는 것이 편함. 

const int MX= 100005;
int dat[MX];
int pos=0;

 

 

push,pop 함수 

 

값 추가 (push) : pos++

값 삭제 (pop) : pos-- 

 

2.STL stack

 

⚠️스택이 비어 있을 때 pop(), top()하지 않기.-> empty()로 먼저 확인하기. 

 

 

 

백준 10773

 

---

0x06강 큐

 

큐: FIFO(first in first out)

ex) 공항 탑승 수속

 

큐의 성질

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

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

3. 제일 상단의 원소 확인이 O(1)

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

 

 

1. 배열로 구현

const int MX= 100005;
int dat[MX];
int head=0,tail=0;

배열로 구현시 삭제가 발생할 때마다 쓸모 없는 공간이 생김 

=> 원형큐 를 사용하면 됨.

 

 

2. STL queue

BFS와 Flood fill을 할 때 사용함. 

 

 

---

0x07강 덱

덱:양쪽 끝에서 삽입,삭제가 모두 가능함.

 

덱의 성질

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

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

3. 제일 상단의 원소 확인이 O(1)

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

 

 

1. 배열로 구현

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

 

 head와 tail의 초기값이 MX인 이유: 시작 지점이 0번째인 경우 양방향으로 확장이 불가능함. 중간에 있어야 확장이 되기 때문에 전체 크기의 중간, 2*MX+1의 중간인 MX에서 시작함. 

 

 

2. STL deque

 

STL vector에서 사용하는 함수를 전부 사용할 수 있음-> insert(),erase()

 

 

---

0x06강 스택의 활용

 

수식의 괄호쌍 

=> 괄호가 수식에 맞게 적용된 것인지 확인하기.

 

1. 열고 닫는 괄호의 갯수 

2. 인접한 소괄호, 중괄호.. 를 지우기 

3. 문자열을 앞에서부터 읽어나갈 때, 닫는 괄호는 남아 있는 괄호 중에서 가장 최근에 들어온 여는 괄호와 짝을 지어 없애버리는 명령이라고 생각해도 된다.

 

=> 1,2,3 해당 개념을 이용해 수식의 괄호쌍이 올바른지  스택(stack)으로 구현할 수 있음.

 

 

 

백준 4949

백준 10799

백준 2054