10. 큐 이론

https://howudong.tistory.com/86#google_vignette

큐의 이해

선입 선출(FIFO, First-in First-out)

: 가장 먼저 삽입되는 개체가 가장 먼저 삭제되는 구조, 편의점에서 물건 채울때 원리

- 전단(front)은 큐에서 삭제가 일어나는 곳

- 후단(rear)은 큐에서 삽입이 일어나는 곳

큐의 연산 - 삽입(Enqueue)

- 비어 있는 큐의 초기 상태에는 Front와 Rear 값 모두 -1로 설정.

- 자료가 삽입될 때마다 Rear가 1씩 증가하며 이동

- 새로운 자료를 삽입하기 위해서는 먼저 Rear 포인터를 증가시키고, 그 위치에 자료를 입력

큐의 연산 - 삭제(Dequeue)

- Front 포인터가 1씩 증가하며 자료를 삭제

- 마지막으로 입력된 자료가 삭제하면 Front 포인터와 Rear 포인터의 값이 같아짐.

큐의 연산

큐의 단점

- 위 사진은 4개의 공간을 가지는 큐 구조에 'A', 'B', 'C', 'D' 4개의 자료를 삽입(Enqueue)하고 2개의 자료를

삭제(Dequeue)한 경우

- 여기서 생각할 수 있는 큐의 단점은?

 

원형 큐의 이해

-원형큐는 Rear나Front가 배열의 끝에 도달하면 회전하도록 하여 메모리 공간을 좀 더 효율적으로 사용할 수 있음.

 

- Front와 Rear의 초깃값은 0

- 원형 큐는 자료 공간이 가득찬 것과 빈 것을 구분하기 위해 Front가 위치한 곳은 자료를 저장할 수 없도록 비워두는 것이 일반적

- Front와 Rear의 값이 같다면 Empty

- Front의 공간은 항상 비워 두기 때문에 Rear+1의 위치가 Front와 같게 된다면 Full

 

큐의 구현 - 기본 셋팅

구현할 함수

원형큐 구현

원형큐의 구현 - 기본 셋팅

+ 선형 큐에서 추가로 print_queue함수를 만들어보자

큐 응용문제

큐 구현

https://www.acmicpc.net/problem/18258

 

1.STL vector를 사용하여 문제를 풀어보자.

2. STL queue를 사용하여 문제를 풀어보자.

 

3. 무슨 차이일까?(힌트: 시간복잡도 - 교과서 p149)

 

알고리즘 성능 분석

시간 복잡도란

특정 알고리즘이 얼마만큼의 시간을 필요로 하는가를 측정하는 것

공간 복잡도란

얼마만큼의 공간을 필요로 하는가를 측정하는 것

 

현재 대부분의 시스템에서 메모리 용량이 기하급수적 발전하고 있는 만큼 공간 복잡도에 비해 시간 복잡도에 대한 중요도가 훨씬 높게 평가되고 있다.

 

빅오 표기법

가장 널리 이용되는 시간복잡도 표기법

연산의 횟수와 프로그램 실행시간에 비례

-> 총 연산의 횟수를 가지고 시간복잡도를 구함

 

n개의 자료가 들어온다면 왼쪽의 프로그램은 몇번의 연산을 할까?

큐의 성질

1. 원소의 추가 O(1)

2. 원소의 제거 O(1)

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

덱(deque)

덱(deque)은 double-ended queue의 줄임말

전단(front)와 후단(rear)에서 모두 삽입과 삭제 가능한 큐

덱 연습문제

https://www.acmicpc.net/problem/5430

reverse 함수를 쓰면

시간복잡도가 O(n)가 되어 시간초과가 뜬다!

reverse함수를 쓰지 않고 덱의 상태를 거꾸로 나타내기 위해서 어떻게 하면 좋을까?

 

백준 큐 문제 풀기