02. 큐의 정의와 활용
유명 맛집에 갔다고 가정해봅시다. 대기줄이 너무 길지만, 오늘 아니면 못 먹을 것 같아 꾹 참고 기다리기로 했습니다. 당연하겠지만, 앞 사람들이 중간에 지쳐서 나가지 않는다면 앞 사람들이 모두 들어가야 여러분들이 들어갈 기회가 생기겠죠?
이런식으로 줄을 설 때, 먼저 줄을 선 사람이 먼저 식당에 입장할 수 있다는 것은 길게 설명하지 않아도 모두가 알 것입니다.
우리는 이런 구조를 선입선출 구조 (FIFO; First In First Out) 라고 부르는데, 이번에 배울 큐 라는 자료구조는 이 선입선출 구조를 따르고 있는 구조입니다.
queue는 크게 5가지 함수 사용이 가능합니다.
1. push(x) : x를 queue의 맨 뒤에 추가합니다.
2. size() : queue 안에 들어있는 데이터의 개수를 반환합니다.
3. empty() : queue 안에 남아있는 데이터가 없다면 true, 있다면 false를 반환합니다.
4. front() : queue의 맨 앞에 있는 숫자 값을 반환합니다. 단, queue에서 해당 데이터를 제거하지는 않습니다.
5. pop() : queue의 맨 앞에 있는 숫자 값을 반환합니다. 단, 동시에 queue에서 해당 데이터를 제거합니다.
여러 연산이 순서대로 실행되었을 때의 모습은 다음과 같습니다.
비록 데이터의 삽입과 삭제가 동일한 장소에서 수행되지는 않지만, 다른 값들의 이동이 필요하지 않기 때문에 여전히 삭제와 삽입의 시간복잡도는 으로 동일합니다.
< 배열과 스택, 그리고 큐 >
앞에서 스택과 배열의 연관 관계에 대해 이야기 해보았습니다. 그렇다면 큐는 어떨까요?
이것도 배열의 특성을 잘 생각해보면 금방 답을 구할 수 있을 것입니다. 스택의 경우엔 맨 뒤에서 데이터를 삽입하고 삭제한다면 충분히 을 만들 수 있기 때문에 가능하다고 언급했습니다.
큐의 경우, 배열 맨 앞에서 삽입을 하고 맨 뒤에서 삭제를 하거나, 맨 뒤에서 삽입을 하고 맨 앞에서 삭제를 해야 할 것입니다. 그러나 배열의 맨 앞에서 삭제나 삽입을 진행한다면, 무조건 의 시간복잡도를 보여줄 것입니다. 따라서 배열을 스택처럼 활용할 수는 있지만, 큐처럼 사용하기에는 다소 무리가 따를 것입니다.
다만 맨 앞이나 뒤에서 삽입 삭제가 일어날 때 시간복잡도가 항상 인 경우를 이전에 본 적이 있지 않나요? 네 맞습니다. 바로 연결 리스트를 사용하는 것입니다. 배열 대신 연결 리스트를 이용하여 큐를 구현한다면, 모든 연산에 대해 시간복잡도를 만 갖게 만들 수 있습니다. 스택 역시 연결 리스트를 이용하여 모든 연산에 대해 시간복잡도를 만 갖게 할 수 있습니다.
< 소요시간 2 >
처음 원소가 N개 들어있을 때, 소요시간이 오래 걸리는 것부터 순서대로 나열하세요.
< 큐의 응용 >
앞에서 스택의 응용을 배웠습니다. 그렇다면 큐는 어떤 방식으로 활용할 수 있을까요?
우선, 큐를 처음 설명했을 때 처럼 일자로 줄을 서는 경우에 큐가 사용될 수 있을 겁니다. 이 부분은 앞에서 설명과 문제를 통해 어느정도 익숙했을 것입니다.
또 다른 경우를 살펴보겠습니다. 학생들이 원형으로 서있다고 가정해봅시다. 원의 끝에는 선생님이 계시고 학생이 선생님에게 가면 테스트를 받아 통과되면 집에 가고, 떨어지면 다시 줄에 서서 자기 차례가 될 때 까지 기다려야 한다고 해봅시다.
이것을 컴퓨터로 표현하기 위해선 어떤 자료구조를 사용하는게 좋을까요?
방법은 간단합니다. 원형으로 서 있는 학생 줄의 가운데를 잘라 펼쳐보면, 일자로 되는 것을 볼 수 있습니다. 결국 앞에서 설명했던 일자 줄 구조가 되고, 이것을 큐로 처리하면 될 것입니다.
사실, 큐에 들어간 데이터가 상황에 따라 다시 큐에 들어가야 한다면, 이 구조는 다음과 같이 원형으로 그릴 수 있을 겁니다.
앞에서 설명한 콜 스택 처럼, 이런 큐 구조도 컴퓨터에서 중요하게 사용하고 있는 구조이기 때문에, 이후 여러분들이 컴퓨터를 깊게 공부할 때 다시 볼 수 있을 것입니다!
< 요세푸스 >
유대인 역사가 플라비우스 요세푸스는 전쟁에 참전했다가 자신을 포함해 총 41명의 병사들과 함께 포위 당한 상황에 놓여있었습니다. 그들은 항복할 바에 죽음을 선택하겠다고 말했고, 서로 원형으로 모여서 계속해서 3번째 사람을 죽이는 방식으로 자살을 선택했습니다. 그러나 요세푸스는 살고 싶었고, 머리를 열심히 굴려 마지막까지 살아남은 뒤, 결국 살아남아서 항복했습니다.
요세푸스가 되어서, N명이 포위당한 상황에, 계속해서 K번째 사람이 죽는다면, 여러분들은 몇 번 자리로 가야 살아남을 수 있을까요?
여기서는 queue를 이용해 문제를 풀어보려고 합니다.
예를 들어 N이 5, K가 3인 경우를 살펴보겠습니다.
처음에는 1번에서 시작하여 시계방향으로 계속 회전하게 됩니다.
K가 3이므로 3번째마다 사람을 선택해야 하므로 3번째 사람까지 이동해줍니다.
이제는 3번이 제거가 되어야 합니다.
이러한 과정을 계속 거치다보면 최종적으로 숫자가 하나만 남게 됩니다. 그때의 큐에 남아있는 원소가 저희가 구하고자 하는 답이 됩니다.
이러한 과정을 코드로 구현했을 때, 각 빈칸에 들어가야 할 것을 골라주세요.
function solution(N, K)
set q = empty queue
for i = 1 ... N
q.push(i)
while q.size() != 1
for i = 1 ... K - 1
(1) q.push(q.front())
(2) q.pop()
(3) q.pop()
return q.front()
< 큐 STL >
C++에서는 queue라는 STL을 이용할 수 있습니다.
queue를 사용하기 위해서는 #include <queue> 헤더와, queue<T> name; 형태의 선언이 필요합니다.
T는 타입으로, 큐 안에 들어갈 원소의 타입을 적어줘야 합니다.
또, queue는 원래 std::queue로 쓰여야 하므로 using namespace std;를 미리 적어 queue 만으로도 이용이 가능하도록 하는 것이 좋습니다.
정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하여보세요. 명령어는 총 5가지 입니다.
정수를 관리할 queue는 다음과 같이 선언해 볼 수 있습니다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q;
return 0;
}
queue를 이용할 때 자주 사용되는 것은 다음 5가지 입니다.
명령어 :
- push(E) : 맨 뒤에 데이터 E를 추가합니다.
- size() : 현재 queue에 들어있는 데이터의 수를 반환합니다.
- empty() : 현재 queue가 비어있다면 true, 아니라면 false를 반환합니다.
- front() : queue의 맨 앞에 있는 데이터를 반환합니다.
- pop() : queue의 맨 앞에 있는 데이터를 뺍니다. C++에서의 queue는 pop() 호출시 삭제만 할 뿐, 해당 값을 반환하지 않습니다. 이는 C++의 철학상, 하나의 함수는 하나의 역할만 해야한다는 점과 안전성 측면에서 이렇게 설계되어져 있습니다. 꼭 유의하시기를 바랍니다.
따라서 다음과 같이 코드를 작성해볼 수 있습니다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
queue<int> q; // 정수를 관리할 queue를 선언합니다. => 빈 큐
q.push(3);
q.push(5);
q.push(9);
cout << q.front() << endl; // 가장 앞에 있는 원소를 출력합니다. => 3
q.pop(); // 가장 앞에 있는 원소를 제거합니다.
cout << q.size() << endl; // 원소의 개수를 출력합니다 => 2
while(!q.empty()){ // 가장 앞에 있는 원소부터 순서대로 출력합니다.
cout << q.front() << endl; // 순서대로 5 9 출력됩니다.
q.pop(); // 가장 앞에 있는 원소를 제거합니다.
}
return 0;
}
< 정수 명령 처리 2 >
입력 형식
첫 번째 줄에는 주어지는 명령의 수 N이 주어집니다.
두 번째 줄부터 N개의 줄에 걸쳐 명령이 하나씩 주어집니다. 문제에 나와있지 않은 명령이 주어지는 경우는 없으며, 불가능한 명령이 주어지는 경우 역시 없다고 가정해도 좋습니다.
- 1 ≤ N ≤ 10,000
- 1 ≤ 주어지는 정수 ≤ 100,000
출력 형식
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력합니다.
******************************************************************************************************************************************
C++14
#include <iostream>
#include <queue>
#include <string>
using namespace std;
// 변수 선언
int n;
queue<int> q;
int main() {
// 입력:
cin >> n;
for(int i = 0; i < n; i++) {
string command;
cin >> command;
if(command == "push") {
int x;
cin >> x;
q.push(x);
}
else if(command == "pop") {
int v = q.front();
q.pop();
cout << v << endl;
}
else if(command == "size") {
cout << q.size() << endl;
}
else if(command == "empty") {
if(q.empty())
cout << 1 << endl;
else
cout << 0 << endl;
}
else {
cout << q.front() << endl;
}
}
return 0;
}
< 스택 VS 큐 >
<역지사지>
큐는 데이터를 처리하기 위해 양쪽을 모두 사용하는 자기 자신에 비해 한쪽만 사용하는 스택을 이해할 수 없었습니다. '왜 그럴까?' 생각하다가 스택의 입장을 이해해보기 위해 스택의 연산을 직접 수행해보려고 합니다.
그러나 FIFO 구조인 큐는 LIFO 구조인 스택을 따라할 수 없었습니다. 한참을 고민한 끝에, pop 과정에서 추가적으로 큐를 하나 더 사용하여 스택 기능을 구현할 수 있었습니다.
스택 기능을 재구현했다는 것은, 새로 적힌 함수를 이용하여 다음 테스트를 올바르게 통과하였다는 것을 의미합니다.
function test()
set s = empty stack
s.push(15)
s.push(35)
s.push(20)
print(s.pop()) // 20이 출력되어야 함
print(s.pop()) // 35이 출력되어야 함
print(s.pop()) // 15이 출력되어야 함
stack 기능을 큐로 구현하기 위해서는 다음과 같이 생각해보면 됩니다. stack에서의 push의 경우에는 queue에 push를 해두고, stack에서의 pop의 경우에는 기존 queue에 있던 데이터를 마지막 하나를 제외하고 전부 새로운 큐에 옮겨준 뒤, 기존 큐를 새로운 큐로 대체해두고 마지막 원소를 반환하면 됩니다. 위의 코드를 queue로 구현하여 진행했을 때의 과정을 살펴보면 다음과 같습니다.
이 과정(stack의 push, pop 함수)을 이제 코드로 나타내보려고 합니다.
function Stack.push(q, val)
q.push(val)
function Stack.pop(q)
set new_q = empty queue
while q.size() != (1) 1
new_q.push((2) q.pop() )
set top = q.pop()
q = new_q
return (3) top
1. 먼저 큐에 있는 데이터를 새로운 큐로 옮겨야 한다.
2. 데이터가 앞에서부터 차례대로 pop 되어 new_q로 들어가고, new_q에서도 q에서의 순서가 유지됨
3. 이 때 큐 맨 뒤의 마지막 데이터는 제거되어야 하므로 옮기지 않습니다.
4. q.size() != 1 일 때만 new_q.push(q.pop()) 을 진행시킴
5. q에 남은 데이터를 top 에 옮겨주고, 기존의 큐를 새로운 큐로 대체해준다.
6. 이제 q에서 맨 뒤 원소가 제거되었다.
7. 제거된 데이터인 top 을 반환해주면, Stack.pop 을 구현할 수 있음
< 원형 순열에서의 인원 제거 >
1번부터 N번까지 N명의 사람이 원을 이루면서 앉아있고, 양의 정수 K가 주어집니다.
다음의 연산을 N명의 사람들이 모두 제거될때 까지 진행합니다.
- 1번부터 순서대로 K번째 사람을 제거합니다.
- 한 사람이 제거되면 남은 사람들로 원을 이루며 1번 연산을 과정을 반복합니다.
제거되는 사람의 번호를 순서대로 나열한 순열을 구하는 프로그램을 작성해보세요.
입력 형식
첫 번째 줄에 정수 N과 K가 공백을 두고 순서대로 주어집니다.
- 1 ≤ K ≤ N ≤ 5,000
출력 형식
첫 번째 줄에 제거되는 사람의 번호를 순서대로 나열한 순열을 출력합니다.
입력 : 6 4
출력 : 4 2 1 3 6 5
입력 : 7 3
출력 : 3 6 2 7 5 1 4
<풀이>
큐를 이용
큐를 이용하면 총 N 라운드 동안 K 번씩 이동을 진행 > 총 시간복잡도 O(KN) 에 문제 해결이 가능
#include <iostream>
#include <queue>
using namespace std;
//
namespace 이름 공간, std 클래스 >> 이름 공간에 있는 클래스에 정의되어 있는 함수들을 사용
std에는 cout, cin, endl 등의 함수가 정의
//
// 변수 선언
int n, k;
queue<int> q;
int main() {
// 입력:
cin >> n >> k;
// 큐로 현재 남은 사람들을 관리합니다.
for(int i = 0; i < n; i++)
q.push(i + 1);
while(q.size() != 1) {
// k번째 사람을 찾습니다.
// 이 과정에서 이미 탐색한 사람은 맨 뒤로 옮겨줍니다.
for(int i = 0; i < k - 1; i++) {
q.push(q.front());
q.pop();
}
// k번째 사람을 제거합니다.
cout << q.front() << " ";
q.pop();
}
// 마지막 사람을 제거합니다.
cout << q.front();
return 0;
}
<큐 연습>
다음 코드를 실행했을 때, 반환 되는 결과 값은 무엇인가요? >> 답: 43
function solution()
set q = empty queue
q.push(10)
q.push(15)
q.push(35)
q.push(40)
q.pop()
q.push(20)
q.pop()
q.pop()
q.pop()
q.push(20)
q.push(15)
set result = q.size()
result += q.pop()
result += q.pop()
if q.empty() == true
result *= 2
return result
'AI HW study > 자료구조·알고리즘' 카테고리의 다른 글
| 05. 스택, 큐, 덱 - Deque (0) | 2023.08.18 |
|---|---|
| ** [C++] 입문 (0) | 2023.08.18 |
| 05. 스택, 큐, 덱 - Stack (0) | 2023.08.16 |
| 03. 정렬 - 기수 정렬, 정렬 속도 비교, 병합 정렬, 퀵 정렬, 합 정렬, Stable Sort, In-place Sort (0) | 2023.08.14 |
| 03. 정렬 - Bubble Sort, 선택 정렬, 삽입 정렬 (0) | 2023.08.10 |
