Algorithm/C++
[21.08.27]Priority_queue / Heap Sort / Dijkstra알고리즘
문래동까마귀
2021. 8. 27. 10:32
- STL 사용하지않고 구현하기
#include<iostream>
using namespace std;
int heap[30];
int index;
void push(int value)
{
// 1 번 인덱스 부터
heap[++index] = value;
// 부모 그리고 넘어온 값
int p, now;
now = index;
while (1)
{
// 부모 인덱스 확인
p = now / 2;
// 1번 인덱스만 체워짐
if (now == 1)break;
// 부모랑 들어온 값이랑 비교후 스왑
if (heap[p] > heap[now])swap(heap[p], heap[now]);
else break;
// 부모를 기점으로 더 위(부모의 부모랑 비교)
now = p;
}
}
int top()
{
return heap[1];
}
void pop()
{
// 맨 끝을 맨 위로 올리고
heap[1] = heap[index];
//맨 끝값을 지우고
heap[index] = 0;
index--;
int p, son, son2;
p = 1;
while (1) {
son = p * 2; // 왼쪽자식
son2 = son + 1; // 오른쪽 자식
// 오른쪽에 자식이 있고 자식들 비교해서 작은 자식을 = son
if (son2 <= index && heap[son] > heap[son2])son = son2;
// 배열에 마지막만 남거나 부모가 자식보다 작으면 break
if (son > index || heap[p] < heap[son])break;
else swap(heap[p], heap[son]);
// 트리의 밑을 보기 (자식이 다시 부모가 되어서 체크)
p = son;
}
}
int main()
{
push(9);
push(3);
push(5);
push(2);
push(8);
push(4);
push(1);
for (int x = 0; x < 7; x++)
{
cout << top() << " ";
pop();
}
return 0;
}
- STL 사용하기
#include<iostream>
#include<queue>
using namespace std;
priority_queue<int,vector<int>,greater<int>>q; //오름차순
//priority_queue<int,vector<int>,less<int>>q; //max heap(내림차순)일경우 생략가능
int main() {
q.push(4);
q.push(14);
q.push(44);
q.push(64);
q.push(43);
q.push(24);
int len = q.size();
for (int i = 0; i < len; i++) {
cout << q.top() << " ";
q.pop();
}
return 0;
}
- operator 사용하기(우선순위 - 숫자 오름차순, 문자오름차순)
#include<iostream>
#include<queue>
using namespace std;
struct node {
int num;
char ch;
};
node vect[7] = {
{3,'b'},
{1,'k'},
{5,'b'},
{13,'a'},
{1,'c'},
{3,'a'},
{1,'d'}
};
priority_queue<node>q;
// 첫번째 인자값의 우선순위가 더 낮다면 true를 반환
// sort랑 반대 주의!
bool operator<(node back, node front) {
if (front.num < back.num) return true;
if (front.num > back.num) return false;
return front.ch < back.ch;
}
int main() {
for (int x = 0; x < 7; x++) {
q.push(vect[x]);
}
for (int x = 0; x < 7; x++) {
cout << q.top().num << " " << q.top().ch << endl;
q.pop();
}
return 0;
}
- 2차원배열의 값 큰것부터 위치 출력하기
#include<iostream>
#include<queue>
using namespace std;
struct node {
int y, x;
int num;
};
int map[3][3] = {
4,7,3,
1,94,5,
6,2,8
};
priority_queue<node>q;
bool operator<(node back, node front) {
return front.num < back.num;
}
int main() {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
q.push({ i,j,map[i][j] });
}
}
for (int i = 0; i < 9; i++) {
cout << q.top().y << " " << q.top().x << endl;
q.pop();
}
return 0;
}
- *2, *3, *5 로 구현가능한 숫자중 n번째 수 찾기
#include<iostream>
#include<queue>
#include<vector>
#include<string>
using namespace std;
priority_queue<int, vector<int>, greater<int>>q;
vector<int>vect;
int main() {
int n;
cin >> n;
q.push(1);
int now;
int before = 0;
for (int x = 0; x < n; x++) {
//중복제거
while (1) {
now = q.top();
q.pop();
if (now != before)break;
}
before = now;
vect.push_back(now);
q.push(now * 2);
q.push(now * 3);
q.push(now * 5);
}
cout << vect[n - 1];
return 0;
}
Heap은 Data를 이진트리 형태로 저장해두고, 우선순위가 높은 값을 빠르게 찾아주는 자료구조 입니다.
다익스트라 알고리즘 - 경로가 양수로만 정해져있음( 갈수없는곳은 큰값으로 채움)
#include<iostream> // 다익스트라 n2
using namespace std;
char name[6] = "ABCDE";
const int m = 999;
int map[5][5] = {
m,3,m,9,5,
m,m,7,m,1,
m,m,m,1,m,
m,m,m,m,m,
m,m,1,m,m,
};
int result[5] = {
m,3,m,9,5,
};
int used[5] = { 1 };
int check()
{
int Min = 21e8;
int Minindex = 0;
for (int x = 0; x < 5; x++)
{
if (used[x]==0 && result[x] < Min) {
Min = result[x];
Minindex = x;
}
}
return Minindex;
}
void daijk()
{
for (int y = 0; y < 4; y++)
{
int via = check(); // 경유지 선택
used[via] = 1;
for (int x = 0; x < 5; x++)
{
int baro = result[x];
int kyoung = result[via] + map[via][x];
if (baro > kyoung)result[x] = kyoung;
}
}
}
int main()
{
daijk();
char ends;
cin >> ends;
for (int x = 0; x < 5; x++)
{
if (name[x] == ends)
{
cout << result[x];
break;
}
}
return 0;
}
#include<iostream> // 다익스트라 nlogn
#include<queue>
#include<vector>
using namespace std;
char name[6] = "ABCDE";
struct node {
int n; // 인덱스
int price;
};
vector<vector<node>>vect(5);
priority_queue<node>q;
int result[5] = { 999,999,999,999,999 };
int used[5];
bool operator<(node back, node front) // 우선순위 조건
{
return front.price < back.price;
}
int main()
{
// 인접 리스트
vect[0].push_back({ 1,3 });
vect[0].push_back({ 3,9 });
vect[0].push_back({ 4,5 });
vect[1].push_back({ 2,7 });
vect[1].push_back({ 4,1 });
vect[2].push_back({ 3,1 });
vect[4].push_back({ 2,1 });
q.push({ 0,0 });
while (!q.empty())
{
node via = q.top();
q.pop();
if (used[via.n] == 1)continue;
used[via.n] = 1;
// result vs 경유지 거쳐서 가는 비용 비교후 result 갱신
for (int x = 0; x < vect[via.n].size(); x++)
{
node target = vect[via.n][x];
if (result[target.n] > via.price + target.price) {
result[target.n] = via.price + target.price;
q.push({ target.n,result[target.n] });
}
}
}
return 0;
}