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;
}

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

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

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

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

1.문제설명

각 센서들의 좌표를 정렬하고 각 좌표간의 간격을 구해서 다시 정렬하여

가장 긴 간격을 k의 개수에 따라서 알맞게 빼주면 답을 구할 수 있습니다.

좌표는 중복된 값이 들어올 수 있으므로 set 자료구조를 이용하면 편하게 구할 수 있습니다.

6
2
1 6 9 3 6 7

위 예제에서는 센서간의 간격의 길이가 3이 제일 길기 때문에

전체 간격의 길이인 9-1=8에서 3을 빼주면

나머지 센서를 다 포괄할 수 있게 됩니다.

2.문제풀이코드 C++

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

int n, k;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n >> k;
	set<int> num;

	for (int i = 0; i < n; i++) {
		int tmp;
		cin >> tmp;
		num.insert(tmp);
	}

	n = num.size();

	if (n <= k) {
		cout << 0;
		return 0;
	}
	vector<int> v(num.begin(), num.end());

	vector<int> interval;

	int ans = 0;
	for (int i = 0; i < n - 1; i++) {
		ans += v[i + 1] - v[i];
		interval.push_back(v[i + 1] - v[i]);
	}

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

	
	for (int i = 0; i < k-1; i++) {
		ans -= interval[interval.size() - 1 - i];
	}
	cout << ans << '\n';


	

	return 0;
}

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

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



int n, k;

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

	vector<int> v;
	for (int i = 0; i < k; i++) {
		int tmp;
		cin >> tmp;
		v.push_back(tmp);
	}

	unordered_set<int> set;

	int ans = 0;
	for (int i = 0; i < k; i++) {
		int tmp = v[i];

		if (set.size() < n) {
			set.insert(tmp);
		}
		else if(set.size()==n) {
			if (set.count(tmp)) {
				continue;
			}
			else {
				map<int, int> m;

				for (auto x : set) {
					m[x] = 1000;
				}

				for (int j = i + 1; j < k; j++) {
					if (set.count(v[j])) {
						m[v[j]] = min(m[v[j]], j);
					}
				}

				int maxx = 0;
				int max_id = -1;

				for (auto x : set) {
					if (maxx < m[x]) {
						maxx = m[x];
						max_id = x;
					}
				}
				set.erase(max_id);
				set.insert(tmp);
				
				ans++;
			}
		}

	}

	cout << ans << '\n';


	return 0;
}

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

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

int n;
vector<pair<int, int> > v;
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	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());

	priority_queue<int> Q;

	for (int i = 0; i < n; i++) {
		if (i == 0) {
			Q.push(-v[i].second);
			continue;
		}

		if (v[i].first >= -Q.top()) {
			Q.pop();
			Q.push(-v[i].second);
		}
		else {
			Q.push(-v[i].second);
		}
	}

	cout << Q.size() << '\n';


	return 0;
}

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

1.문제설명

이 문제의 답을 구하는 방법은 크게 두가지가 있습니다.

첫번째는

123~987중에서 조건이 주어질 때마다 정답이 될 수 있는 후보만 남겨주는 것입니다.

두번째는

조건에 부합하는 숫자의 집합을 구해서 모든 조건의 교집합을 구해내는 것입니다.

첫번째로 구하는게 123~987 내에서 계산하는 숫자를 계속 좁혀나가니까 효율적입니다.

저는 처음에 든생각이 두번째로 푸는거라 이악물고 풀었는데 답이 나오네요

테스트케이스가 워낙 작아서 두번째도 가능합니다.

두가지방법 모두 코드를 올립니다.

2.문제풀이코드 C++

첫번째 방법

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

int n;
bool ch[1000];

void compare(int x, int y, int z) {

	for (int i = 123; i <= 987; i++) {
		if (ch[i]) {
			int s = 0, b = 0;

			int arr1[3] = { i / 100, (i % 100) / 10 ,i % 10 };
			int arr2[3] = { x / 100, (x % 100) / 10 ,x % 10 };


			for (int j = 0; j < 3; j++) {
				for (int k = 0; k < 3; k++) {
					if(j==k && (arr1[j]==arr2[k])){
						s++;
					}
					else if (j != k && arr1[j] == arr2[k]) {
						b++;
					}
				}
			}

			//후보에서 제외
			if (!(y == s && z == b)) {
				ch[i] = 0;
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	//ch배열 초기화 
	for (int i = 1; i <= 9; i++) {
		for (int j = 1; j <= 9; j++) {
			for (int k = 1; k <= 9; k++) {
				if (i != j && k != j && i != k) {
					ch[i * 100 + 10 * j + k] = 1;
				}
			}
		}
	}


	for (int i = 0; i < n; i++) {
		int x, y, z;
		cin >> x >> y >> z;
		compare(x, y, z);
	}


	int ans = 0;
	for (int i = 0; i < 1000; i++) {
		if (ch[i]) ans++;
	}

	cout << ans << '\n';

	return 0;
}

두번째 방법

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

int n;
bool ch[101][1000];

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

	for (int i = 0; i < n; i++) {
		int a, s, b;
		cin >> a >> s >> b;

		int x = a / 100;
		int y = (a % 100) / 10;
		int z = a % 10;

		if (s == 3 && b == 0) {
			cout << 1 << '\n';
			return 0;
		}
		else if (s == 0 && b == 3) {
			ch[i][z * 100 + x * 10 + y] = 1;
			ch[i][y * 100 + z * 10 + x] = 1;
		}
		else if (s == 1 && b == 2) {
			ch[i][100 * x + 10 * z + y] = 1;
			ch[i][100 * z + 10 * y + x] = 1;
			ch[i][100 * y + 10 * x + z] = 1;
		}
		else if (s == 2 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * y + j] = 1;
					ch[i][100 * x + 10 * j + z] = 1;
					ch[i][100 * j + 10 * y + z] = 1;
				}
			}
		}
		else if (s == 1 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * x + 10 * j + y] = 1;
					ch[i][100 * x + 10 * z + j] = 1;
					ch[i][100 * z + 10 * y + j] = 1;
					ch[i][100 * j + 10 * y + x] = 1;
					ch[i][100 * j + 10 * x + z] = 1;
					ch[i][100 * y + 10 * j + z] = 1;
				}
			}
		}
		else if (s == 0 && b == 2) {
			for (int j = 1; j <= 9; j++) {
				if (j != z && j != x && j != y) {
					ch[i][100 * j + 10 * x + y] = 1;
					ch[i][100 * y + 10 * x + j] = 1;
					ch[i][100 * y + 10 * j + x] = 1;
					ch[i][100 * z + 10 * j + x] = 1;
					ch[i][100 * z + 10 * x + j] = 1;
					ch[i][100 * j + 10 * z + x] = 1;
					ch[i][100 * z + 10 * j + y] = 1;
					ch[i][100 * y + 10 * z + j] = 1;
					ch[i][100 * j + 10 * z + y] = 1;
				}
			}
		}
		else if (s == 1 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * x + 10 * j + k] = 1;
						ch[i][100 * j + 10 * y + k] = 1;
						ch[i][100 * j + 10 * k + z] = 1;
					}
				}
			}
		}
		else if (s==0 && b == 1) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					if (j != z && j != x && j != y && j != k && k != x && k != y && k != z) {
						ch[i][100 * j + 10 * x + k] = 1;
						ch[i][100 * j + 10 * k + x] = 1;

						ch[i][100 * y + 10 * j + k] = 1;
						ch[i][100 * j + 10 * k + y] = 1;

						ch[i][100 * z + 10 * j + k] = 1;
						ch[i][100 * j + 10 * z + k] = 1;

					}
				}
			}
		}
		else if (s == 0 && b == 0) {
			for (int j = 1; j <= 9; j++) {
				for (int k = 1; k <= 9; k++) {
					for (int t = 1; t <= 9; t++) {
						if (j != z && j != x && j != y && j != k && k != x && k != y && k != z
							&& x != t && y != t && z != t && k != t && j != t) {
							ch[i][100 * j + 10 * t + k] = 1;
						}
					}
				}
			}

		}
	}

	int ans = 0;

	for (int i = 100; i < 1000; i++) {
		bool flag = true;
		for (int j = 0; j < n; j++) {
			if (ch[j][i] == 0) {
				flag = false;
				break;
			}
		}
		if (flag) ans++;
	}

	cout << ans << '\n';
	return 0;
}

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

1.문제설명

1. 서로 다른 사탕이 있으면 바꾼다.

2. 모든 행과 열에서 연속되는 최대 사탕의 수를 구해본다.

3. 1과 2를 모든 영역에 대해 반복해야한다.

2.문제풀이코드 C++

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

int n, ans;
char arr[51][51];

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

void Count() {
	for (int i = 0; i < n; i++) {
		int comp = arr[i][0];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[i][j]) {
				cnt++;
			}
			else {
				comp = arr[i][j];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

	for (int i = 0; i < n; i++) {
		int comp = arr[0][i];
		int cnt = 1;
		for (int j = 1; j < n; j++) {
			if (comp == arr[j][i]) {
				cnt++;
			}
			else {
				comp = arr[j][i];
				ans = max(ans, cnt);
				cnt = 1;
			}
		}
		ans = max(ans, cnt);
	}

}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	
	cin >> n;
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < n; j++) {
			arr[i][j] = s[j];
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {

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

				if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
				if (arr[i][j] != arr[nx][ny]) {
					swap(arr[i][j], arr[nx][ny]);
					Count();
					swap(arr[i][j], arr[nx][ny]);
				}
			}
		}
	}
	
	cout << ans << '\n';


	return 0;
}