2일차 강의요약 (4강 ~ 8강)

4강

- STL의 list는 이중연결리스트 구조

- 야매 연결 리스트 (배열로 구현하는 간결 연결리스트)

const int MX = 1000005;

int dat[MX], pre[MX], nxt[MX];

int unused = 1;

 

fill(pre, pre+MX, -1);

fill(nxt, nxt+MX, -1);

 

1406번 에디터 

→ STL list, 야매 연결 리스트를 사용하여 풀어보기

 

5강 (스택)

push, pop, top, emtpy, size

스택이 비어있을 때에는 top이나 pop을 호출하지 않도록 주의

 

6강 (큐)

원형큐 → push와 pop을 반복하다보면 점점 뒤로 밀리는 점 개선

 

7강 (덱)

stl deque에선 인덱스로 원소에 접근할 수 있음

stl deque는 front에서도 O(1)에 추가와 제거가 가능한 vector 느낌임

→ vector와 달리 deque는 원소들이 메모리 상에 연속하게 배치되어 있지 않음

앞쪽에서 추가와 제거가 필요하지 않고 배열과 같은 느낌으로 사용하는 것은

vector를 사용하는 것이 더 적절함.

 

8강 (스택의 활용)

수식의 괄호 쌍

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

 

1. 여는 괄호가 나오면 스택에 추가

2. 닫는 괄호가 나왔을 경우,

 2-1 스택이 비어있으면 올바르지 않은 괄호 쌍

 2-2 스택의 top이 짝이 맞지 않는 괄호일 경우 올바르지 않은 괄호쌍

 2-3 스택의 top이 짝이 맞는 괄호일 경우 pop

3. 모든 과정을 끝낸 후 스택에 괄호가 남아있으면 올바르지 않은 괄호 쌍,

남아있지 않으면 올바른 괄호 쌍