챕터2-2. 자료구조 | 큐(Queue)
큐의 개념
# 큐는 무엇인가
- 한쪽 끝에서만 자료를 넣고 다른 한쪽 끝에서만 뺄 수 있는 자료구조
- 먼저 넣은 것이 가장 먼저 나오기 때문에 First In First Out(FIFO) 라고도 한다.
- push와 pop을 진행하다보면 begin변수의 값은 계속 증가만 하기 때문에 배열이 꽉 차지 않은 상황임에도
더이상 데이터를 집어넣을 수 없는 상황이 발생한다.
이를 보완한 방법으로 '순환큐'라는 게 존재하는데 이는 심화과정이므로 나중에 공부하고 일단 아래 부분들만 알아두자.
# 직접 구현하기 위해 필요한 요소
- 데이터를 저장할 '배열' (링크드리스트로 구현할 수도 있다고 함)
- pop하면 나올 위치를 가리키는 'begin 변수'
- push가면 들어갈 위치를 가리키는 'end 변수'
# 큐의 연산
- push() : 큐에 자료를 넣는 연산(back의 위치에서 일어남)
- pop() : 큐에서 자료를 빼는 연산(front의 위치에서 일어남)
- front() : 큐의 가장 앞에 있는 자료를 보는 연산
- back() : 큐의 가장 뒤에 있는 자료를 보는 연산
- empty() : 큐가 비어있는지 아닌지를 알아보는 연산
- size() : 큐에 저장되어 있는 자료의 개수를 알아보는 연산
@ push 연산의 예시
queue[end] = val
end += 1
@ pop 연산의 예시
queue[begin] = 0 // 생략해도 될듯하다. 어차피 나중에 덮어쓰면 되므로
begin += 1
@ size 연산의 예시
size = end - begin
@ empty 연산의 예시
empty = (begin == end)
큐를 적용한 문제풀이
# 큐를 구현하는 문제
- https://www.acmicpc.net/problem/10845
@ 직접구현(C++) : 배열이용
@ C++의 경우에는 STL의 queue을 사용함
@ Java의 경우에는 java.util.Queue 사용함
@ python의 경우에는 Queue 모듈을 사용함
# 조세퍼스 문제
- https://www.acmicpc.net/problem/1158
- N = 7, K= 2 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop (2pop 1push)
- N = 7, K= 3 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop push pop (3pop, 2push)
- N = 7, K= 4 일 때 1개의 숫자를 제거하는데 필요한 횟수 : pop push pop push pop push pop (4pop, 3push)
- 따라서 N, K 가 주어지면 1개의 숫자를 제거하는게 필요한 횟수는 (Mpop, M-1push) 가 되고 이를 N개의 숫자에 대해 수행하면
전체 시간복잡도는 O(N*(K+K-1)) = O(N*(2K-1)) = O(NK) 이다.
1<=K<=N<=5000 이므로 최대 반복횟수는 5000^2 = 25000000 이고 이는 1억을 넘지 않으므로
큐를 이용한 방법을 사용해서 풀 수 있는 것이다.
