티스토리 뷰
BFS에 자주 사용되는 Queue (알고리즘 문제풀이 기준), 그리고 정렬에 자주 사용되는 Prioriry Queue(우선순위 큐, 힙)의 사용법에 대해서 알아보도록 하겠습니다.
( Queue에 대한 정보는 C++ Reference를 참고했습니다.)
1. Queue의 특성
Queue는 FIFO입니다. FIFO는 First in First out으로, 먼저 들어온 것이 먼저 나갑니다. 그냥 마트나, 뭐 놀이기구 탈 때 줄 서는 거랑 똑같다고 생각하면 됩니다. 먼저 오는 사람이 탈출구에서 가장 가깝고 먼저 서비스 받음을 알 수 있습니다.
template을 보면, template <class T, class Container = deque<T>> class queue입니다.
queue도 stack과 마찬가지로 내부적으로는 deque로 구현되어 있습니다. 그래서 queue의 메서드를 실행하면 내부적으로 deque의 매서드들이 그 연산을 처리해줍니다.
2. Queue의 구성
2.1) 생성자
stack의 생성자와 비슷합니다. 보통은 아무 원소를 가지고 있지 않은 텅 빈 큐를 많이 사용합니다.
queue<int> q;와 같은 형태.
deque와 list를 받아서 생성할 수 도 있습니다. 그런데 이 부분은 잘 쓰이지 않기 때문에 보고 싶은 분들은 C++ reference를 참고하시기 바랍니다. (링크)
http://www.cplusplus.com/reference/queue/queue/queue/
2.2) 반복자
없습니다.
원소 하나하나 접근할 수 없습니다. front, back을 사용하여 양 끝으로만 접근해야 합니다.
2.3) 매서드
Queue에서 가장 많이 사용하는 push와 pop, 그리고 front를 살펴보겠습니다. front를 보니 back도 보겠습니다.
front, back은 상수 시간에 원소를 가지고 올 수 있습니다. O(1).
push와 pop은 내부적으로 push_back, pop_back을 사용하기 때문에 Default인 deque의 push_back, pop_back의 시간 복잡도를 따릅니다.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int>q;
q.push(1);
q.push(3);
q.push(5);
q.push(7);
q.push(2);
q.push(4);
cout << "--------------- 초기 --------------" << '\n';
cout << "q.front() : " <<q.front() << " q.back() : " << q.back() << "\n\n";
cout << "--------------- pop 후 --------------" << '\n';
q.pop();
cout << "q.front() : " << q.front() << " q.back() : " << q.back() << "\n\n";
return 0;
}
실행결과는 위 사진과 같습니다. Queue의 구조를 보면,
위의 사진처럼 되어있습니다. 따라서 front는 1이라는 반환 합니다. 그리고 참조 형태로도 반환할 수 있습니다.
이 상태에서 pop을 하면 front에 있는 원소가 삭제됩니다. 따라서 front는 3을 가리키게 되고 한 번 더 front, back을 출력하면
back은 그대로, front는 1에서 3으로 변경된 것을 볼 수 있습니다.
다음은 .empty()메서드입니다. size가 0이면 True, 아니면 False를 반환합니다.
#include <iostream>
#include <queue>
using namespace std;
int main()
{
queue<int>q;
q.push(1);
q.push(3);
cout << "--------------- 초기 --------------" << '\n';
cout << "q.size() : " <<q.size() << '\n';
cout << "q.empty() : ";
if (q.empty())
cout << "True\n\n";
else
cout << "False\n\n";
cout << "--------------- pop 후 --------------" << '\n';
q.pop();
cout << "q.size() : " << q.size() << '\n';
cout << "q.empty() : ";
if (q.empty())
cout << "True\n\n";
else
cout << "False\n\n";
cout << "--------------- pop 후 --------------" << '\n';
q.pop();
cout << "q.size() : " << q.size() << '\n';
cout << "q.empty() : ";
if (q.empty())
cout << "True\n\n";
else
cout << "False\n\n";
return 0;
}
참고로, 쓰던 Queue를 초기화하고 싶을 때 queue가 empty 할 때까지 pop 하는 것보다 저는 개인적으로 q = queue<int>()를 많이 사용합니다. Vector에는 clear라는 메서드가 있습니다.
이 정도의 메서드만 알아도 Queue를 사용하는 데는 전혀 지장이 없습니다. swap, emplace와 같은 추가적인 것은 필요할 때 찾아서 사용하시면 될 것 같습니다.
다음은 우선순위 큐에 대해서 알아보도록 하겠습니다.
3. Priority Queue의 특성
우선순위 큐는 할 이야기가 조금 많습니다.
정렬을 할 때 사용되기 때문에 중요합니다. 물론 기본적인 '정렬'만 해내야 한다면 algorithm헤더에 있는 sort함수를 사용해서 해도 되는데, 조금 한번 꼬아서 내는 응용문제 같은 경우라면 우선순위 큐를 사용해야 할 수 있기 때문입니다.
우선순위 큐는 힙을 사용합니다. 그래서 살행 도중에 디버깅을 해보면 첫 번째 원소만 정렬되어 있고(최대 or 최소), 나머지 원소는 느슨한 정렬 상태를 유지합니다. 단순히 부모보다 작으면 왼쪽 크면 오른쪽의 순서로 말이죠.
그래서 삽입할 때 O(log n)(밑은 2입니다.)의 시간 복잡도를 갖게 됩니다.
그래서 n개의 원소를 정렬할 때에는 O(nlogn)의 시간 복잡도를 갖게 되는 것입니다.
한 번 사용해보고, 또 응용문제 해결에 가장 중요한 정렬하는 방법, 정렬 기준에 대해서 알아보도록 하겠습니다.
3.1) 생성자
우선순위 큐는 기본 큐와 생성자가 비슷한 듯 안 비슷하기 때문에 한번 살펴보겠습니다.
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
int main()
{
int arr[] = { 10,30,20,5 };
priority_queue <int> pq1; //텅 빈 생성자
priority_queue <int> pq2(arr, arr + 4); //배열의 범위로 초기화
cout << "pq2 : ";
while (!pq2.empty()){
cout << pq2.top()<<" ";
pq2.pop();
}
cout << "\n\n";
priority_queue <int, vector<int>, greater<int>> pq3(arr, arr + 4);
cout << "pq3 : ";
while (!pq3.empty()) {
cout << pq3.top() << " ";
pq3.pop();
}
cout << "\n\n";
return 0;
}
priority_queue <int> pq2를 선언하면 Default로 컨테이너는 vector와 정렬 순서로 less<int>를 사용합니다. 여기서 less나 greater같은 비교자 매서드는 #include <functional>을 전처리해야 사용할 수 있습니다.
위의 코드와 같이 우선순위 큐의 기본 정렬방법은 내림차순입니다. 그런데 밑의 pq3와 같이 greater를 사용해주면 오름차순으로 정렬할 수 있습니다.
또, greater를 사용하지 않고
#include <iostream>
#include <queue>
#include <functional>
using namespace std;
class comp {
public:
bool operator()(const int &lhs, const int& rhs) const{
return lhs > rhs;
}
};
int main()
{
int arr[] = { 10,30,20,5 };
priority_queue <int> pq1; //텅 빈 생성자
priority_queue <int> pq2(arr, arr + 4); //배열의 범위로 초기화
cout << "pq2 : ";
while (!pq2.empty()){
cout << pq2.top()<<" ";
pq2.pop();
}
cout << "\n\n";
priority_queue <int, vector<int>, comp> pq3(arr, arr + 4);
cout << "pq3 : ";
while (!pq3.empty()) {
cout << pq3.top() << " ";
pq3.pop();
}
cout << "\n\n";
return 0;
}다음과 같이 비교하는 클래스를 만들어도 된다. 보통 구조체로 하는 편이긴 합니다.
class는 public: 써주는 거 잊지 맙시다.
bool operator()(const int &lhs, const int& rhs) const {
return lhs > rhs;
}
이 함수가 비교자가 됩니다. 이런 형태로 오름차순을 구현해줄 수 있습니다.
구조체인 경우 입니다.
bool operator<(const int &other) const{
return lhs < rhs;
}
구조체에서는 < 연산자가 없다면 컴파일러가 operator<함수를 구현하라고 오류를 뱉어줍니다.
3.2) 반복자
없습니다.
3.3) 매서드
queue의 front가 priority_queue의 top과 동일한 역할을 한다는 점.
그 외는 queue와 동일하게 동작합니다.
시간 복잡도의 경우 삽입 삭제가 로그 시간을 갖습니다.
3.4) 정렬 순서
한 개의 값을 가질 때는 less와 greater를 가지고 정렬할 수 있었습니다.
그런데 여러 개 값을 가질 때는 어떻게 정렬해야 하는지 알아보도록 하겠습니다.
less의 구현을 보면,
bool operator() (const T& x, const T& y) const {return x<y;}
greater의 구현을 보면
bool operator() (const T& x, const T& y) const {return x>y;}
즉, less로 예를 들어보면 if x is less than y, return true. 라고 할 수 있겠습니다.
코드를 보면서 비교 함수의 원리에 대해서 알아보도록 하겠습니다.
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#include <functional>
using namespace std;
class comp {
public:
bool operator()(const int &lhs, const int& rhs) const {
return lhs > rhs;
}
};
bool cmp(const int &lhs, const int& rhs) {
return lhs < rhs;
}
int main()
{
int arr[] = { 10,30,20,5 };
priority_queue <int> pq1; //텅 빈 생성자
priority_queue <int> pq2(arr, arr + 4); //배열의 범위로 초기화
cout << "pq2 : ";
while (!pq2.empty()){
cout << pq2.top()<<" ";
pq2.pop();
}
cout << "\n\n";
priority_queue <int, vector<int>, comp> pq3(arr, arr + 4);
cout << "pq3 : ";
while (!pq3.empty()) {
cout << pq3.top() << " ";
pq3.pop();
}
cout << "\n\n";
vector<int> v1(arr, arr + 4);
sort(v1.begin(), v1.end(), cmp);
cout << "v1 :";
for (int item : v1)
cout << item << " ";
return 0;
}
여기서 주의하면서 보셔야 할 부분은 vector를 정렬하는 데 사용한 비교 함수와 우선순위 큐를 오름차순으로 하기 위해 사용자 정의 비교 클래스를 사용한 부분입니다.
// Prioriry queue 비교자
class comp {
public:
bool operator()(const int &lhs, const int& rhs) const {
return lhs > rhs;
}
};
// Vector 비교자
bool cmp(const int &lhs, const int& rhs) {
return lhs < rhs;
}
제가 C++공부했을 때로 보면, 비교 함수에서 true가 반환되면 lhs가 rhs보다 정렬순서로 봤을 때 앞에 있는 것이 맞다.라는 것을 의미한다고 알고 있습니다.
그래서 Vector의 비교자처럼 오름차순으로 하려고 한다면, lhs가 rhs보다 작으면 앞에 있는 것이 맞는 말이니 저런 방식으로 작성하면 됩니다. 반대로 내림차순을 원할 때 lhs > rhs인 경우로 한다면 lhs(100) > rhs(1)에는 true를 반환하게 되므로 큰 숫자가 앞에 오게 됩니다.
그런데 operator()를 정의할 때는 뭔가 규칙이 반대가 됩니다.
set의 경우에도 comp클래스를 넣으면 내림차순으로 됩니다.
뭔가 우선순위 큐가 반대로 구현되어있거나 그만한 이유가 있을 것 같으니 이건 외우는 수밖에 없다고 생각합니다.. ㅠ
★★★★이 부분을 숙지하고 이번엔 자료가 여러 개인 경우 예를 들면 구조체라거나 Pair<int,int> 같은 변수라던가 그럴 때 정렬하는 방법을 살펴보도록 하겠습니다.
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
class comp {
public:
bool operator()(const pair<int,int> &lhs, const pair<int, int>& rhs) const {
return lhs.first > rhs.first;
}
};
int main()
{
pair<int, int> arr[]
= { {1,2},
{4,2},
{1,5},
{6,4},
{2,9},
{3,5},
{5,3},
{8,6},
{2,8},
{1,1},
{9,2},
{0,5},
{2,7},
};
priority_queue<pair<int, int>,vector<pair<int,int>>,comp> pq(arr,arr+13);
while (!pq.empty()){
cout << "(" << pq.top().first << "," << pq.top().second << ")\n";
pq.pop();
}
return 0;
}
예상했던 대로, 비교자에서 첫 번째 원소만 고려하게 했습니다. 그래서 두 번째 원소는 어떻게 되든 말든 신경을 안 쓰는 순서대로 된 거죠.
첫 번째 원소를 기준으로 오름차순으로 정렬한 것입니다.
이번에는 두 번째 원소도 함께 정렬을 해봅시다. 첫 번째 원소는 오름차순으로 하되 두 번째 원소는 그 첫 번째 오름차순 된 것에서 내림차순으로 정렬해보도록 하겠습니다.
비교자 부분에서,
class comp {
public:
bool operator()(const pair<int,int> &lhs, const pair<int, int>& rhs) const {
if (lhs.first > rhs.first)
return true; //return lhs.first > rhs.first 해도 OK
else if (lhs.first == rhs.first)
return lhs.second < rhs.second;
else
return false; //return lhs.first <= rhs.first 해도 OK
}
};위의 코드와 같이 수정해줍시다.
if문을 통해서 첫 번째 원소 기준으로 작성해줍시다. 우선순위를 첫 번째 원소에 뒀기 때문에 조건은 첫 번째 원소 기준으로 이루어져야 합니다.
만약 첫 번째 원소가 같다면 내림차순으로 정렬하도록 bool값을 반환해주었습니다.
이에 따라 실행결과는
위의 사진과 같이 나옵니다.
pair가 아니어도 괜찮습니다. 구조체, 클래스여도 괜찮습니다. 비교 함수의 매개변수에 자료형만 알맞게 맞춰주시면 됩니다. 다음 개발할 때에는 템플릿화 시켜서 사용할 수 있을 것 같습니다. :)
마치며...
Queue와 Priority queue는 문제를 풀면서 정말 많이 사용한 자료구조입니다.
이 부분은 확실히 하고 넘어가는 게 좋을 것 같습니다.
특별한 점은 우선순위 큐 비교자가 다른 컨테이너들이랑 조금 다르게 작동한다는 점입니다.
일반적인 경우에 true를 반환하는 의미는 lhs가 rhs보다 앞에 있음이 옳을 때입니다.
지적, 댓글 언제나 환영입니다~ :)
'개발 > C++' 카테고리의 다른 글
| [C++ / 2인용] 테트리스 개발 ( Class 부분 ) (0) | 2020.08.27 |
|---|---|
| [C++ / STL] Set 분석 (2) | 2020.08.19 |
| [C++/Library] String 분석 (0) | 2020.08.09 |
| [C++ / STL] Stack 분석 (0) | 2020.07.31 |
| [C++ / STL] vector 분석 (0) | 2020.07.31 |