백준 BOJ 알고리즘 공부 일기 (오프라인 쿼리 포함) 220829

백준 BOJ 13306번 : 트리

문제 난이도 : Platinum IV

알고리즘 분류 : 오프라인 쿼리, 분리 집합

 

트리와 쿼리가 주어질 때, 각 쿼리에 대해 특정 간선을 지우거나 두 정점이 연결 상태인지를 구하는 문제이다.

 

오프라인 쿼리 문제인데, 오프라인 쿼리 문제는 주어진 쿼리 순서대로 처리를 하는 것이 아니라 문제를 효율적으로 풀 수 있게끔 쿼리의 순서를 재배치하여 풀이하는 방식의 문제를 말한다.

예를 들어 이 문제에서는 쿼리를 역순으로 배치한 뒤 분리 집합으로 노드들을 연결해가면서 풀어주면 아주 쉽게 풀 수 있다.

역순 배치가 아닌 다른 순서대로 푸는 문제도 있는 것 같던데 조만간 공부할 것이다. (예를 들면 mo's 알고리즘. 지금 제곱근 분할법 문제 몇 개는 풀어봤는데 mo's를 공부 안해서 못 풀고 있는 문제들이 많다.)

 

 

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

struct s { int Q, a, b; };

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

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

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

    vector<int> p(N+1);
    for(int i=2; i<=N; i++) cin >> p[i];

    M += N-1;

    vector<s> q(M);

    for(int i=0; i<M; i++) {
        cin >> q[i].Q;

        if(q[i].Q == 0) cin >> q[i].a;
        else if(q[i].Q == 1) cin >> q[i].a >> q[i].b;
    }

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    stack<bool> ans;

    for(int i=M-1; i>=0; i--) {
        if(q[i].Q == 0) {
            if(f(q[i].a) != f(p[q[i].a])) v[f(q[i].a)] = f(p[q[i].a]);
        }
        else if(q[i].Q == 1) {
            if(f(q[i].a) == f(q[i].b)) ans.push(true);
            else ans.push(false);
        }
    }

    while(!ans.empty()) {
        if(ans.top()) cout << "YES\n";
        else cout << "NO\n";

        ans.pop();
    }
}

 

 

백준 BOJ 10775번 : 공항

문제 난이도 : Gold II

알고리즘 분류 : 분리 집합

 

N개의 게이트가 있고, M개의 비행기가 각각 u_i번 이하의 게이트에 도킹할 수 있다고 할 때, 주어진 입력 순서대로 비행기가 도킹한다면 최대로 도킹할 수 있는 비행기의 수를 구하는 문제이다.

 

그리디하게 접근하여 u_i 이하의 도킹이 가능한 가장 큰 번호의 게이트에 도킹을 해준다.

그 다음, 같은 번호의 게이트에 비행기가 들어올 경우 그 이하의 최대 번호로 연결을 효율적으로 해주어야 하는데 여기서 분리 집합을 사용하면 수월하다.

f(u_i)번 게이트에 도킹 후 f(u_i)값을 f(u_i) - 1로 해주면 된다.

한 번 parent로 이동했을 때 그 게이트가 이미 차 있다고 하더라도 해당 게이트의 parent 역시 다른 게이트로 연결되어 있을 것이기 때문에 빈 게이트를 효율적으로 찾아줄 수가 있다.

도킹을 계속 하다가 만약 f(u_i) = 0일 경우 도킹이 더 이상 불가능한 것이므로 지금까지 연결한 비행기의 개수로 답을 얻어주면 된다.

 

 

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

vector<int> v;

int f(int x) {
    if(v[x] == x) return x;
    else return v[x] = f(v[x]);
}

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

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

    v.resize(N+1);
    for(int i=1; i<=N; i++) v[i] = i;

    int ans = 0;

    vector<int> u(M);
    for(int i=0; i<M; i++) cin >> u[i];

    for(int i=0; i<M; i++) {
        int x = u[i];

        if(f(x) == 0) break;

        v[f(x)] = f(x) - 1;
        ans++;
    }

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

 

 

백준 BOJ 1440번 : 타임머신

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

시, 분, 초가 주어질 때 시, 분, 초의 순서를 바꾸어 (그대로인 것 포함) 읽어도 시, 분, 초의 범위에 해당하는 것의 개수를 구하는 문제이다.

 

next_permutation으로 3!가지 경우를 모두 확인해보면 된다.

다만 이 문제의 경우 두 값이 같은 경우도 있는데 next_permutation 함수는 이 경우를 건너뛰므로 모두 다른 값을 가지는 벡터 하나를 추가로 이용해주는 방법 등을 사용해야한다.

 

 

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

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

    vector<int> v(3);

    char c;

    cin >> v[0] >> c >> v[1] >> c >> v[2];

    vector<int> u(3);
    u[0] = 0, u[1] = 1, u[2] = 2;

    int ans = 0;

    while(true) {
        if(v[u[0]] >= 1 && v[u[0]] <= 12 && v[u[1]] >= 0 && v[u[1]] <= 59 && v[u[2]] >= 0 && v[u[2]] <= 59) ans++;

        if(!next_permutation(u.begin(), u.end())) break;
   }

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

 

 

백준 BOJ 7637번 : AAAAHH! Overbooked!

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

24시간짜리 시간으로 주어진 N개의 시간 범위에 대해, 겹치는 것이 있는지 확인하는 문제이다.

 

24 x 60짜리 크기의 bool 변수를 이용하여 체크를 일일이 해주면서 새로 체크할 값에 이미 체크가 하나라도 되어있다면 conflict를, 그렇지 않다면 no conflict를 출력해주면 된다.

 

 

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

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

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        vector<bool> v(24*60);
        bool check = true;

        while(N--) {
            string str; cin >> str;

            int a = stoi(str.substr(0, 2));
            int b = stoi(str.substr(3, 2));
            int c = stoi(str.substr(6, 2));
            int d = stoi(str.substr(9, 2));

            for(int i=a*60+b; i<c*60+d; i++) {
                if(v[i]) check = false;

                v[i] = true;
            }
        }

        if(check) cout << "no conflict\n";
        else cout << "conflict\n";
    }
}

 

 

백준 BOJ 8676번 : Figury

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

주어진 N개의 수에 대해 3개 연속으로 다른 수가 나오는 경우가 있는지 체크하는 문제이다.

 

단순히 3개씩 묶어서 일일이 확인해보면 된다.

 

 

#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];

    bool check = false;

    for(int i=2; i<N; i++)
        if(v[i] != v[i-1] && v[i-1] != v[i-2] && v[i-2] != v[i]) check = true;

    if(check) cout << "TAK\n";
    else cout << "NIE\n";
}

 

 

백준 BOJ 9151번 : Starship Hakodate-maru

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

N 이하이면서 가장 큰 a^3 + b x (b+1) x (b+2) / 6의 값을 구하는 문제이다.

 

2중 for문으로 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);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

        int ans = 0;

        for(int i=0; i*i*i<=N; i++)
            for(int j=0; i*i*i+j*(j+1)*(j+2)/6<=N; j++) ans = max(ans, i*i*i + j*(j+1)*(j+2)/6);

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

 

 

백준 BOJ 9182번 : Biorhythms

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

특성 a는 23일마다, 특성 b는 28일마다, 특성 c는 33일마다 발현되며 하나의 테스트케이스에 각 특성이 발현된 날짜, 그리고 현재 날짜가 주어질 때 다음 날부터 세 특성이 모두 발현되는 날 중 가장 가까운 날까지의 기간을 구하는 문제이다.

 

입력이 a b c d로 들어온다고 해보자.

그러면 x > d인 x에 대해 x % 23 = a % 23이고, x % 28 = b % 28이고, x % 33 = c % 23이라면 x는 d일 이후 세 특성이 모두 발현되는 날이다.

따라서 이러한 x 중 가장 작은 것을 답으로 얻어주면 된다.

 

 

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

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

    for(int t=1; ; t++) {
        int a, b, c, d; cin >> a >> b >> c >> d;
        if(a == -1 && b == -1 && c == -1 && d == -1) break;

        for(int i=d+1; i<=21252; i++) {
            if(i % 23 == a % 23 && i % 28 == b % 28 && i % 33 == c % 33) {
                cout << "Case " << t << ": the next triple peak occurs in " << i - d << " days.\n";
                break;
            }
        }
    }
}

 

 

백준 BOJ 9377번 : String LD

문제 난이도 : Bronze II

알고리즘 분류 : 브루트포스

 

N개의 문자열에 대해, 각 문자열의 맨 왼쪽 문자를 지우는 연산을 다음이 되기 전까지 반복한다.

1. 문자열의 길이가 1인 것이 발생

2. 두 문자열이 같은 것이 발생

 

이 때, 연산을 최대 몇 번 수행할 수 있는지 구하는 문제이다.

예를 들어 1번 연산을 수행하여 같은 문자열이 발생한다면 답은 0이다. (발생 이전까지만 반복해야하므로)

 

조건 그대로 체크만 해주면 된다.

같은 문자열이 있는 것은 sort 해준 뒤 v[i-1]과 v[i]를 비교해주면 된다.

다만 두 문자열이 같은 것이 발생했을 경우는 이미 연산을 수행한 이후이므로 연산 수행 횟수를 잘 계산해서 구해주어야 한다. (0번이면 상관 없지만, 1번 이상인 경우는 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);

    while(true) {
        int N; cin >> N;
        if(N == 0) break;

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

        for(int i=0; ; i++) {
            sort(v.begin(), v.end());

            bool check = false;

            for(int j=0; j<N; j++)
                if(v[j].length() == 1) check = true;

            for(int j=1; j<N; j++)
                if(v[j] == v[j-1]) check = true;

            if(check) {
                cout << i << "\n";
                break;
            }

            for(int j=0; j<N; j++)
                v[j] = v[j].substr(1, v[j].length()-1);

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

            check = false;

            for(int j=1; j<N; j++)
                if(v[j] == v[j-1]) check = true;

            if(check) {
                cout << i << "\n";
                break;
            }
        }
    }
}

 

 

백준 BOJ 9161번 : Sir Bedavere’s Bogus Division Solutions

문제 난이도 : Bronze III

알고리즘 분류 : 브루트포스

 

한 숫자의 맨 뒷자리와 다른 숫자의 맨 앞자리가 같은3자리 숫자 abc와 cde가 있을 때, 공통되는 숫자를 지워 ab, de를 만들었을 때 abc / cde = ab / de인 수의 순서쌍을 모두 구하는 문제이다.

 

abc를 100 ~ 999, cde도 100 ~ 999 사이의 모든 경우를 확인해보면 된다.

 

 

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

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

    for(int i=100; i<=999; i++)
        for(int j=100; j<=999; j++) {
            if(i % 10 != j / 100) continue;
            if(i % 111 == 0) continue;

            int a = i, b = j, c = i / 10, d = j % 100;

            if(a * d == b * c)
                cout << a << " / " << b << " = " << c << " / " << d << "\n";
        }
}

 

 

백준 BOJ 9664번 : NASLJEDSTVO

문제 난이도 : Bronze III

알고리즘 분류 : 브루트포스

 

몇 개의 물건 중에서 1/N만큼을 (내림) 가져가고 남은 것이 M개일 때, 원래 있었던 것으로 가능한 최소/최대 물건의 수를 구하는 문제이다.

 

내림 처리를 하고 가져갔기 때문에 역으로 연산하기가 쉽지 않다.

따라서 범위를 넉넉하게 잡아서 x - x/N = M이면 x에 대해 최대, 최소를 갱신해주면 된다.

 

 

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

    int Min = INT_MAX, Max = INT_MIN;

    for(int i=1; i<=1e3; i++) {
        if(i - i/N == M) {
            Min = min(Min, i);
            Max = max(Max, i);
        }
    }

    cout << Min << " " << Max << "\n";
}

 

 

백준 BOJ 19751번 : Fractification

문제 난이도 : Bronze III

알고리즘 분류 : 브루트포스

 

네 정수 a, b, c, d가 주어질 때 a/b + c/d가 최소가 되도록 값들을 적절히 swap하는 문제이다.

 

next_permutation 함수를 이용하여 4! 가지의 경우를 모두 비교해보면 된다.

실수 연산에서 오차가 발생하지 않을까 했는데 다행히 극악의 테스트케이스는 없는 것 같다.

 

 

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

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

    vector<double> v(4);

    for(int i=0; i<4; i++) cin >> v[i];

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

    vector<double> u;
    double Min = INT_MAX;

    while(true) {
        if(v[0] / v[1] + v[2] / v[3] < Min) {
            Min = v[0] / v[1] + v[2] / v[3];

            u = v;
        }

        if(!next_permutation(v.begin(), v.end())) break;
    }

    for(int i=0; i<4; i++) cout << (int)u[i] << " ";
    cout << "\n";
}

 

 

백준 BOJ 24348번 : ИЗРАЗ

문제 난이도 : Bronze III

알고리즘 분류 : 브루트포스

 

3개의 수가 주어질 때, +, -, * 를 최대 한 번만 사용하여 만들 수 있는 최댓값을 구하는 문제이다. (세 수의 순서를 바꿔도 된다.)

 

next_permutation을 이용하여 세 수의 순서를 바꾸고, 주어지는 수가 0 이상이므로 +와 *만을 가지고 모든 조합을 비교해보면 된다.

 

 

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

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

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

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

    int ans = 0;

    while(true) {
        ans = max(ans, v[0] + v[1] * v[2]);
        ans = max(ans, v[0] * v[1] + v[2]);

        if(!next_permutation(v.begin(), v.end())) break;
    }

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