백준 BOJ 스위핑, 값/좌표 압축 알고리즘 문제 풀이 모음 220819
백준 BOJ 18869번 : 멀티버스 II
문제 난이도 : Gold V
알고리즘 분류 : 값/좌표 압축
두 집합에 대해, a_i, a_j와 b_i, b_j의 대소 관계가 모두 같다면 두 집합은 동일하다고 할 때, N개의 집합에 대해 몇 개의 집합 쌍이 동일한지를 구하는 문제이다.
각 집합에 대해 좌표 압축을 수행해주면, 원소들의 대소 관계가 같은 집합은 동일한 원소들을 가지게 된다.
이를 활용하여 좌표 압축을 N번 반복해준 뒤 브루트포스로 답을 구해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int M, N; cin >> M >> N;
vector<vector<int>> v(M, vector<int>(N)), u(v), w(v);
for(int i=0; i<M; i++) {
for(int j=0; j<N; j++) {
cin >> v[i][j];
u[i][j] = v[i][j];
}
sort(u[i].begin(), u[i].end());
u[i].erase(unique(u[i].begin(), u[i].end()), u[i].end());
for(int j=0; j<v[i].size(); j++)
w[i][j] = lower_bound(u[i].begin(), u[i].end(), v[i][j]) - u[i].begin();
}
int ans = 0;
for(int i=0; i<M; i++)
for(int j=i+1; j<M; j++)
if(w[i] == w[j]) ans++;
cout << ans << "\n";
}
백준 BOJ 1911번 : 흙길 보수하기
문제 난이도 : Silver I
알고리즘 분류 : 그리디, 스위핑
1차원 좌표 상의 N개의 물 웅덩이의 양 끝 좌표가 주어질 때, 길이가 M인 널빤지로 이들을 모두 커버하기 위해서 최소 몇 개의 널빤지가 필요한지 구하는 문제이다.
먼저 N개의 웅덩이를 좌표 순으로 정렬한 뒤, 왼쪽 웅덩이부터 최소한의 판자로 메꾸고 나서 현재 좌표를 판자의 오른쪽 끝으로 갱신해준다.
그 다음 웅덩이에 대해서는, 웅덩이의 오른쪽 끝보다 현재 좌표가 크면 그냥 넘어가고, 그렇지 않으면 오른쪽 끝까지 다시 판자로 덮는 과정을 반복한다. (스위핑)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
int x = INT_MIN, ans = 0;
for(int i=0; i<N; i++) {
if(x >= v[i].second) continue;
x = max(x, v[i].first);
int cnt = ((v[i].second - x) - 1) / M + 1;
ans += cnt;
x += M * cnt;
}
cout << ans << "\n";
}
백준 BOJ 21600번 : 계단
문제 난이도 : Silver I
알고리즘 분류 : 그리디, 스위핑
N개의 막대로 이루어진 히스토그램이 주어졌을 때, 가장 큰 연속된 계단의 크기를 구하는 문제이다. (자세한 설명은 문제 원문을 참고하는 것을 추천한다.)
cur를 현재 위치를 마지막으로 이루는 계단의 높이라고 하고, ans를 지금까지 cur 중에 최대 cur 값이라고 하면, 맨 왼쪽 값부터 입력을 받으면서 cur와 ans를 갱신해나가며 답을 구할 수 있다.
예를 들어 특정 위치에서의 높이가 cur보다 높다면, cur를 1 증가시켜줄 수 있다. (1칸 더 높은 계단을 연결할 수 있으므로)
만약 그렇지 않다면, 현재 높이가 현재 위치를 마지막으로 하는 계단의 높이가 된다.
ans 값은 조건문에 관계없이 항상 갱신시켜주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
int ans = 0, cur = 0;
for(int i=0; i<N; i++) {
int x; cin >> x;
if(x > cur) cur++;
else cur = x;
ans = max(ans, cur);
}
cout << ans << "\n";
}
백준 BOJ 12867번 : N차원 여행
문제 난이도 : Silver II
알고리즘 분류 : 값/좌표 압축
N차원 좌표 상에서, 원점에서 시작하여 N번의 이동을 할 때 중복 방문한 지점이 있었는지를 구하는 문제이다.
이 때, N은 10억 이하이고 이동 횟수는 50 이하이다.
N이 아주 크므로 좌표 압축을 통해 0인 부분을 제거하면 벡터의 크기를 50 이하로 줄일 수 있다.
좌표 압축을 사용해준 뒤 vector<int>에서 bool로 가는 map을 활용하여 중복 여부를 체크해줄 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int M, N; cin >> M >> N;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) {
cin >> v[i];
u[i] = v[i];
}
vector<char> vv(N);
for(int i=0; i<N; i++) cin >> vv[i];
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
vector<int> w(N);
for(int i=0; i<v.size(); i++)
w[i] = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
map<vector<int>, bool> m;
vector<int> uu(N);
m[uu] = true;
bool check = true;
for(int i=0; i<N; i++) {
if(vv[i] == '+') uu[w[i]]++;
else if(vv[i] == '-') uu[w[i]]--;
if(m[uu]) check = false;
m[uu] = true;
}
if(check) cout << 1 << "\n";
else cout << 0 << "\n";
}
백준 BOJ 15889번 : 호 안에 수류탄이야!!
문제 난이도 : Silver III
알고리즘 분류 : 그리디, 스위핑
N명의 사람의 수직선 상의 좌표가 주어지고, 그 중 왼쪽 N-1명이 수류탄을 던질 수 있는 범위가 주어질 때, 맨 왼쪽 사람에서 전달을 시작하여 맨 오른쪽 사람이 받을 수 있는지의 여부를 구하는 문제이다.
맨 왼쪽 사람부터 시작하여 각 사람이 도달 가능한 최대 거리를 구하고, 다음 사람이 이 최대 거리 내에 있어야 전달이 가능하다.
만약 한 사람이라도 해당하지 않는 경우가 발생한다면 맨 오른쪽까지 도달하는 것은 불가능하다.
원래는 이 문제에서는 정렬을 해줄 필요가 없다고 나오지는 않았으나, 맥락 상 좌표 순서대로 주어진다고 유추가 가능하기 때문에 정렬을 해주지 않아도 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v(N);
for(int i=0; i<N; i++) cin >> v[i];
vector<int> u(N-1);
for(int i=0; i<N-1; i++) cin >> u[i];
int sum = 0;
for(int i=0; i<N-1; i++) {
sum = max(sum, v[i] + u[i]);
if(sum < v[i+1]) {
cout << "엄마 나 전역 늦어질 것 같아\n";
return 0;
}
}
cout << "권병장님, 중대장님이 찾으십니다\n";
}
백준 BOJ 24035번 : Impartial Offerings
문제 난이도 : Silver IV
알고리즘 분류 : 값/좌표 압축
N마리의 강아지들에게 간식을 주는데, 모든 강아지들에게 간식을 1 이상 주되 무게가 더 무거운 강아지한테는 더 많은 간식을 준다고 할 때 주어야 할 모든 간식의 양의 최솟값을 구하는 문제이다.
강아지들의 무게에 대한 값들을 압축해주면, 그 합들이 답이 된다.
예를 들어 N = 4이고 30 20 5 5라면, 이를 값 압축을 해주면 3 2 1 1이 되고, 간식을 이렇게 주면 된다.
따라서 이 경우 답은 3+2+1+1 = 7이 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int T; cin >> T;
for(int t=1; t<=T; t++) {
int N; cin >> N;
vector<int> v(N), u(N);
for(int i=0; i<N; i++) {
cin >> v[i];
u[i] = v[i];
}
sort(u.begin(), u.end());
u.erase(unique(u.begin(), u.end()), u.end());
vector<int> w(N);
for(int i=0; i<v.size(); i++)
w[i] = lower_bound(u.begin(), u.end(), v[i]) - u.begin() + 1;
int ans = 0;
for(int i=0; i<N; i++) ans += w[i];
cout << "Case #" << t << ": " << ans << "\n";
}
}
백준 BOJ 8641번 : Sklep
문제 난이도 : Silver IV
알고리즘 분류 : 해시를 사용한 집합과 맵
N개의 목록에 걸쳐 상품의 번호와 개수가 주어질 때, 상품의 번호가 한 번씩 나타나도록 하여 각 상품의 개수를 구하는 문제이다.
이 때 출력 순서는 해당 상품 번호가 먼저 나타난 순으로 출력해야 한다.
해시를 사용한 집합과 맵을 사용하여 풀이해줄 수 있다.
이전에 나온 적 없는 상품이면 벡터에 넣어주고, 마지막에 이 벡터에 나온 순서대로 맵의 값을 출력해주면 된다.
unordered_map을 사용하면 일반 map보다 2배 빠른 속도로 통과할 수 있다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<int> v;
unordered_map<int, int> m;
while(N--) {
int a, b; cin >> a >> b;
if(m[a] == 0) v.push_back(a);
m[a] += b;
}
cout << v.size() << "\n";
for(int i=0; i<v.size(); i++)
cout << v[i] << " " << m[v[i]] << "\n";
}
백준 BOJ 18881번 : Social Distancing II
문제 난이도 : Silver V
알고리즘 분류 : 정렬, 스위핑
N마리의 소가 있고, 각각 위치와 병에 걸린 여부(1 or 0)가 주어질 때 병 걸린 소는 특정 거리 (입력으로 주어지지 않음) 내에 있는 소들을 감염시킨다고 할 때, 최초에 감염되었을 수 있는 소의 최소 마리 수를 구하는 문제이다.
먼저 소들을 정렬해주고, 인접한 두 소들 중 한 마리만 병에 걸린 경우 감염 반경은 그 두 소의 거리 미만임을 알 수 있다.
따라서 모든 인접한 소들에 대해 이러한 검사를 해주어 r의 범위를 찾는다.
이제 병에 걸린 소들만 벡터에 저장한 뒤 인접한 소들 사이의 거리가 r보다 큰 경우 이들은 서로 다른 근원지에서 병이 걸렸음을 알 수 있으므로, 인접한 병 걸린 소들을 탐색하며 답에 1씩 추가해주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v(N);
for(int i=0; i<N; i++)
cin >> v[i].first >> v[i].second;
sort(v.begin(), v.end());
int r = INT_MAX;
for(int i=1; i<N; i++)
if(v[i-1].second != v[i].second)
r = min(r, v[i].first - v[i-1].first - 1);
vector<int> u;
for(int i=0; i<N; i++)
if(v[i].second == 1) u.push_back(v[i].first);
int ans = 1;
for(int i=1; i<u.size(); i++)
if(u[i] - u[i-1] > r) ans++;
cout << ans << "\n";
}
백준 BOJ 14567번 : 선수과목 (Prerequisite)
문제 난이도 : Gold V
알고리즘 분류 : 위상 정렬
M개의 순서쌍 (a, b)에 대해 a를 반드시 b보다 이전 학기에 들어야할 때, N개의 과목을 최소 학기에 모두 듣기 위해서는 각 과목들을 몇 학기에 들어야 하는지 구하는 문제이다.
위상 정렬 문제로, 기존 위상 정렬 코드에서 queue 부분에 학기만 기록할 수 있도록 해주면 된다.
최초로 queue에 넣은 과목들은 1학기에 듣고, 그 다음 push 되는 것들은 1학기 증가시켜서 저장하고, ... 이 과정을 반복하면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
vector<vector<int>> adj(N+1);
vector<int> deg(N+1);
while(M--) {
int a, b; cin >> a >> b;
adj[a].push_back(b);
deg[b]++;
}
queue<int> q;
vector<int> ans(N+1);
for(int i=1; i<=N; i++)
if(deg[i] == 0) {
q.push(i);
ans[i] = 1;
}
while(!q.empty()) {
int x = q.front();
q.pop();
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
deg[y]--;
if(deg[y] == 0) {
ans[y] = ans[x] + 1;
q.push(y);
}
}
}
for(int i=1; i<=N; i++) cout << ans[i] << " ";
cout << "\n";
}
백준 BOJ 2171번 : 직사각형의 개수
문제 난이도 : Gold IV
알고리즘 분류 : 자료 구조
2차원 좌표 평면 상에 주어진 N개의 점에 대해, 그들 중 4개를 선택하여 만들 수 있는 직사각형의 개수를 구하는 문제이다.
원래는 좌표 압축을 사용하여 풀이하려고 했는데, 더 좋은 풀이 겸 배울 게 많은 방법이 있어서 해당 방법으로 풀이해보았다.
set을 사용하면 log 시간에 데이터를 삽입, 삭제, 탐색할 수 있기 때문에 이런 문제를 짧은 코드로도 풀이할 수 있다.
아무튼 핵심 풀이는 set에 모든 좌표들을 넣고, 2중 for문으로 잡은 두 점을 직사각형의 대각선에 위치한 점이라고 보고 set에 나머지 두 점이 존재하는지를 찾는 것이다.
다만 이 경우 반대 대각선으로도 직사각형의 count가 한 번 더 일어나므로, count 된 값을 2로 나누어 정답을 얻어주면 된다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v;
set<pair<int, int>> s;
for(int i=0; i<N; i++) {
int x, y; cin >> x >> y;
v.push_back({x, y});
s.insert({x, y});
}
int ans = 0;
for(int i=0; i<N; i++)
for(int j=i+1; j<N; j++) {
if(v[i].first == v[j].first || v[i].second == v[j].second) continue;
if(s.count({v[i].first, v[j].second}) > 0 && s.count({v[j].first, v[i].second})) ans++;
}
ans /= 2;
cout << ans << "\n";
}
백준 BOJ 11830번 : Star triangles
문제 난이도 : Silver I
알고리즘 분류 : 해시를 사용한 집합과 맵
N개의 점의 좌표가 주어졌을 때, 그 중 3개를 선택하여 두 변이 x축, y축과 평행한 직각삼각형의 수를 구하는 문제이다.
어떤 점의 좌표에 대해서, x 좌표가 같은 점 1개와 y 좌표가 같은 점 1개를 선택해서 직각삼각형을 만들 수 있다.
따라서 map 2개를 선언하여 각 점들의 x 좌표와 y 좌표의 수를 저장하고, 각 점에 대해 위에서 말한대로 점 한 개씩을 선택해서 곱해주면 경우의 수가 된다. (물론 자기 자신에 해당하는 점 1개는 빼야한다.)
#include <bits/stdc++.h>
#define int long long
using namespace std;
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N; cin >> N;
vector<pair<int, int>> v;
unordered_map<int, int> mx, my;
for(int i=0; i<N; i++) {
int x, y; cin >> x >> y;
v.push_back({x, y});
mx[x]++;
my[y]++;
}
int ans = 0;
for(int i=0; i<N; i++) {
ans += (mx[v[i].first] - 1) * (my[v[i].second] - 1);
}
cout << ans << "\n";
}
백준 BOJ 5971번 : Meeting Place
문제 난이도 : Gold V
알고리즘 분류 : LCA
N개의 노드를 가진 트리가 주어지고 M개의 쿼리에 대해 두 노드의 최소 공통 조상(LCA)을 구하는 문제이다.
N이 1,000 이하이므로 하나의 쿼리를 O(H) 시간에 처리하는 풀이로 풀어도 되지만, log(H) 시간 LCA 알고리즘을 다시 작성해보는 겸 로그 시간 풀이로 풀이하였다.
#include <bits/stdc++.h>
#define int long long
using namespace std;
vector<vector<int>> adj, par, dis;
vector<int> dep;
void fp(int p, int x, int d) {
if(adj[x].size() == 0) return;
par[x][0] = p;
dep[x] = d;
for(int i=0; i<adj[x].size(); i++) {
int y = adj[x][i];
if(y != p) fp(x, y, d+1);
}
}
main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL), cout.tie(NULL);
int N, M; cin >> N >> M;
adj.resize(N+1);
for(int i=2; i<=N; i++) {
int x; cin >> x;
adj[i].push_back(x);
adj[x].push_back(i);
}
par.resize(N+1, vector<int>(30));
dep.resize(N+1);
fp(0, 1, 0);
int H = (int)floor(log2(N+1));
dis.resize(N+1, vector<int>(30));
for(int i=1; i<=H; i++)
for(int j=2; j<=N; j++)
if(par[j][i-1] != 0) {
par[j][i] = par[par[j][i-1]][i-1];
dis[j][i] = dis[j][i-1] + dis[par[j][i-1]][i-1];
}
while(M--) {
int a, b; cin >> a >> b;
if(dep[a] != dep[b]) {
if(dep[a] < dep[b]) swap(a, b);
int diff = dep[a] - dep[b];
for(int i=0; diff>0; i++) {
if(diff % 2 == 1) a = par[a][i];
diff /= 2;
}
}
if(a != b) {
for(int i=H; i>=0; i--)
if(par[a][i] != 0 && par[a][i] != par[b][i]) {
a = par[a][i];
b = par[b][i];
}
a = par[a][0];
}
cout << a << "\n";
}
}