https://www.acmicpc.net/problem/7662

#include <bits/stdc++.h>
using namespace std;

struct Node_max {
	int idx, value;
	bool operator<(const Node_max& b) const {
		return value < b.value;
	}
};

struct Node_min {
	int idx, value;
	bool operator<(const Node_min &b) const {
		return value > b.value;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int t;
	cin >> t;
	for (int T = 0; T < t; T++) {
		int k;
		cin >> k;

		priority_queue<Node_max> max_q;
		priority_queue<Node_min> min_q;


		vector<bool> ch(k + 1, 0);
		int idx = 1;
		int q_size = 0;

		for (int i = 0; i < k; i++) {
			char c;
			int val;

			cin >> c >> val;

			if (c == 'I') {

				max_q.push({ idx,val });
				min_q.push({ idx,val });
				idx++;
			}
			else {
				if (val == -1) {
					
					while (!min_q.empty() && ch[min_q.top().idx]) {
						min_q.pop();
					}

					if (!min_q.empty()) {
						ch[min_q.top().idx] = 1;
						min_q.pop();
					}

				}
				else {
					while (!max_q.empty() && ch[max_q.top().idx]) {
						max_q.pop();
					}

					if (!max_q.empty()) {
						ch[max_q.top().idx] = 1;
						max_q.pop();
					}



				}
			}


		}

		int ans = 0;
		for (int i = 1; i < idx; i++) {
			if (ch[i] == 0) {
				ans++;
			}
		}
		if (ans == 0) {
			cout << "EMPTY\n";
		}
		else {
			
			while (!min_q.empty() && ch[min_q.top().idx]) {
				min_q.pop();
			}


			while (!max_q.empty() && ch[max_q.top().idx]) {
				max_q.pop();
			}


			cout << max_q.top().value << ' ' << min_q.top().value << '\n';



		}
	}

	return 0;
}

https://www.acmicpc.net/problem/16139

#include <bits/stdc++.h>
using namespace std;


int psum[200001][26];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	string s;
	cin >> s;
	s = "_" + s;

	for (int i = 1; i < s.length(); i++) {

		for (int j = 0; j < 26; j++) {
			psum[i][j] = psum[i - 1][j];
		}
		psum[i][s[i]-'a']++;
	}


	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		char c;
		int l, r;
		cin >> c >> l >> r;
		cout << psum[r+1][c - 'a'] - psum[l][c - 'a'] <<'\n';
	}



	return 0;
}

https://www.acmicpc.net/problem/10986

#include <bits/stdc++.h>
using namespace std;

int n, m;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> m;
	long long ans = 0;

	int tmp = 0;

	vector<long long> map(m, 0);
	for (int i = 1; i <= n; i++) {
		int a;
		cin >> a;
		tmp = (tmp + a)%m;

		map[tmp]++;
		if (tmp == 0) {
			ans++;
		}
	}

	for (int i = 0; i < m; i++) {
		ans += map[i] * (map[i] - 1) / 2;
	}

	cout << ans << '\n';


	return 0;
}

https://www.acmicpc.net/problem/16236

#include <bits/stdc++.h>
using namespace std;

int n, arr[21][21];
struct Shark {
	int x, y, size=2, cnt =0;
	void sizeUp() {
		if (cnt >= size) {
			cnt -= size;
			size++;
		}
	}
};

struct Node {
	int x, y , dist;

	bool operator<(const Node& b) const {
		if (dist == b.dist) {
			if (x == b.x) {
				return y > b.y;
			}
			return x > b.x;
		}
		else return dist > b.dist;
	}
};

int dx[4] = { 1,0,-1,0 };
int dy[4] = { 0,1,0,-1 };
bool ch[21][21];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	Shark sk;
	cin >> n;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cin >> arr[i][j];
			if (arr[i][j] == 9) {
				arr[i][j] = 0;
				sk.x = i;
				sk.y = j;
			}
		}
	}

	priority_queue<Node> Q;
	Q.push({ sk.x, sk.y, 0 });
	ch[sk.x][sk.y] = 1;

	int ans = 0;

	while (!Q.empty()) {
		int x = Q.top().x;
		int y = Q.top().y;
		int d = Q.top().dist;
		Q.pop();

		if (arr[x][y]!=0 && arr[x][y] < sk.size) {
			arr[x][y] = 0;
			sk.cnt++;
			sk.sizeUp();

			memset(ch, 0, sizeof(ch));
			ans += d;

			while (!Q.empty()) {
				Q.pop();
			}
			Q.push({ x,y,0 });
			ch[x][y] = 1;
			continue;
		}


		for (int i = 0; i < 4; i++) {
			int nx = x + dx[i];
			int ny = y + dy[i];

			if (nx < 0 || nx >= n || ny < 0 || ny >= n || ch[nx][ny]) continue;
			if (arr[nx][ny] <= sk.size) {
				ch[nx][ny] = 1;
				Q.push({ nx,ny,d + 1 });
			}
		}
	}

	cout << ans << '\n';

	return 0;
}

https://www.acmicpc.net/problem/11660

#include <bits/stdc++.h>
using namespace std;


int n, m;
int psum[1025][1025];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	cin >> n >> m;

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			int a;
			cin >> a;
			psum[i + 1][j + 1] = psum[i + 1][j] + psum[i][j + 1] - psum[i][j] + a;
		}
	}

	for (int i = 0; i < m; i++) {
		int x1, x2, y1, y2;
		cin >> x1 >> y1 >> x2 >> y2;
		cout << psum[x2][y2] - psum[x2][y1 - 1] - psum[x1 - 1][y2] + psum[x1-1][y1-1] << '\n';
	}



	return 0;
}

https://www.acmicpc.net/problem/1493

1.문제설명

큰 정육면체부터 채워보면서

다 채울 수 있는지 재귀적으로 구해볼 수 있다.

남은 부분을 새로운 박스로 만드는 것에 대해 

깊이 생각해볼 필요가 있다.

2.문제풀이코드 C++

#include <bits/stdc++.h>
using namespace std;

int arr[20] , ans;
bool flag;


void rec(int l, int w, int h) {

	if (l == 0 || w == 0 || h == 0) return;

	for (int i = 19; i >= 0; i--) {
		if (arr[i] == 0) continue;

		int cur = 1 << i;

		if (l >= cur && w >= cur && h >= cur) {
			arr[i]--;

			rec(l, w, h - cur);
			rec(l-cur, w, cur);
			rec(cur, w - cur, cur);


			ans++;

			return;
		}
	}

	flag = true;

	return;
}



int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int l, w, h, n;
	cin >> l >> w >> h;
	cin >> n;

	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		arr[a] = b;
	}

	rec(l, w, h);

	if (flag) {
		cout << -1 << '\n';
	}
	else {
		cout << ans << '\n';
	}
	

	return 0;
}

우선순위 큐와 벡터 정렬 시간복잡도 차이

가끔 알고리즘 문제를 풀다보면 정렬하는 과정이 필요한 문제가 있습니다.

우선순위 큐

문제를 푸는 과정 중에서 원소의 삽입과 삭제를 할 때마다 정렬이 필요한 경우에는

Priority Queue 자료구조를 이용하여 쉽게 구현할 수 있습니다.

벡터

정렬된 결과가 필요할 때 array나 vector을 sort함수를 이용해 쉽게 정렬해줄 수 있습니다.

우선순위 큐 VS 벡터 Sort

그런데 특정 결과를 얻기 위해서 모든 원소를 한번 정렬해준 결과가 필요할 때

과연 우선순위 큐를 이용해서 pop해주면서 순서대로 사용하는 것과

벡터를 이용해서 한번 nlogn 으로 sort 해주는 것 중

어떤게 더 시간복잡도 상에서 빠른지 궁금해졌습니다.

https://stackoverflow.com/questions/3759112/whats-faster-inserting-into-a-priority-queue-or-sorting-retrospectively

결론

내용을 간단히 정리하면

자료 형태나 문제에 따라 다르겠지만

우선순위 큐에 n개의 항목을 삽입 하는 것은

점근적 복잡도 O(nlogn)를 가지므로 복잡도 측면 에서 결국 한 번 사용하는 것보다 효율적이지 않습니다.

즉 정렬이 최종적으로 한번 만 필요한 경우에는

vector 나 array를 한 번 sort 해주는 게 효율적입니다.

반대로 원소의 삽입과 pop이 빈번한 경우는 우선순위큐를 이용해

효율적으로 알고리즘을 구성할 수 있습니다.

https://www.acmicpc.net/problem/13904

1.문제설명

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point > b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	vector<Hw> v;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		v.push_back({ a,b });
	}

	sort(v.begin(), v.end());

	int ans = 0;
	for (int i = 0; i <v.size(); i++) {
		int day = v[i].day;
		int point = v[i].point;

		while (ch[day] && day>=1) {
			day--;
		}
		if (day == 0) continue;
		ch[day] = 1;
		ans += point;
	}
	
	cout << ans << '\n';
	return 0;
}

2. 우선순위 큐 활용

#include <bits/stdc++.h>
using namespace std;

int n;
bool ch[1001];
struct Hw {
	int day, point;
	bool operator<(const Hw& b) const {
		return point < b.point;
	}
};

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	priority_queue<Hw> Q;

	cin >> n;
	for (int i = 0; i < n; i++) {
		int a, b;
		cin >> a >> b;
		Q.push({ a,b });
	}

	int ans = 0;
	while (!Q.empty()) {
		int day = Q.top().day;
		int point = Q.top().point;
		Q.pop();

		while (ch[day] && day>=1) {
			day--;
		}

		if (day == 0) continue;
		ch[day] = 1;
		ans += point;


	}

	cout << ans << '\n';

	return 0;
}

우선순위큐를 이용해서 삽입할 때마다 바로 정렬을 해주거나

벡터를 이용해서 최종적으로 정렬을 해주거나

문제를 푸는데는 큰 차이가 없어보입니다.