백준 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";
    }
}