C++ STL 기본 컨테이너 구조(스택,큐,사전,우선순위 큐,집합,벡터) -2

저는 평범한 대학생이므로 내용 중 틀린 부분이 있을 수 있습니다. 알려주시면 확인 후 바로 수정하겠습니다.

 

-이번에는 우선순위 큐와 집합에 대해서 알아 보겠습니다.

 

• 4.우선순위 큐 (heap)

-우선 순위 큐는 스케줄이나 달력 같은 것을 관리하기 위한 용도로 사용됩니다. 예를 들어 공항이나 주차장에서 어떤 것이 다음 순서가 될지를 결정하는 것과 같이 시간에 맟춰서 계획을 짜야 하는 경우에는 항상 우선 순위 큐를 사용한다고 볼 수 있습니다.

 

-우선 순위 큐를 구현하는 가장 대표적인 방법은 이진 힙을 이용하는 방법이며, 이진 힙은 하향식이든 상향식이든 상관없이 효율적 관리가 가능합니다. 힙은 효율적이긴 하지만 시간이 촉박한 경우에는 제대로 만들기 까다로우므로 삽입 작업을 많이 하지 않는 경우에는 정렬된 배열을 사용하는 방법이 관리하기 더쉽습니다.

 

-연산

 

push(x)	x를 우선순위 큐에 추가
pop(x)	top에 있는 원소를 삭제
top()	우선순위 큐의 top에 있는 원소를 반환
size()	우선순위 큐의 크기를 반환
empty()	우선순위 큐가 비었는지를 검사

 

추가적인 연산은 아래의 사이트에서 확인하시면 됩니다.

http://www.cplusplus.com/reference/queue/priority_queue/?kw=priority_queue

 

-c++ 에서는 default로 max heap이 생성되도록 되있습니다.(내부 구조 vector, less(오름차순)) 따라서 priority_queue<int> pq1; 라고 생성 해주시면 바로 max heap 이 생성되어 집니다.

min heap 같은경우엔 priority_queue<int, vector<int> , greater<int> > pq2; 이렇게 생성해주어야 합니다.

 

우선순위 큐는 top에 항상  min이나 max값을 위치시키는데 log N의 시간밖에 걸리지 않는 마법같은 존재이므로 여러가지 알고리즘 문제 해결에 굉장히 유용하게 사용되니 잘 익혀두셔야 합니다.

 

다음은 테스트 코드입니다.

 

 #include <iostream>
#include <queue>

using namespace std;

int main(void) {
	priority_queue<int> pq1; //max heap 생성 
	
	priority_queue<int, vector<int> , greater<int> > pq2; //min heap 생성 
	
	cout<<pq1.empty()<<endl; //우선순위 큐가 비어있는지 검사 
	
	pq1.push(20);
	pq1.push(30);
	pq1.push(40);
	
	cout<<pq1.top() <<endl; //top 값 반환 
	
	pq1.push(50); 
	
	cout<<pq1.top() <<endl;
	
	pq1.pop(); //top에 있는 값 삭제 
	
	cout<<pq1.top() <<endl;
	cout<<pq1.size()<<endl; //사이즈 반환 
	
	pq2.push(20); 
	pq2.push(30);
	pq2.push(40);
	
	cout<<pq2.top() <<endl; //가장 작은 값인 20 반환 (top)
	
	pq2.push(10);
	
	cout<<pq2.top() <<endl; //가장 작은 값인 10 반환 (top) 
	
	pq2.pop();
	
	cout<<pq2.top() <<endl; //가장 작은 값인 20 반환 (top)
	cout<<pq2.size()<<endl;
	
	return 0;
}

 

 

 

• 5.집합(set)

-집합은 주어진 전체집합 U로부터 원소들을 뽑아서 정렬하지 않은 상태로 모아놓은 것입니다.

-전체집합이 아주 크거나 무한집합이라면 사전을 써서 부분집합을 표현하는 수밖에 없습니다. 정렬된 사전을 사용하면 합집합 및 교집합을 구하기가 아주 쉽습니다. (정렬된 사전 두개를 합치기만 하면 됨) -> 합쳐진 목록에 한번 이상 등장하면 합집합의 원소이고, 두번 등장하면 교집합의 원소입니다.

 

-전체집합이 작고 내용이 바뀌지 않는 집합이면 비트 벡터를 이용하는 것도 좋습니다.

 

-set 같은 경우 default 로 less(오름차순) 이 설정되어 있습니다.

 정렬 조건은 변경하고 싶으실 때는 set<int, greater<int>> s2; 이런식으로 우선순위 큐의 min heap 생성과 유사하게 생성할 수 있습니다.

 

-연산

 

insert(x)	집합에 x원소 추가
erase(x)	집합에서 x원소 제거
find(x)	x에 해당하는 iterator 를 반환
count(x)	집합내에 x의 개수를 반환,set은 중복을 허용하지 않으므로 0또는 1반환
clear()	집합내에 있는 모든 원소를 제거합니다.
begin(),end()	각각 시작,끝 iterator 를 반환

 

추가적인 연산은 아래의 사이트에서 확인하시면 됩니다.

http://www.cplusplus.com/reference/set/set/?kw=set

 

다음은 테스트 코드입니다.

 

 

#include <iostream>
#include <set>

using namespace std; 

int main(void) {
	set<int> s1; //집합 생성 
	set<int, greater<int>> s2; //내림차순으로 정렬되는 집합 생성 
	
	s1.insert(3);
	s1.insert(1);
	s1.insert(2);
	s1.insert(4);
	
	cout<<s1.count(3)<<endl; //3의 개수 반환 
	s1.erase(1); //1 제거 
	
	for(auto it = s1.begin(); it != s1.end(); it++) //집합을 순회하며 출력 (오름차순) 
		cout<<*it<<endl;
	
	s2.insert(4);
	s2.insert(5);
	s2.insert(3);
	s2.insert(2);
	
	for(auto it = s2.begin(); it != s2.end(); it++) //집합을 순회하며 출력 (내림차순) 
		cout<<*it<<endl;

	s2.clear();
	cout<<s2.empty()<<endl; 
	
	return 0;
}

 

 

우선순위 큐를 설명하는중 vector에 대해서 나왔으므로 또 굉장히 자주 사용되는 컨테이너중 하나이므로 한번 살펴보도록 하겠습니다.

• 6.벡터(vector)

-벡터는 동적 배열로서 삽입이나 제거시 스스로 자신의 크기를 조절을 해줍니다. (이때문에 엄청 편리합니다.)

 

-연산

push_back(x)	x를 vector의 끝에 삽입합니다.
pop_back()	vector의 끝부분 원소를 제거합니다.
front()	vector의 첫번째 원소를 반환합니다.
back()	vector의 끝원소를 반환합니다.
size(), resize(n)	size()는 크기를 반환하고 resize는 n으로 vector의 사이즈를 변경합니다.
begin(),end()	시작,끝 부분의 iterator를 반환합니다.
empty(),clear()	비어있는지를 검사,  clear는 모든 원소를 제거합니다.
at(idx), [idx]	각각 idx번째 원소를 참조합니다.(at은 범위를 점검,속도가 느림 []는 그반대입니다.)

 

추가적인 연산은 아래의 사이트에서 확인하시면 됩니다.

http://www.cplusplus.com/reference/vector/vector/

 

아래는 테스트 코드입니다.

#include <iostream>
#include <vector>

using namespace std; 

int main(void) {
	vector<int> s1; //벡터 생성 
	
	s1.push_back(1); 
	s1.push_back(2);
	s1.push_back(3);
	s1.push_back(4);
	
	cout<<s1.front()<<endl; //첫번째 원소 출력 
	cout<<s1.back()<<endl; //끝부분 원소 출력 
	
	s1.pop_back(); //끝부분 원소 제거 
	
	cout<<s1.back()<<endl;  
	
	cout<<"두번째 인덱스:"<<s1.at(1)<<endl; //두번째 원소  출력 
	cout<<"두번째 인덱스:"<<s1[1]<<endl; //두번째 원소 출력 
	
	cout<<"사이즈:" <<s1.size()<<endl; //사이즈 반환 
	 
	s1.resize(5); //사이즈 5로 조정 
	
	cout<<"사이즈:" <<s1.size()<<endl;
	
	for(auto it = s1.begin(); it!=s1.end(); it++) //순회하며 출력 
		cout<<*it<<endl;
		
	s1.clear(); //모든 원소 제거 
	cout<<s1.empty()<<endl; //비어있는지 검사 
	return 0;
}

 

 

이상으로 6가지 컨테이너 구조에 대해서 알아보았습니다.