Queue
메모리 안 데이터를 더욱 효율적으로 다루기 위해 만들어진 데이터 참조 방식.
한쪽 끝에서 원소를 넣고 반대쪽 끝에서 원소를 뺄 수 있는 자료구조 (First in First out)
큐에서는 추가되는 곳을 뒤쪽(rear)이라고 하고 제거되는 쪽을 앞쪽(front)이라고 한다.
제일 앞, 뒤가 아닌 나머지 원소들의 확인/변경이 불가능하다.
시간복잡도
| 연산 | 시간복잡도 |
| 삽입 | O(1) |
| 제거 | O(1) |
| 앞/뒤 원소 확인 | O(1) |
Deque
양쪽 끝에서 삽입과 삭제가 전부 가능하며 Double Ended Queue라는 뜻을 가지고 있다.
제일 앞/뒤가 아닌 나머지 원소들의 확인/변경이 불가능하지만 STL deque에서는 인덱스로 원소에 접근이 가능하다.
시간복잡도
| 연산 | 시간복잡도 |
| 삽입 | O(1) |
| 제거 | O(1) |
| 앞/뒤 원소 확인 | O(1) |
<11866 - 요세푸스 문제 0>
https://www.acmicpc.net/problem/11866
n명의 사람이 원을 이뤘을 때 k번째 사람을 제거하는 문제다. n이 7, k가 3이면 먼저 1에서 3번째인 3번째를 제거하고, 제거된 사람을 기준으로 다시 3번째 사람을 제거하는 방식이다.
풀이
큐의 경우 가장 앞쪽의 사람만 제거할 수 있기 때문에 k번째 사람이 맨 앞쪽에 올 때까지 이전의 사람들을 pop하고 다시 큐의 뒤쪽에 push하는 과정이 필요하다. 해당 과정을 반복문을 통해 진행해 모두 제거될 때까지 진행하면 된다. 결과를 출력할 시 형식에 맞춰서 출력하는 것을 주의해야한다.
(요세푸스 순열에 대해 구글링 해봤는데 흥미로운 일화가 있다. 요세푸스라는 지휘관이 유대-로마 전쟁 때 패배해 죽을 위기에 처했는데 요세푸스 순열을 이용해 살아남을 수 있었다는 이야기다.)
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, k = 0;
cin >> n >> k;
int* arr = new int[n];
queue<int> q;
for (int i = 1; i <= n; i++) {
q.push(i);
}
cout << "<";
while (q.size() != 1) {
for (int i = 1; i < k; i++) {
int tmp = q.front();
q.push(tmp);
q.pop();
}
cout << q.front();
q.pop();
cout << ", ";
}
cout << q.front() << ">";
return 0;
}
<5430 - AC>
https://www.acmicpc.net/problem/5430
수의 순서를 뒤집는 함수, 첫번째 수를 버리는 함수를 구현해 여러 번의 테스트 케이스를 해야한다.
풀이
이 문제에서 구현해야하는 ‘뒤집기’, ‘버리기’를 통해 앞에서 삭제, 뒤에서 삭제가 모두 가능해야한다. 따라서 덱을 사용하는 문제라는 것을 알 수 있다. 문자열로 입력받은 배열을 덱으로 만들고 배열을 뒤집혀있는지 아닌지 확인하고, 에러가 발생했는지 아닌지만 확인하면 문제를 풀 수 있다.
#include <iostream>
#include <deque>
#include <string>
using namespace std;
int main() {
int t, n= 0; //테스트 케이스 개수, 배열 안의 수의 개수
string p, str; //테스트 케이스의 수행할 함수, 배열 문자열
deque<int> dq;
cin >> t;
while (t--) {
cin >> p >> n >> str;
string tmp;
for (int i = 0; i < str.size(); i++) {
if ((str[i] == ',') || (str[i] == ']')) {
if (tmp != "") {
dq.push_back(stoi(tmp));
tmp.clear();
}
}
else if (str[i] != '[') {
tmp += str[i];
}
}
bool error = false;
bool reverse = false;
for (int i = 0; i < p.size(); i++) {
if (p[i] == 'R') {
reverse = !reverse;
}
else { //'D'
if (!reverse) { //false
if (!dq.empty()) {
dq.pop_front();
}
else {
error = true;
cout << "error" << endl;
break;
}
}
else { //true
if (!dq.empty()) {
dq.pop_back();
}
else {
error = true;
cout << "error" << endl;
break;
}
}
}
}
if (!error) { //false
cout << "[";
if (!reverse) { //false
while ((dq.size() != 1) && (!dq.empty())) { //n~2
cout << dq.front() << ",";
dq.pop_front();
}
if (dq.size() == 1) { //1
cout << dq.front();
dq.pop_front();
}
cout << "]" << endl;
}
else {//true
while ((dq.size() != 1) && (!dq.empty())) {
cout << dq.back() << ",";
dq.pop_back();
}
if (dq.size() == 1) { //1
cout << dq.back();
dq.pop_back();
}
cout << "]" << endl;
}
}
}
return 0;
}
<10025 - 게으른 백곰>
https://www.acmicpc.net/problem/10025
슬라이딩 윈도우 관련 문제다. 창문을 순서대로 옮겨 범위 내의 얼음의 합을 확인해 최대값을 구해야 한다.
풀이
슬라이딩 방식의 특성상 앞에서 pop되고 뒤에서 push되기때문에 큐를 사용해 문제를 풀 수 있다. 창문이 한 칸씩 밀려날 때마다 앞쪽의 값 없애고, 뒤쪽에 값을 추가하면 된다. 이때 최대 배열의 크기로 배열을 선언하면 스택 오버플로우 에러를 겪을 수 있다. 이때 배열을 지역변수가 아닌 전역함수로 선언하면 해결할 수 있다.
#include <iostream>
#include <queue>
using namespace std;
int arr[1000001];
int main() {
int n, k, g, x, sum = 0, max = 0;
queue<int> q;
cin >> n >> k;
k = k * 2 + 1;
while (n--) {
cin >> g >> x;
arr[x] = g;
}
for (int i = 0; i < 1000001; i++) {
if (q.size() < k) { //큐가 다 차있지 않음
q.push(arr[i]);
sum += arr[i];
}
else {
sum -= q.front();
q.pop();
q.push(arr[i]);
sum += arr[i];
}
if (sum > max) {
max = sum;
}
}
cout << max << endl;
return 0;
}
<15565 - 귀여운 라이언>
https://www.acmicpc.net/problem/15565
라이언 인형이 K개 이상 있는 가장 작은 연속된 집합의 크기를 구해야 한다.
풀이
이 문제는 투 포인터 관련 문제다. 두 변수로 부분 배열의 앞과 끝의 위치를 기록하면서 문제를 풀면 된다. 이번 주 주제가 큐와 덱이므로 큐를 사용했지만 배열만을 통해서 구현할 수 있는 문제다. K개 이상의 라이언 인형을 포함하는 배열이 없다면 -1을 출력하는 것을 주의해야한다.
#include <iostream>
#include <queue>
using namespace std;
int main() {
int n, k, doll, sum = 0;
cin >> n >> k;
int width = n + 1, min = n + 1; //최대범위 지정
queue<int> q;
int* arr = new int[n];
for (int i = 0; i < n; i++) { //라이언=1, 어피치=2
cin >> doll;
arr[i] = doll;
}
int last = 0;
int first = 0;
while (first < n) {
if (sum < k) { //k개 이하
if (last < n) {
q.push(arr[last]);
if (arr[last] == 1) sum++;
last++;
}
else {
if (min == n + 1) {
cout << "-1" << endl;
return 0;
}
else break;
}
}
else { //k개
if (q.front() == 1) sum--;
q.pop();
first++;
}
if (sum == k) {
width = q.size();
if (width < min) min = width;
}
}
cout << min << endl;
return 0;
}
<2346 - 풍선 터트리기>
https://www.acmicpc.net/problem/2346
원형으로 놓여있는 풍선의 종이에 적힌 값만큼 이동해 다음 풍선을 터트리는 과정을 진행한다.
풀이
5430 - AC의 문제와 마찬가지로 양끝으로 삭제, 추가가 자유로워야하기 때문에 덱을 사용하는 것이 편리하다. 풍선에는 ‘순서 값’과 ‘종이에 적힌 값’(이동하는 정도)이 필요하기 때문에 utility의 pair을 사용해 값을 저장했다. 종이의 값이 양수면 순서대로, 음수면 반대로 움직인 후 풍선을 제거해야한다. 따라서 11866 - 요세푸스 문제 0, 5430 - AC와 유사하게 push_back과 push_front를 적절히 사용해 순서를 조절해야 한다.
#include <iostream>
#include <utility>
#include <deque>
using namespace std;
deque <pair<int, int>> dq;
int move(int mv) {
pair<int, int> del;
if (mv > 0) {//양수
for (int i = 0; i < mv-1; i++) {
dq.push_back(dq.front());
dq.pop_front();
}
del = dq.front();
dq.pop_front();
cout << " " << del.first;
return del.second;
}
else { //음수
for (int i = 0; i < mv*-1-1; i++) {
dq.push_front(dq.back());
dq.pop_back();
}
del = dq.back();
dq.pop_back();
cout << " " << del.first;
return del.second;
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(NULL); // 입력 속도 향상
int n, tmp, mv = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> tmp;
dq.push_back(make_pair(i + 1, tmp)); //<순서, 값>
}
mv = dq.front().second; //1번 삭제
cout << dq.front().first;
dq.pop_front();
while (!dq.empty()) {
mv = move(mv);
}
return 0;
}'Group Study (2022-2023) > Algorithm' 카테고리의 다른 글
| [Algorithm] 6주차 스터디 - 이분탐색과 파라메트릭 탐색 (0) | 2022.11.20 |
|---|---|
| [Algorithm] 5주차 스터디 - 다이나믹 프로그래밍 (0) | 2022.11.12 |
| [Algorithm] 3주차 스터디 - 스택 (0) | 2022.10.31 |
| [Algorithm] 2주차 스터디 - 정렬 (1) | 2022.10.09 |
| [Algorithm] 1주차 스터디 - 브루트 포스와 백트래킹 (0) | 2022.10.02 |