220712 PS 일기 : 교차 개수 세기, 문자열 조합 DP, 누적 합 활용 등

2022년 7월 12일 화요일 푼 문제들과 사용되는 개념들을 정리한다.

 

 

백준 BOJ 1615번 : 교차 개수 세기

문제 난이도 : Gold I

알고리즘 분류 : 세그먼트 트리

 

 

N개의 점들의 쌍에 대해 M개의 선분이 주어질 때 교차 개수를 세는 문제이다.

세그먼트 트리의 가장 대표적인 문제들 중 하나인 Inversion Counting Problem인데 왜 그동안 못 풀고 있었나 봤더니 점들의 위치가 중복되어 주어진다는 점 때문이었다.

 

생각해보니 기존의 Inversion Counting Problem에서 같은 점이 주어져도 update 함수에서 tree[node] = 1로 설정해주었는데, 해당 노드에 점이 하나 추가되는 것이므로 간단히 tree[node]++와 같이 값을 갱신해주기만 하면 되는 문제였다.

 

 

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

vector<pair<int, int>> v;
vector<int> u;

void upd(int n, int b, int e, int idx) {
    if(b == e) {
        u[n] += 1;
        return;
    }

    if(idx <= (b+e)/2) upd(n*2, b, (b+e)/2, idx);
    else upd(n*2 + 1, (b+e)/2 + 1, e, idx);

    u[n] = u[n*2] + u[n*2 + 1];
}

int cnt(int n, int b, int e, int l, int r) {
    if(r < b || e < l) return 0;
    if(l <= b && e <= r) return u[n];

    int lv = cnt(n*2, b, (b+e)/2, l, r);
    int rv = cnt(n*2 + 1, (b+e)/2 + 1, e, l, r);

    return lv + rv;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    v.resize(M);

    for(int i=0; i<M; i++) cin >> v[i].first >> v[i].second;

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

    u.resize(N*4);

    int ans = 0;
    for(int i=0; i<M; i++) {
        ans += cnt(1, 1, N, v[i].second + 1, N);
        upd(1, 1, N, v[i].second);
    }

    cout << ans << "\n";
}

 

 

백준 BOJ 16500번 : 문자열 판별

문제 난이도 : Gold V

알고리즘 분류 : DP

 

 

주어진 문자열들의 목록으로 문자열 S를 만들 수 있는지를 판별하는 문제이다.

DP 문제이고 범위가 넓지 않으므로 모든 자리에 대해 모든 문자열들을 대입해서 확인해보면 된다.

당연하게도 풀이는 탑다운 방식와 바텀업 방식이 있는데 웬만하면 바텀업 방식으로 짜는 것을 개인적으로 선호한다.

문자열 S의 앞에서부터 검사해도 되겠지만 조건문만 더러워질 것 같아서 그냥 뒤에서부터 검사했다.

 

 

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

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    string str; cin >> str;

    int N; cin >> N;

    vector<string> v(N);
    for(int i=0; i<N; i++) cin >> v[i];

    vector<bool> dp(str.length()+1, false);
    dp[str.length()] = true;

    for(int i=str.length()-1; i>=0; i--)
        for(int j=0; j<N; j++) {
            if(i + v[j].length() > str.length()) continue;
            if(str.substr(i, v[j].length()) != v[j]) continue;

            if(dp[i + v[j].length()]) dp[i] = true;
        }

    if(dp[0]) cout << 1 << "\n";
    else cout << 0 << "\n";
}

 

 

백준 BOJ 11055번 : 가장 큰 증가 부분 수열

문제 난이도 : Silver II

알고리즘 분류 : DP

 

수열이 주어질 때 그 부분 수열 중에서 (연속하지 않아도 됨) 합이 가장 큰 부분 수열을 구하는 문제이다.

이전에 풀었었으나 다룬 적이 없어 코드 보는 김에 그냥 다시 정리한다.

 

간단힌 점화식으로 해결이 된다.

dp[i]를 0 ~ i까지의 수열의 부분 수열 중 합이 가장 큰 부분 수열의 합이라고 정의하면 이중 for문을 이용하여 O(N^2)에 쉽게 해결이 된다.

만약 조건이 연속한 부분 수열이었다면 O(N)에 풀이할 수 있음이 잘 알려져있다.

 

이 문제도 더 빨리 푸는 알고리즘이 있을 것 같은데 딱히 생각나지는 않는다.

있다면 무조건 알아둬야 할텐데 생각이 안 나서 아쉽다.

 

 

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

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N; cin >> N;

    vector<int> arr(N);
    for(int i=0; i<N; i++) cin >> arr[i];

    vector<int> dp(arr); // dp[i] : largest sum in the interval "0 ~ i"

    for(int i=0; i<N; i++)
        for(int j=0; j<i; j++)
            if(arr[i] > arr[j]) dp[i] = max(dp[i], dp[j] + arr[i]);

    int ans = 0;
    for(int i=0; i<N; i++) ans = max(ans, dp[i]);

    cout << ans;
}

 

 

백준 BOJ 11997번 : Load Balancing (Silver)

문제 난이도 : Gold IV

알고리즘 분류 : 좌표 압축, 누적 합

 

소들의 좌표가 주어지고 이들을 x축 평행, y축 평행한 직선으로 나누어 4개의 구간으로 나눈다고 할 때, 각 구간 중 소가 가장 많은 구간의 소의 수가 최소가 될 때 그 소의 개수를 구하는 문제이다.

동치는 아니지만 쉽게 말하자면 소를 네 개의 구간으로 최대한 균등 비슷하게 나눠주면 된다.

 

먼저 소의 좌표가 최대 100만까지 나올 수 있음에 비해 소의 수는 1000마리로 적으므로 좌표 압축을 생각해줄 수 있다.

그 다음 누적 합을 이용하여 4개의 구간으로 나눴을 때 소들의 개수를 세서 답을 찾아주면 된다.

소가 최대 1000마리이므로 브루트포스로 탐색해도 된다.

 

다만 좌표 압축과 누적 합을 모두 구하기가 상당히 까다롭고 코드가 길어진다.

특히 누적합을 이용하여 4개 구간 직사각형의 소의 수를 표현하기가 아주 귀찮다.

(w[i][j], w[i][ycnt] - w[i][j], w[xcnt][j] - w[i][j], w[xcnt][ycnt] - w[i][ycnt] - w[xcnt][j] + w[i][j])

 

아주 귀찮아질 뻔했는데 다행히 실수 없이 한 번에 맞았다.

 

 

#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>> vx(N+1), vy(N+1);

    for(int i=1; i<=N; i++) {
        cin >> vx[i].first >> vy[i].first;

        vx[i].second = vy[i].second = i;
    }

    sort(vx.begin()+1, vx.end());
    sort(vy.begin()+1, vy.end());

    struct p { int x, y; };
    vector<p> v(N+1);
    int xcnt = 1, ycnt = 1;

    for(int i=1; i<=N; i++) {
        if(i > 1 && vx[i].first > vx[i-1].first) xcnt++;

        v[vx[i].second].x = xcnt;
    }
    for(int i=1; i<=N; i++) {
        if(i > 1 && vy[i].first > vy[i-1].first) ycnt++;

        v[vy[i].second].y = ycnt;
    }

    vector<vector<int>> u(xcnt+1, vector<int>(ycnt+1));
    for(int i=1; i<=N; i++) u[v[i].x][v[i].y]++;

    vector<vector<int>> w(xcnt+1, vector<int>(ycnt+1));
    for(int i=1; i<=xcnt; i++)
        for(int j=1; j<=ycnt; j++)
            w[i][j] = w[i-1][j] + w[i][j-1] - w[i-1][j-1] + u[i][j];

    int ans = INT_MAX;
    for(int i=1; i<=xcnt; i++)
        for(int j=1; j<=ycnt; j++) {
            int x = max({w[i][j],
                          w[i][ycnt] - w[i][j],
                          w[xcnt][j] - w[i][j],
                          w[xcnt][ycnt] - w[i][ycnt] - w[xcnt][j] + w[i][j]});

            ans = min(ans, x);
        }

    cout << ans << "\n";
}

 

 

백준 BOJ 1327번 : 소트 게임

문제 난이도 : Gold V

알고리즘 분류 : 그래프 이론, 너비 우선 탐색(BFS) 등

 

길이가 N인 수열에서 길이가 M인 부분 수열을 0회 이상 뒤집어 오름차순 수열을 만들 수 있는지의 여부를 판단하는 문제이다.

 

범위가 매우 작기 때문에 모든 경우를 다 확인해볼 수 있다.

다만 구현이 생각보다는 쉽지 않으므로 BFS를 생각해볼 수 있다.

정수 배열이 아닌 문자열을 활용하면 reverse 함수를 이용해 쉽게 뒤집어 줄 수 있고 또 substr 함수로 합치기가 용이하므로 문자열을 이용한 풀이가 무난하다.

문자열의 방문 여부는 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 N, M; cin >> N >> M;

    string str = "";

    for(int i=0; i<N; i++) {
        char c; cin >> c;

        str += c;
    }

    string asc = str;
    sort(asc.begin(), asc.end());

    queue<pair<string, int>> q;
    q.push({str, 0});

    map<string, bool> vis;
    vis[str] = true;

    while(!q.empty()) {
        string s = q.front().first;
        int cnt = q.front().second;
        q.pop();

        if(s == asc) {
            cout << cnt << "\n";
            return 0;
        }

        for(int i=0; i<N-M+1; i++) {
            string temp = s.substr(i, M);
            reverse(temp.begin(), temp.end());
            string rev = s.substr(0, i) + temp + s.substr(i+M, s.length()-(i+M));
            
            if(vis[rev]) continue;
            
            vis[rev] = true;
            q.push({rev, cnt + 1});
        }
    }

    cout << -1 << "\n";
}

 

 

 

오늘은 10문제를 풀었다.

갈수록 안 푼 문제 중에서는 쉬운 문제들이 줄어들고 있어서 어려운 문제들을 많이 풀어야겠다고 생각한다.