우선순위 큐, 순열, k값 찾기

1. 우선순위 큐

---

1 - 1. 기본 개념

• 우선순위를 가지고 정렬 되어 있는 큐
• 내부적으로 Heap 자료구조를 사용한다.
• 삽입 삭제는 "항상" O(logN), 우선순위 높은 원소 검색은 O(1)

 

1 - 2. 사용하기

• 기본적으로 가장 큰 원소가 먼저 나오는 최대 힙으로 구현 되어 있다.
• 최소힙을 위해서는 아래와 같이 구현하면 된다.
  • 첫번째 인자는 자료형
  • 두번째 인자는 구현체
  • 세번째 인자는 비교연산자(비교 함수)

priority_queue<int, vector<int>, greater<int>> minPQ;

• 새롭게 만든 타입을 사용하는 경우의 예시

#include <iostream>
#include <string>
#include <queue>
using namespace std;

class Student
{
public:
	string name;
	int age;
};

struct cmp
{
	bool operator()(Student& a, Student& b)
	{
		return a.age < b.age;
	}
};
int main()
{
	priority_queue<Student, vector<Student>, cmp>pq;

	Student s1("A", 19);
	Student s2("B", 22);
	Student s3("Z", 30);
	Student s4("C", 15);

	pq.push(s1);
	pq.push(s2);
	pq.push(s3);
	pq.push(s4);

	while (!pq.empty())
	{
		cout << pq.top().name << " " << pq.top().age << " ";
		cout << "\n";
		pq.pop();
	}
}

 

 

1 - 3. 주의 사항

• 주의 사항 1) 벡터와는 다른 정렬 기준
  
  • 기본적으로 vector에서 비교함수를 return a.age < b.age 로 만들면, 오름차순 정렬이 된다.
  • 그러나 우선순위큐는 "내림차순"이기 때문에, 비교연산자에서 a.age < b.age를 통해서 나온 결과물이 vector와 반대인 내림차순으로 나오게 된다.
  • 아래 코드 참고

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

class Student
{
public:
	string name;
	int age;
};

struct cmp
{
	bool operator()(Student& a, Student& b)
	{
		return a.age < b.age;
	}
};

bool cmp2(Student& a, Student& b)
{
	return a.age < b.age;
}

int main()
{
	vector<Student> vec;

	priority_queue<Student, vector<Student>, cmp>pq;

	vec.push_back({ "A", 19 });
	vec.push_back({ "B", 22 });
	vec.push_back({ "Z", 30 });
	vec.push_back({ "C", 15 });

	sort(vec.begin(), vec.end(), cmp2);

	for (const auto v : vec)
		cout << v.name << " " << v.age << "\n";
	cout << "\n";

	//
	Student s1("A", 19);
	Student s2("B", 22);
	Student s3("Z", 30);
	Student s4("C", 15);

	pq.push(s1);
	pq.push(s2);
	pq.push(s3);
	pq.push(s4);

	while (!pq.empty())
	{
		cout << pq.top().name << " " << pq.top().age << " ";
		cout << "\n";
		pq.pop();
	}
}

• 위 코드의 출력 결과물
  • 위) 벡터의 정렬
  • 아래) 우선순위 큐정렬

• 주의 사항 2) 같은 값이 있는 경우
  • Student의 age가 다 같은 경우 위의 코드를 실행하면, name의 우선순위와는 관련없는 결과가 나온다.
  • 그렇기 때문에, age가 같은 경우 name으로 정렬해주는 등의 처리가 있으면 좋을 것이다.

#include <iostream>
#include <string>
#include <queue>
#include <algorithm>
using namespace std;

class Student
{
public:
	string name;
	int age;
};

struct cmp
{
	bool operator()(Student& a, Student& b)
	{
		return a.age < b.age;
	}
};

int main()
{
	vector<Student> vec;

	priority_queue<Student, vector<Student>, cmp>pq;
    
	Student s1("A", 19);
	Student s2("B", 19);
	Student s3("C", 19);
	Student s4("D", 19);
	Student s5("Z", 19);
	Student s6("F", 19);

	pq.push(s1);
	pq.push(s2);
	pq.push(s3);
	pq.push(s4);
	pq.push(s5);
	pq.push(s6);

	while (!pq.empty())
	{
		cout << pq.top().name << " " << pq.top().age << " ";
		cout << "\n";
		pq.pop();
	}
}

 

 

2.  순열

---

주어진 범위 안에서 순열을 찾아주는 아래와 같은 함수가 있다.

algorithm 헤더를 include 한 다음 사용한다.

2 -1. next_permutation

• 주어진 범위를 사전순으로 "다음 순열"로 바꿔준다.
  • 다음 순열이라는 것이 사전 순서로 현재 순열의 다음 순열을 뜻한다.
• 간단한 예제

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 1,2,3 };
	for (int x : vec)
		cout << x << " "; //1 2 3 
	cout << "\n";

	next_permutation(vec.begin(), vec.end());
	for (int x : vec)
		cout << x << " "; //1 3 2
}

 

2 - 2. prev_permutation

• 주어진 범위를 사전순으로 "이전 순열"로 바꿔준다.
• 간단한 예제

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 1,2,3 };
	for (int x : vec)
		cout << x << " "; //1 2 3 
	cout << "\n";

	prev_permutation(vec.begin(), vec.end());
	for (int x : vec)
		cout << x << " "; //3 2 1
}

 

2 - 3. 추가 예제

• 1,2,3으로 만들수 있는 모든 순열을 출력하는 예제이다.
  • 만약 vec을 {1,3,2} 로 만들면 1,3,2 이후의 순열 값들이 나오게 된다.
  • 만약 vec을  {3,2,1}로 만들면 3,2,1 만 출력되게 된다. 

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int main()
{
	vector<int> vec = { 1,2,3 };
	do
	{
		for (int x : vec)
			cout << x << " ";
		cout << "\n";
	} while (next_permutation(vec.begin(), vec.end()));
}

 

 

3. k값 찾기 - nth_element

---

nth_element 함수는 pivot을 기반으로 사용하는 위치만 정렬하여, 원하는 위치의 값을 찾을 수 있는 함수이다.

• 함수 기본 시그니처

template<class RandomIt>
void nth_element(RandomIt first, RandomIt nth, RandomIt last);

• 파라메터
  • first: 정렬 시작하는 시작점
  • last: 정렬 끝나는 끝점
  • nth: 정렬을 하게되는 기준점
• 결과
  • nth 로 지정한 위치에 있는 숫자까지 정렬을 해서, nth 번째 자리에 nth 번째로 작은 원소가 있고
  • nth자리 앞에는 정렬된 수들이, 이후로는 정렬되지 않은 수들이 존재
• 예제

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main()
{
	vector<int> vec = { 5, 6, 4, 3, 2, 6, 7, 9, 3 };
	nth_element(vec.begin(), vec.begin() + vec.size() / 2, vec.end());
	cout << "중간값: " << vec[vec.size() / 2] << "\n"; // 5

	nth_element(vec.begin(), vec.begin() + 1, vec.end());
	cout << "두번째로 작은 원소: " << vec[1] << "\n"; // 3

	nth_element(vec.begin(), vec.begin() + 1, vec.end(), greater<int>());
	cout << "두번째로 큰 원소: " << vec[1] << "\n"; // 7
}