C++ 알고리즘 구현 코드 모음 정리 자료

개요

알고리즘 사이트 백준(BOJ, Baekjoon Online Judge)에서 약 5100문제 이상을 풀이하며 자주 사용되는 알고리즘들을 모두 정형화된 코드로 정리하였습니다.

(최종 업데이트 날짜: 2024년 4월 29일)

 

각 알고리즘은 BOJ의 문제 난이도 투표 사이트인 Solved.ac의 티어(난이도) 오름차순으로 정리하였습니다.

 

 

알고리즘 모음

무작위화 (난수 생성) (난이도를 매길 수 없음)

- 0 ~ 99 사이의 5개의 난수 출력하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    mt19937 mt((unsigned int)time(NULL));
    uniform_int_distribution<int> uid(0, INT_MAX);
    auto rd = bind(uid, mt);

    for(int i=0; i<5; i++) cout << rd() % 100 << "\n";
}

 

약수의 개수 구하기 (O(N^(1/2)) (Silver V)

 - N의 약수의 개수 cnt 출력

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    int cnt = 0;

    for(int i=1; i<=sqrt(N); i++) {
        if(N % i == 0) {
            if(N / i == i) cnt++;
            else cnt += 2;
        }
    }

    cout << cnt << "\n";
}

 

문자열의 부분 문자열 개수 찾기 (Silver V)

- 문자열 a에 포함된 문자열 b의 개수 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    string a, b; cin >> a >> b;

    int cnt = 0;

    for(int i=0; i<a.length(); i++)
        if(a.find(b, i) == i) cnt++;

    cout << cnt << "\n";
}

 

에라토스테네스의 체 (Silver IV)

- 1 ~ 1e5 사이의 소수 미리 담아두기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int Max = 1e5 + 1;

    vector<bool> isp(Max, true);
    isp[0] = isp[1] = false;

    for(int i=2; i*i<Max; i++)
        for(int j=2; i*j<Max; j++) isp[i*j] = false;

    vector<int> p;
    for(int i=2; i<Max; i++)
        if(isp[i]) p.push_back(i);
}

 

정수 제곱근 구하기 (Silver IV)

- x^2 >= N인 가장 작은 x를 구하는 코드

- 즉, x^2 = N이면 N은 제곱수인 것이고 그렇지 않다면 N은 제곱수가 아님 

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    int l = 0, r = LLONG_MAX;
    while(l <= r) {
        int m = (l + r)/2;

        unsigned long long mm = m * m;

        if(mm >= N) r = m - 1;
        else l = m + 1;
    }

    cout << l << "\n";
}

 

모든 수의 약수의 개수 또는 약수의 합 한 번에 구하기 (Silver III)

- 에라토스테네스의 체와 비슷하게 구현하여 어떤 수의 모든 배수에 더해주는 방식

 

- 약수의 개수 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    vector<int> v(1e6 + 1);

    for(int i=1; i<=1e6; i++)
        for(int j=i; j<=1e6; j+=i) v[j]++;
}

 

- 약수의 합 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    vector<int> v(1e6 + 1);

    for(int i=1; i<=1e6; i++)
        for(int j=i*2; j<=1e6; j+=i) v[j] += i;
}

 

1차원 배열에서의 최대 구간 합 (+ 왼쪽, 오른쪽) (Silver II)

 - 1차원 배열에 대해 최대 구간 합과, 그 구간의 왼쪽과 오른쪽 인덱스 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    int sum = 0, Min = 0, ans = INT_MIN;
    int l = 1, r = 1, ltmp = 1;

    for(int i=0; i<N; i++) {
        sum += v[i];

        if(sum - Min > ans) {
            ans = sum - Min;
            l = ltmp + 1;
            r = i + 1;
        }

        if(sum < Min) {
            Min = sum;
            ltmp = i + 1;
        }
    }

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

 

우선순위 큐 pair + cmp 함수 정의 (Silver II)

- pair<int, int>를 우선순위 큐에 넣기

- 정렬 기준은 second/first 값이 큰 순서 (우선순위 큐에서는 sort의 cmp와 cmp 부등호가 반대로 되어야 한다.)

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

struct cmp {
    bool operator()(pair<int, int> a, pair<int, int> b) {
        return (double)a.second/a.first < (double)b.second/b.first;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq;

    while(K--) {
        int a, b; cin >> a >> b;

        pq.push({a, b});
    }

    while(!pq.empty()) {
        cout << pq.top().first << " " << pq.top().second << "\n";

        pq.pop();
    }
}

 

DFS (덩어리 세기) (Silver II)

 - N x N grid에서 *로 이루어진 덩어리 개수 세기

 

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

const int MAX = 1001;

int N;
char v[MAX][MAX];
bool vis[MAX][MAX];

void f(int x, int y) {
    vis[x][y] = true;

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

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

        if(nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
        if(v[nx][ny] != '*' || vis[nx][ny]) continue;

        f(nx, ny);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N;
    cin.ignore();

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) cin >> v[i][j];
        cin.ignore();
    }

    memset(vis, false, sizeof(vis));

    int ans = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            if(v[i][j] == '*' && !vis[i][j]) {
                f(i, j);
                ans++;
            }

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

 

BFS (Silver II)

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    vector<vector<int>> v(N, vector<int>(M));

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

    vector<vector<bool>> vis(N, vector<bool>(M));
    int ans = 0;

    for(int i=0; i<N; i++)
        for(int j=0; j<M; j++) {
            if(v[i][j] != 0 || vis[i][j]) continue;

            queue<pair<int, int>> q; q.push({i, j});

            while(!q.empty()) {
                int x = q.front().first;
                int y = q.front().second; q.pop();

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

                for(int k=0; k<4; k++) {
                    int nx = (x + dx[k] + N) % N;
                    int ny = (y + dy[k] + M) % M;

                    if(v[nx][ny] != 0 || vis[nx][ny]) continue;

                    vis[nx][ny] = true;
                    q.push({nx, ny});
                }
            }

            ans++;
        }

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

 

값 / 좌표 압축 (Silver II)

 - v에 좌표를 입력받고, u로 정렬 및 값의 변환을 수행하며 w에 압축된 값이 저장됨

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    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();

    for(int i=0; i<N; i++) cout << w[i] << " ";
}

 

조합 (Combination) (Silver I)

 - 입력되는 N, K에 대해 C(N, K)를 출력 (DP)

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

int dp[1001][1001] = {};
int mod = (int)(1e4 + 7);

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    for(int i=0; i<=N; i++) dp[i][0] = 1;
    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % mod;

    cout << dp[N][M] << "\n";
}

 

- 결과값이 자료형 범위를 안 넘어간다는 가정하에 작은 범위 내에서 직접 계산

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    M = min(M, N - M);

    int ans = 1;

    for(int i=1; i<=M; i++) {
        ans *= N;
        ans /= i;

        N--;
    }

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

 

연속 부분 최대 합 (DP) (Silver I)

- N개의 수가 주어질 때 그 중 연속한 부분 수열의 합의 최댓값 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    int ans = v[0];

    for(int i=1; i<N; i++) {
        if(v[i] + v[i-1] > v[i]) v[i] += v[i-1];
        ans = max(ans, v[i]);
    }

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

 

삼분 탐색 (Silver I)

- l ~ r 범위에서 함수 f의 최솟값 구하기

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

double f(vector<double> v, vector<double> u, double m) {
    double sum = 0;

    for(int i=0; i<v.size(); i++)
        sum += abs(v[i] * m - u[i]);

    return sum;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cout << fixed;
    cout.precision(9);

    int N; cin >> N;

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

    double l = 0, r = 1e6;
    double Min = INT_MAX, tr = 1e3;

    while(tr--) {
        double m1 = (l*2 + r) / 3;
        double m2 = (l + r*2) / 3;

        double a = f(v, u, m1);
        double b = f(v, u, m2);

        if(tr == 0) cout << a << "\n";
        else if(a > b) l = m1;
        else r = m2;
    }
}

 

다익스트라 (= 데이크스트라) (우선순위 큐) (Gold V)

- 노드 수 N, 간선 수 M

- M개의 줄에 대해 (시작점, 끝점, 거리) 입력

- 1번 노드에서 N번 노드까지의 최단 거리

 

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

typedef pair<int, int> p;
vector<vector<p>> adj;
vector<int> dis;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    adj.resize(N+1);
    dis.resize(N+1, INT_MAX);

    while(M--) {
        int a, b, c; cin >> a >> b >> c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }

    int sour, dest; cin >> sour >> dest;
    
    dis[sour] = 0;

    priority_queue<p, vector<p>, greater<p>> pq; // <dis, node>
    pq.push({0, sour});

    while(!pq.empty()) {
        int dis1 = pq.top().first;
        int cur = pq.top().second;
        pq.pop();

        if(dis[cur] < dis1) continue;

        for(int i=0; i<adj[cur].size(); i++) {
            int nex = adj[cur][i].first;
            int dis2 = adj[cur][i].second;

            if(dis1 + dis2 < dis[nex]) {
                dis[nex] = dis1 + dis2;
                pq.push({dis[nex], nex});
            }
        }
    }

    cout << dis[dest] << "\n";
}

 

배낭 문제 : N개 물건으로 무게 합이 M 이하면서 가지는 최대 가치 (Gold V)

- 물건 수 N, 무게 제한 M

- v[i]에는 i번째 물건의 <무게, 가치>를 저장

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

vector<vector<int>> dp;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    vector<pair<int, int>> v(N+1); // <weight, value>
    for(int i=1; i<=N; i++)
        cin >> v[i].first >> v[i].second;

    dp.resize(N+1, vector<int>(M+1));

    for(int i=1; i<=N; i++)
        for(int j=1; j<=M; j++) {
            dp[i][j] = dp[i-1][j];
            if(v[i].first <= j)
                dp[i][j] = max(dp[i][j], dp[i-1][j - v[i].first] + v[i].second);
        }

    cout << dp[N][M] << "\n";
}

 

배낭 문제 : N개 동전으로 M원 만드는 조합 수 (Gold V)

 - N개 동전의 가치 v[i] (정렬 필요 없음)

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    int M; cin >> M;

    vector<int> dp(M+1); dp[0] = 1;
    for(int i=0; i<N; i++)
        for(int j=v[i]; j<=M; j++) dp[j] += dp[j - v[i]];

    cout << dp[M] << "\n";
}

 

분리 집합 (Disjoint Set, Union Find) (Gold IV)

- N 이하의 원소들과 M개의 쿼리

- 쿼리 0 a b는 a가 포함된 집합과 b가 포함된 집합을 합침

- 쿼리 1 a b는 a가 포함된 집합과 b가 포함된 집합이 같은지 검사

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

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

    while(M--) {
        int Q, a, b; cin >> Q >> a >> b;

        if(Q == 0) {
            if(f(a) != f(b)) v[f(a)] = f(b);
        }
        else if(Q == 1) {
            if(f(a) == f(b)) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

 

최소 스패닝 트리 (MST) (Gold IV)

- 주어진 Edge들 중에서 일부를 선택하여 만들 수 있는 최소 가중치 합을 가지는 트리

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

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

bool cmp(s x, s y) { return x.c < y.c; }

vector<int> v;

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    vector<s> adj(M);

    for(int i=0; i<M; i++)
        cin >> adj[i].a >> adj[i].b >> adj[i].c;

    sort(adj.begin(), adj.end(), cmp);

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

    int ans = 0, cnt = 0;

    for(int i=0; i<adj.size(); i++) {
        int a = adj[i].a, b = adj[i].b, c = adj[i].c;

        if(f(a) == f(b)) continue;

        v[f(a)] = f(b);

        ans += c;
        cnt++;

        if(cnt == N-1) break;
    }

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

 

분할 정복을 이용한 거듭 제곱 (Gold IV)

- N번째 피보나치 수

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

typedef vector<vector<int>> mat;
int mod = 1e9;

mat f(mat& v, mat& u) {
    int N = 2;
    mat w(N, vector<int>(N));

    for(int i=0; i<v.size(); i++)
        for(int j=0; j<u[0].size(); j++)
            for(int k=0; k<v[0].size(); k++)
                w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;

    return w;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    mat mul(2, vector<int>(2));
    for(int i=0; i<2; i++) mul[i][i] = 1;

    mat ba(2, vector<int>(2));
    ba = {{1, 1}, {1, 0}};

    while(N > 0) {
        if(N % 2 == 1) mul = f(mul, ba);

        ba = f(ba, ba);
        N /= 2;
    }

    cout << mul[0][1] << "\n";
}

 

- 행렬 거듭 제곱 (N x N 행렬의 M 제곱)

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

typedef vector<vector<int>> mat;
int N, mod, M;

mat f(mat& v, mat& u) {
    mat w(N, vector<int>(N));

    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            for(int k=0; k<N; k++)
                w[i][j] = (w[i][j] + v[i][k] * u[k][j]) % mod;

    return w;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    while(true) {
        cin >> N >> mod >> M;
        if(N == 0 && mod == 0 && M == 0) break;

        mat mul(N, vector<int>(N));
        for(int i=0; i<N; i++) mul[i][i] = 1;

        mat bas(N, vector<int>(N));

        for(int i=0; i<N; i++)
            for(int j=0; j<N; j++) cin >> bas[i][j];

        while(M > 0) {
            if(M % 2 == 1) mul = f(mul, bas);

            bas = f(bas, bas);
            M /= 2;
        }

        for(int i=0; i<mul.size(); i++) {
            for(int j=0; j<mul[0].size(); j++) cout << mul[i][j] << " ";

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

 

중간에서 만나기 (Meet in the middle) (Gold IV)

- N개의 원소를 합하여 M이 되는 경우의 수 구하기 (N ≤ 40)

- M이 0인 경우 하나도 선택하지 않는 경우를 포함하는지 안하는지 문제 조건 체크하기

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

int N, M;
vector<int> v, u, w;

void f(int idx, int sum) {
    if(idx == N/2) {
        u.push_back(sum);
        return;
    }

    f(idx + 1, sum);
    f(idx + 1, sum + v[idx]);
}

void g(int idx, int sum) {
    if(idx == N) {
        w.push_back(sum);
        return;
    }

    g(idx + 1, sum);
    g(idx + 1, sum + v[idx]);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cin >> N >> M;

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

    f(0, 0);
    g(N/2, 0);

    sort(u.begin(), u.end());
    sort(w.begin(), w.end());

    int ans = 0;

    for(int i=0; i<u.size(); i++)
        ans += upper_bound(w.begin(), w.end(), M - u[i]) - lower_bound(w.begin(), w.end(), M - u[i]);

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

 

순열 사이클 분할 (Gold IV)

- 순열의 사이클 개수와 주기 구하기

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int T; T = 1;

    while(T--) {
        int N; cin >> N;

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

        vector<bool> vis(N+1);
        int cycle = 0, per = 1;

        for(int i=1; i<=N; i++) {
            if(vis[i]) continue;

            int cnt = 0, x = i;

            while(!vis[x]) {
                vis[x] = true;

                x = v[x];
                cnt++;
            }

            per = per * cnt / __gcd(per, cnt);
            cycle++;
        }

        cout << cycle << " " << per << "\n";
    }
}

 

트라이 (Gold IV)

- 문자열을 효율적으로 저장하는 자료구조

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

const int chsize = 26;
int toIdx(char ch) { return ch - 'a'; }

struct trie {
    trie *adj[chsize]; bool isEnd;
    trie() : adj(), isEnd(false) {}

    void add(string &str, int idx = 0) {
        if(idx == str.length()-1) {
            isEnd = true;
            return;
        }

        int nex = toIdx(str[idx]);
        if(adj[nex] == NULL) adj[nex] = new trie;
        adj[nex]->add(str, idx+1);
    }

    bool fpre(string &str, int idx = 0) {
        if(idx == str.length()-1) return true;

        int nex = toIdx(str[idx]);
        if(adj[nex] == NULL) return false;
        return adj[nex]->fpre(str, idx+1);
    }

    bool ftot(string &str, int idx = 0) {
        if(idx == str.length()-1) {
            if(isEnd) return true;
            else return false;
        }

        int nex = toIdx(str[idx]);
        if(adj[nex] == NULL) return false;
        return adj[nex]->ftot(str, idx+1);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    trie v;

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

        v.add(str);
    }

    int ans = 0;

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

        if(v.fpre(str)) ans++;
    }

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

 

0-1 BFS (Gold IV)

- 모든 간선의 가중치가 0 또는 1일 때 사용 가능한 O(V + E) 알고리즘

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

struct s { int x, y; };

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    vector<vector<char>> v(N, vector<char>(M));

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

    deque<s> d;
    d.push_back({0, 0});

    vector<vector<int>> dis(N, vector<int>(M, INT_MAX));
    dis[0][0] = 0;

    while(!d.empty()) {
        int x = d.front().x, y = d.front().y;
        d.pop_front();

        if(x == N-1 && y == M-1) {
            cout << dis[x][y] << "\n";
            break;
        }

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

        for(int i=0; i<4; i++) {
            int nx = x + dx[i], ny = y + dy[i];

            if(nx < 0 || ny < 0 || nx >= N || ny >= M) continue;
            if(dis[nx][ny] != INT_MAX) continue;

            if(v[nx][ny] == '0') {
                d.push_front({nx, ny});
                dis[nx][ny] = dis[x][y];
            }
            else {
                d.push_back({nx, ny});
                dis[nx][ny] = dis[x][y] + 1;
            }
        }
    }
}

 

- 단순 그래프에서의 활용 예시

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, sour, dest; cin >> N >> sour >> dest;

    vector<vector<int>> adj(N+1);
    for(int i=1; i<=N; i++) {
        int M; cin >> M;

        while(M--) {
            int x; cin >> x;

            adj[i].push_back(x);
        }
    }

    deque<int> d; d.push_back(sour);
    vector<int> dis(N+1, INT_MAX); dis[sour] = 0;

    while(!d.empty()) {
        int x = d.front(); d.pop_front();

        if(x == dest) break;

        for(int i=0; i<adj[x].size(); i++) {
            int y = adj[x][i];

            if(dis[y] != INT_MAX) continue;

            if(i == 0) {
                d.push_front(y);
                dis[y] = dis[x];
            }
            else {
                d.push_back(y);
                dis[y] = dis[x] + 1;
            }
        }
    }

    if(dis[dest] != INT_MAX) cout << dis[dest] << "\n";
    else cout << -1 << "\n";
}

 

위상 정렬 (Gold III)

- N개의 작업, M개의 전후 순서가 결정되어 있는 쌍

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    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;

    for(int i=1; i<=N; i++)
        if(deg[i] == 0) q.push(i);

    vector<int> ord;

    while(!q.empty()) {
        int x = q.front();
        q.pop();

        ord.push_back(x);

        for(int i=0; i<adj[x].size(); i++) {
            int y = adj[x][i];

            deg[y]--;

            if(deg[y] == 0) q.push(y);
        }
    }

    for(int i=0; i<ord.size(); i++) cout << ord[i] << " ";
    cout << "\n";
}

 

카탈란 수 (Gold III)

- dp[i] : i번째 카탈란 수

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    int dp[10001] = {1, 1};

    for(int i=2; i<=N; i++)
        for(int j=0; j<i; j++) dp[i] = (dp[i] + dp[j] * dp[i-1-j]) % (int)(1e9 + 7);

    cout << dp[N] << "\n";
}

 

빠른 에라토스테네스의 체 (Gold III)

- 1부터 10^8까지의 소수를 벡터 v에 저장

- 위의 에라토스테네스의 체보다 빠른 코드

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int Max = 1e8 + 1;
    vector<bool> p(Max);

    vector<int> v;
    v.push_back(2);

    for(int i=3; i<Max; i+=2) {
        if(p[i]) continue;

        v.push_back(i);

        for(int j=i; j<Max; j+=i*2) p[j] = true;
    }
}

 

세그먼트 트리 (Gold I)

- 다양한 함수가 구현된 세그먼트 트리 구조체

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

struct segmentTree {
    vector<int> v;

    int init(int n, int b, int e, vector<int> &u) {
        if(b == e) return v[n] = u[b];

        return v[n] = init(n*2, b, (b+e)/2, u)
                       + init(n*2 + 1, (b+e)/2 + 1, e, u);
    }

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

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

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

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

        return sum(n*2, b, (b+e)/2, l, r)
                + sum(n*2 + 1, (b+e)/2 + 1, e, l, r);
    }

    int kth(int n, int b, int e, int ran) {
        if(b == e) return b;

        if(ran <= v[n*2]) return kth(n*2, b, (b+e)/2, ran);
        else return kth(n*2+1, (b+e)/2+1, e, ran-v[n*2]);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    segmentTree f;
    f.v.resize(1e6*4);

    int N; cin >> N;

    while(N--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int a; cin >> a;

            int kth = f.kth(1, 1, 1e6, a);

            cout << kth << "\n";

            f.upd(1, 1, 1e6, kth, -1);
        }
        else if(Q == 2) {
            int a, b; cin >> a >> b;

            f.upd(1, 1, 1e6, a, b);
        }
    }
}

 

↓ 세그먼트 트리 문제들의 풀이 코드 모음

백준(BOJ) 세그먼트 트리 문제 풀이 모음 (Segment Tree)

 

트리에서 인접하지 않는 노드들 중 최대 가중치 구하기 (Gold I)

- 트리에서 인접하지 않는 노드들 중에서 일부를 선택하여 각 노드들의 가중치의 합이 최대가 되도록 할 때, 그 가중치와 그 때의 선택된 노드들의 번호

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

vector<int> v, u;
vector<vector<int>> adj, dp;
vector<bool> vis;

void dfs(int x) {
    vis[x] = true;

    dp[x][0] = 0;
    dp[x][1] = v[x];

    for(int y : adj[x]) {
        if(vis[y]) continue;

        dfs(y);

        dp[x][0] += max(dp[y][0], dp[y][1]);
        dp[x][1] += dp[y][0];
    }
}

void get(int x, int pre) {
    if(dp[x][1] > dp[x][0] && !vis[pre]) {
        u.push_back(x);
        vis[x] = true;
    }

    for(int y : adj[x])
        if(y != pre) get(y, x);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    adj.resize(N+1);
    for(int i=1; i<=N-1; i++) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

    dp.resize(N+1, vector<int>(2));
    vis.resize(N+1);

    dfs(1);

    cout << max(dp[1][0], dp[1][1]) << "\n";

    vis.clear();
    vis.resize(N+1);

    get(1, 0);

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

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

 

RREF (가우스 소거법, Gaussian Elimination) (Gold I)

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    vector<vector<double>> v(N, vector<double>(M));

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

    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            double d = v[i][i], c = v[j][i] / v[i][i];

            for(int k=0; k<M; k++) {
                if(j == i) v[j][k] /= d;
                else v[j][k] -= c * v[i][k];
            }
        }
    }

    for(int i=0; i<N; i++) {
        for(int j=0; j<M; j++) cout << v[i][j] << " ";
        cout << "\n";
    }
}

 

가장 긴 증가하는 부분 수열 (LIS) (Platinum V)

- 정수 개수 N개

- N개의 수가 입력됨

- 가장 긴 증가하는 부분 수열의 길이와 그 원소를 출력

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

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    vector<int> u;
    u.push_back(v[0]);

    int cnt = 0;

    vector<pair<int, int>> dp(N);
    dp[0] = {v[0], 0};

    for(int i=1; i<N; i++) {
        if(v[i] > u.back()) {
            u.push_back(v[i]);
            cnt++;

            dp[i] = {v[i], cnt};
        }
        else {
            int x = lower_bound(u.begin(), u.end(), v[i]) - u.begin();
            u[x] = v[i];

            dp[i] = {v[i], x};
        }
    }

    cout << cnt + 1 << "\n";

    vector<int> ans;

    for(int i=N-1; i>=0; i--)
        if(cnt == dp[i].second) {
            ans.push_back(dp[i].first);
            cnt--;
        }

    for(int i=ans.size()-1; i>=0; i--) cout << ans[i] << " ";
    cout << "\n";
}

 

컨벡스 헐 (Convex Hull, 볼록 껍질) (Platinum V)

- 특정한 순서 없이 N개의 좌표가 주어짐

- 볼록 껍질을 구성하는 점의 개수와 좌표 출력

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

struct p { double x, y; };
vector<p> v;

double ccw(p a, p b, p c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool cmp(p a, p b) {
    double x = ccw(v[0], a, b);

    if(x != 0) return x > 0;
    else if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;

    for(int i=1; i<v.size(); i++)
        if(v[i].x < v[0].x || (v[i].x == v[0].x && v[i].y < v[0].y)) swap(v[i], v[0]);

    sort(v.begin()+1, v.end(), cmp);

    stack<p> s;

    s.push(v[0]);
    s.push(v[1]);

    for(int i=2; i<N; i++) {
        while(s.size() >= 2) {
            p a = s.top(); s.pop();
            p b = s.top();

            if(ccw(b, a, v[i]) > 0) {
                s.push(a);
                break;
            }
        }
        s.push(v[i]);
    }

    v.clear();

    while(!s.empty()) {
        v.push_back(s.top());
        s.pop();
    }

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

    cout << v.size() << "\n";

    for(int i=0; i<v.size(); i++)
        cout << v[i].x << " " << v[i].y << "\n";
}

 

최소 공통 조상 (LCA, log 시간 알고리즘) (Platinum V)

- N개의 노드를 가지는 트리 (N-1개의 간선 입력)

- M개의 쿼리 (a, b)에 대해 a, b의 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);
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    adj.resize(N+1);

    for(int i=0; i<N-1; i++) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
        adj[b].push_back(a);
    }

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

    int M; cin >> M;

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

 

강한 결합 요소, 강한 연결 요소 (SCC, Strongly Connected Component) (Platinum V)

- N개의 노드와 M개의 간선으로 주어진 그래프

- scc 벡터의 각 벡터에 scc 원소들을 오름차순으로 저장

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

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

        scc.push_back(v);
    }

    return tmp;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    adj.resize(N+1);

    while(M--) {
        int a, b; cin >> a >> b;

        adj[a].push_back(b);
    }

    nnum.resize(N+1);
    cnum.resize(N+1);
    ch.resize(N+1);

    for(int i=1; i<=N; i++)
        if(nnum[i] == 0) dfs(i);

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

    cout << scc.size() << "\n";

    for(int i=0; i<scc.size(); i++) {
        for(int j=0; j<scc[i].size(); j++) cout << scc[i][j] << " ";
        cout << -1 << "\n";
    }
}

 

- indegree = 0인 component 개수 구하는 코드 (모든 노드에 도달하기 위해서는 최소 몇 개의 시작점이 필요한 지)

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

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

        scc.push_back(v);
    }

    return tmp;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        adj.clear();
        adj.resize(N+1);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[a].push_back(b);
        }

        nnum.clear();   nnum.resize(N+1);
        cnum.clear();   cnum.resize(N+1);
        ch.clear();     ch.resize(N+1);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=1; i<=N; i++)
            if(nnum[i] == 0) dfs(i);

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

        vector<int> ind(N+1);

        for(int i=1; i<=N; i++)
            for(int j=0; j<adj[i].size(); j++) {
                int x = adj[i][j];

                if(cnum[i] != cnum[x]) ind[cnum[x]]++;
            }

        int ans = 0;
        for(int i=1; i<=ccnt; i++)
            if(ind[i] == 0) ans++;

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

 

느리게 갱신되는 세그먼트 트리 (Lazy Propagation) (Platinum IV)

- 1번 쿼리에 대해 구간 전체의 원소 각각에 +diff의 연산

- 2번 쿼리에 대해 구간 전체의 원소의 합을 출력

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

vector<int> v, u, w; // v : array, u : tree, w : lazy

int init(int n, int b, int e) {
    if(b == e) return u[n] = v[b];

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

    return u[n] = lv + rv;
}

void lazy(int n, int b, int e) {
    if(w[n] == 0) return;

    u[n] += (e-b+1)*w[n];

    if(b != e) {
        w[n*2] += w[n];
        w[n*2 + 1] += w[n];
    }

    w[n] = 0;
}

int upd(int n, int b, int  e, int l, int r, int diff) {
    lazy(n, b, e);

    if(r < b || e < l) return u[n];

    if(l <= b && e <= r) {
        w[n] += diff;
        lazy(n, b, e);
        return u[n];
    }

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

    return u[n] = lv + rv;
}

int query(int n, int b, int e, int l, int r) {
    lazy(n, b, e);

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

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

    return lv + rv;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

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

    u.resize(N*4);
    init(1, 1, N);

    w.resize(N*4);

    M += K;
    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int a, b, c; cin >> a >> b >> c;
            upd(1, 1, N, a, b, c);
        }
        else if(Q == 2) {
            int a, b; cin >> a >> b;
            cout << query(1, 1, N, a, b) << "\n";
        }
    }
}

 

최대 유량 (Max Flow) (Platinum IV)

- 간선을 push_back 해주되 ord에 서로 몇 번째인지를 저장하여 역방향 간선을 O(1)에 찾을 수 있도록 구현

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

struct MF {
    struct se { int num, cap, ord; };
    vector<vector<se>> adj;

    void edge(int a, int b, int c) {
        adj[a].push_back({b, c, adj[b].size()});
        adj[b].push_back({a, 0, adj[a].size()-1});
    }

    int sz, sour, sink;
    vector<int> lv, idx;

    void init(int sz_) { sz = sz_; adj.resize(sz); }

    bool bfs() {
        lv.clear(); lv.resize(sz, -1); lv[sour] = 0;

        queue<int> q; q.push(sour);

        while(!q.empty()) {
            int x = q.front(); q.pop();

            for(auto e : adj[x]) {
                int y = e.num, cap = e.cap;

                if(lv[y] != -1 || cap == 0) continue;

                lv[y] = lv[x] + 1;
                q.push(y);
            }
        }

        if(lv[sink] != -1) return true;
        else return false;
    }

    int dfs(int x, int flo) {
        if(x == sink) return flo;

        for(int &i=idx[x]; i<adj[x].size(); i++) {
            int y = adj[x][i].num, cap = adj[x][i].cap;

            if(lv[x] + 1 != lv[y] || cap == 0) continue;

            int sfl = dfs(y, min(flo, cap));

            if(sfl == 0) continue;

            adj[x][i].cap -= sfl;
            adj[y][adj[x][i].ord].cap += sfl;

            return sfl;
        }

        return 0;
    }

    int mf(int sour_, int sink_) {
        int maxf = 0; sour = sour_, sink = sink_;

        while(bfs()) {
            idx.clear(); idx.resize(sz);

            while(true) {
                int sfl = dfs(sour, INT_MAX);

                if(sfl == 0) break;

                maxf += sfl;
            }
        }

        return maxf;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    MF f; f.init(N+M+4);

    int sour = N+M+1, sink = N+M+2, ext = N+M+3;

    f.edge(sour, ext, K);

    for(int i=1; i<=N; i++) {
        f.edge(sour, i, 1);
        f.edge(ext, i, 1);

        int L; cin >> L;

        while(L--) {
            int x; cin >> x;

            f.edge(i, N+x, 1);
        }
    }

    for(int i=1; i<=M; i++) f.edge(N+i, sink, 1);

    cout << f.mf(sour, sink) << "\n";
}

 

- 간선을 push_back 해주되 역방향 간선을 포인터로 연결하여 O(1)에 찾을 수 있도록 구현

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

struct MF {
    struct se {
        int num, cap; se *oth;
        se(int num, int cap) : num(num), cap(cap) {}
    };
    vector<vector<se *>> adj;

    void edge(int a, int b, int cap) {
        se *fow = new se(b, cap);
        se *rev = new se(a, 0);

        fow->oth = rev;
        rev->oth = fow;

        adj[a].push_back(fow);
        adj[b].push_back(rev);
    }

    int sz, sour, sink;
    vector<int> lv, idx;

    void init(int sz_) { sz = sz_; adj.resize(sz); }

    bool bfs() {
        lv.clear(); lv.resize(sz, -1); lv[sour] = 0;

        queue<int> q; q.push(sour);

        while(!q.empty()) {
            int x = q.front(); q.pop();

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i]->num;

                if(lv[y] != -1 || adj[x][i]->cap == 0) continue;

                lv[y] = lv[x] + 1;
                q.push(y);
            }
        }

        if(lv[sink] != -1) return true;
        else return false;
    }

    int dfs(int x, int flo) {
        if(x == sink) return flo;

        for(int &i=idx[x]; i<adj[x].size(); i++) {
            int y = adj[x][i]->num, cap = adj[x][i]->cap;

            if(lv[x] + 1 != lv[y] || cap == 0) continue;

            int sfl = dfs(y, min(flo, cap));

            if(sfl == 0) continue;

            adj[x][i]->cap -= sfl;
            adj[x][i]->oth->cap += sfl;

            return sfl;
        }

        return 0;
    }

    int mf(int sour_, int sink_) {
        int maxf = 0; sour = sour_, sink = sink_;

        while(bfs()) {
            idx.clear(); idx.resize(sz);

            while(true) {
                int sfl = dfs(sour, INT_MAX);

                if(sfl == 0) break;

                maxf += sfl;
            }
        }

        return maxf;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    MF f; f.init(N+M+4);

    int sour = N+M+1, sink = N+M+2, ext = N+M+3;

    f.edge(sour, ext, K);

    for(int i=1; i<=N; i++) {
        f.edge(sour, i, 1);
        f.edge(ext, i, 1);

        int L; cin >> L;

        while(L--) {
            int x; cin >> x;

            f.edge(i, N+x, 1);
        }
    }

    for(int i=1; i<=M; i++) f.edge(N+i, sink, 1);

    cout << f.mf(sour, sink) << "\n";
}

 

- capacity, flow를 N x N 배열로 선언하여 구현 ([a][b]의 역방향은 [b][a]로 O(1)에 접근 가능)

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

struct MF {
    int sz, sour, sink;
    vector<vector<int>> adj, cap, flo;
    vector<int> lv, idx;

    void init(int sz_) {
        sz = sz_;

        adj.resize(sz);
        cap.resize(sz, vector<int>(sz));
        flo.resize(sz, vector<int>(sz));

        lv.resize(sz), idx.resize(sz);
    }

    void edge(int a, int b, int c) {
        adj[a].push_back(b);
        adj[b].push_back(a);
        cap[a][b] = c;
    }

    bool bfs() {
        lv.clear(); lv.resize(sz, -1); lv[sour] = 0;

        queue<int> q; q.push(sour);

        while(!q.empty()) {
            int x = q.front(); q.pop();

            for(auto y : adj[x]) {
                if(lv[y] != -1 || cap[x][y] - flo[x][y] == 0) continue;

                lv[y] = lv[x] + 1;
                q.push(y);
            }
        }

        if(lv[sink] != -1) return true;
        else return false;
    }

    int dfs(int x, int tot) {
        if(x == sink) return tot;

        for(int &i=idx[x]; i<adj[x].size(); i++) {
            int y = adj[x][i];

            if(lv[y] != lv[x] + 1 || cap[x][y] - flo[x][y] == 0) continue;

            int sfl = dfs(y, min(tot, cap[x][y] - flo[x][y]));

            if(sfl == 0) continue;

            flo[x][y] += sfl;
            flo[y][x] -= sfl;

            return sfl;
        }

        return 0;
    }

    int mf(int sour_, int sink_) {
        sour = sour_, sink = sink_;

        int mxf = 0;

        while(bfs()) {
            idx.clear(); idx.resize(sz);

            while(true) {
                int flo = dfs(sour, INT_MAX);

                if(flo == 0) break;

                mxf += flo;
            }
        }

        return mxf;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    MF f; f.init(N+M+4);

    int sour = N+M+1, sink = N+M+2, ext = N+M+3;

    f.edge(sour, ext, K);

    for(int i=1; i<=N; i++) {
        f.edge(sour, i, 1);
        f.edge(ext, i, 1);

        int L; cin >> L;

        while(L--) {
            int x; cin >> x;

            f.edge(i, N+x, 1);
        }
    }

    for(int i=1; i<=M; i++) f.edge(N+i, sink, 1);

    cout << f.mf(sour, sink) << "\n";
}

 

회전하는 캘리퍼스 : 가장 먼 두 점 (Platinum IV)

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

struct P { int x, y; };

P operator-(P a, P b) {
    P c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}

vector<P> v;

double ccw(P a, P b, P c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool cmp(P &a, P &b) {
    double x = ccw(v[0], a, b);
    if(x != 0) return x > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;

    for(int i=1; i<N; i++)
        if(v[i].y < v[0].y || (v[i].y == v[0].y && v[i].x < v[0].x)) swap(v[i], v[0]);

    sort(v.begin()+1, v.end(), cmp);

    stack<P> s;

    s.push(v[0]);
    s.push(v[1]);

    for(int i=2; i<N; i++) {
        while(s.size() >= 2) {
            P a = s.top(); s.pop();
            P b = s.top();

            if(ccw(b, a, v[i]) > 0) {
                s.push(a);
                break;
            }
        }
        s.push(v[i]);
    }

    vector<P> u(s.size());
    while(!s.empty()) {
        u[s.size()-1] = s.top();
        s.pop();
    }

    int l = 0, r = 0;
    for(int i=0; i<u.size(); i++) {
        if(u[i].x < u[l].x) l = i;
        if(u[i].x > u[r].x) r = i;
    }

    double ans = sqrt(pow(u[l].x - u[r].x, 2) + pow(u[l].y - u[r].y, 2));
    P o = {0, 0};

    for(int i=0; i<u.size(); i++) {
        int nl = (l+1) % u.size();
        int nr = (r+1) % u.size();

        if(ccw(o, u[nl] - u[l], u[r] - u[nr]) > 0) l = nl;
        else r = nr;

        ans = max(ans, sqrt(pow(u[l].x - u[r].x, 2) + pow(u[l].y - u[r].y, 2)));
    }

    cout << fixed;
    cout.precision(6);

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

 

선분 교차 판정 (Platinum IV)

- 두 선분의 끝 점의 좌표가 주어질 때, 두 선분의 교차 여부를 구하고, 만약 한 점에서만 교차한다면 그 좌표를 오차 범위 1e-9 이내로 구하기

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

struct s { int x, y; };

bool operator== (s a, s b) {
    if(a.x == b.x && a.y == b.y) return true;
    else return false;
}
bool operator>= (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y >= b.y)) return true;
    else return false;
}
bool operator<= (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y <= b.y)) return true;
    else return false;
}
bool operator> (s a, s b) {
    if(a.x > b.x || (a.x == b.x && a.y > b.y)) return true;
    else return false;
}
bool operator< (s a, s b) {
    if(a.x < b.x || (a.x == b.x && a.y < b.y)) return true;
    else return false;
}

int ccw(s a, s b, s c) {
    int val = a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);

    if(val == 0) return 0;
    else if(val > 0) return 1;
    else if(val < 0) return -1;
}

bool cross, overlap;
double cx, cy;

void coor(s a, s b, s c, s d) {
    double X = (a.x * b.y - a.y * b.x) * (c.x - d.x) - (a.x - b.x) * (c.x * d.y - c.y * d.x);
    double Y = (a.x * b.y - a.y * b.x) * (c.y - d.y) - (a.y - b.y) * (c.x * d.y - c.y * d.x);
    double div = (a.x - b.x) * (c.y - d.y) - (a.y - b.y) * (c.x - d.x);

    if(div == 0) {
        if(b == c && a <= c) cx = b.x, cy = b.y, overlap = false;
        else if(a == d && c <= a) cx = a.x, cy = a.y, overlap = false;
        else overlap = true;
    }
    else cx = X / div, cy = Y / div, overlap = false;
}

void inter(s a, s b, s c, s d) {
    int val1 = ccw(a, b, c) * ccw(a, b, d);
    int val2 = ccw(c, d, a) * ccw(c, d, b);

    if(val1 == 0 && val2 == 0) {
        if(a > b) swap(a, b);
        if(c > d) swap(c, d);

        if(a <= d && b >= c) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
    else {
        if(val1 <= 0 && val2 <= 0) {
            cross = true;
            coor(a, b, c, d);
        }
        else cross = false;
    }
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cout << fixed;
    cout.precision(9);
    
    int T = 1;
    
    while(T--) {
        vector<s> v(4);
        for(int i=0; i<4; i++) cin >> v[i].x >> v[i].y;

        inter(v[0], v[1], v[2], v[3]);

        if(cross) {
            cout << 1 << "\n";
            if(!overlap) cout << cx << " " << cy << "\n";
        }
        else cout << 0 << "\n";
    }
}

 

오일러 회로/경로 (Eulerian Circuit/Path) (Platinum IV)

- 그래프에서 모든 간선을 한 번씩 지나 출발점으로 돌아오는 경로 (O(E log V))

- 오일러 회로는 홀수 차수 정점이 0개, 오일러 경로는 홀수 차수 정점이 0개 또는 2개여야 한다.

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

struct segmentTree {
    vector<int> v;

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

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

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

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

        return sum(n*2, b, (b+e)/2, l, r)
                + sum(n*2 + 1, (b+e)/2 + 1, e, l, r);
    }

    int kth(int n, int b, int e, int ran) {
        if(b == e) return b;

        if(ran <= v[n*2]) return kth(n*2, b, (b+e)/2, ran);
        else return kth(n*2+1, (b+e)/2+1, e, ran-v[n*2]);
    }
};

struct EulerianPath {
    segmentTree adj[1001];

    int N, start = 0;
    stack<int> s;

    void init() {
        cin >> N;

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

            for(int j=1; j<=N; j++) {
                int x; cin >> x;

                adj[i].upd(1, 1, N, j, x);
            }
        }
    }

    bool exist() {
        int cnt = 0;

        for(int i=1; i<=N; i++) {
            int sum = adj[i].sum(1, 1, N, 1, N);

            if(sum % 2 == 1) cnt++;
            if(start == 0 && sum > 0) start = i;
        }

        if(cnt == 0 || cnt == 2) return true; // circuit, path

        return false;
    }

    void dfs(int x) {
        while(adj[x].sum(1, 1, N, 1, N) > 0) {
            int y = adj[x].kth(1, 1, N, 1);

            adj[x].upd(1, 1, N, y, -1);
            adj[y].upd(1, 1, N, x, -1);

            dfs(y);
        }

        s.push(x);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    EulerianPath f; f.init();

    if(!f.exist()) {
        cout << -1 << "\n";
        return 0;
    }

    f.dfs(f.start);

    while(!f.s.empty()) {
        cout << f.s.top() << " ";
        f.s.pop();
    }
    cout << "\n";
}

 

최소 비용 최대 유량 (MCMF, Mininum Cost Maximum Flow) (Platinum III)

- 최대 유량을 최소 비용으로 흘릴 때 유량과 비용 구하기

- 두 노드 사이에 2개 이상의 간선이 있을 때도 작동하며, Dinic 알고리즘과 비슷하게 유량을 갱신함과 동시에 새로운 DAG를 O(V+E) 시간에 갱신하는 최적화된 MCMF

- 최대 비용을 구하려면 간선을 추가할 때 비용을 마이너스 값으로 입력한 뒤, 구해진 최소 비용에 마이너스 값을 붙여 구해주면 된다.

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

struct MCMF {
    struct se { int num, cap, sco, ord; };
    vector<vector<se>> adj;

    void edge(int a, int b, int c, int d){
        adj[a].push_back({b, c, d, adj[b].size()});
        adj[b].push_back({a, 0, -d, adj[a].size()-1});
    }

    int sour, sink;
    vector<int> tco, idx;
    vector<bool> chk;

    int dfs(int x, int flo){
        chk[x] = true;

        if(x == sink) return flo;

        for(; idx[x] < adj[x].size(); idx[x]++) {
            se &ad = adj[x][idx[x]];

            if(chk[ad.num] || tco[x] + ad.sco != tco[ad.num] || ad.cap == 0) continue;

            int ret = dfs(ad.num, min(flo, ad.cap));

            if(ret == 0) continue;

            ad.cap -= ret;
            adj[ad.num][ad.ord].cap += ret;

            return ret;
        }

        return 0;
    }

    pair<int, int> mcmf(int sour_, int sink_) {
        sour = sour_, sink = sink_;

        int minc = 0, maxf = 0;

        tco.resize(adj.size(), INT_MAX);
        tco[sour] = 0;

        queue<int> q;
        q.push(sour);

        vector<bool> inq(adj.size());
        inq[sour] = true;

        while(!q.empty()) {
            int x = q.front();
            q.pop(); inq[x] = false;

            for(int i=0; i<adj[x].size(); i++) {
                int y = adj[x][i].num;
                int cap = adj[x][i].cap;
                int sco = adj[x][i].sco;

                if(cap <= 0 || tco[x] + sco >= tco[y]) continue;

                tco[y] = tco[x] + sco;

                if(inq[y]) continue;

                q.push(y);
                inq[y] = true;
            }
        }

        while(true) {
            chk.clear(); chk.resize(adj.size());
            idx.clear(); idx.resize(adj.size());

            while(true) {
                int cur = dfs(sour, INT_MAX);
                if(cur == 0) break;

                minc += tco[sink] * cur;
                maxf += cur;

                chk.clear(); chk.resize(adj.size());
            }

            int Min = INT_MAX;

            for(int i=0; i<adj.size(); i++) {
                if(!chk[i]) continue;

                for(int j=0; j<adj[i].size(); j++) {
                    int x = adj[i][j].num;
                    int cap = adj[i][j].cap;
                    int sco = adj[i][j].sco;

                    if(cap > 0 && !chk[x]) Min = min(Min, tco[i] + sco - tco[x]);
                }
            }

            if(Min == INT_MAX) break;

            for(int i=0; i<adj.size(); i++)
                if(!chk[i]) tco[i] += Min;
        }

        return {minc, maxf};
    }
};

int32_t main(){
    cin.tie(0)->sync_with_stdio(0);

    int T = 1;

    while(T--) {
        int N, M; cin >> N >> M;

        MCMF f;

        f.adj.resize(N+M+3);

        int sour = N+M+1, sink = N+M+2;

        for(int i=1; i<=N; i++) {
            f.edge(sour, i, 1, 0);

            int K; cin >> K;

            while(K--) {
                int a, b; cin >> a >> b;

                f.edge(i, N+a, 1, b);
            }
        }

        for(int i=1; i<=M; i++) f.edge(N+i, sink, 1, 0);

        pair<int, int> mcmf = f.mcmf(sour, sink);

        int minc = mcmf.first;
        int maxf = mcmf.second;

        cout << maxf << "\n";
        cout << minc << "\n";
    }
}

 

- 유량을 특정 양만큼만 흘려주어야 할 때

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

struct MCMF {
    struct se { int num, cap, sco, ord; };
    vector<vector<se>> adj;

    void edge(int a, int b, int c, int d) {
        adj[a].push_back({b, c, d, adj[b].size()});
        adj[b].push_back({a, 0, -d, adj[a].size()-1});
    }

    int mcmf(int sour, int sink, int amount) {
        int maxf = 0, minc = 0;

        while(amount--) {
            vector<int> pre(adj.size(), -1), idx(adj.size(), -1);

            vector<int> tco(adj.size(), INT_MAX);
            tco[sour] = 0;

            queue<int> q;
            q.push(sour);

            vector<bool> inq(adj.size());
            inq[sour] = true;

            while(!q.empty()) {
                int x = q.front();
                q.pop();
                inq[x] = false;

                for(int i=0; i<adj[x].size(); i++) {
                    int y = adj[x][i].num;
                    int cap = adj[x][i].cap;
                    int sco = adj[x][i].sco;

                    if(cap <= 0 || tco[x] + sco >= tco[y]) continue;

                    tco[y] = tco[x] + sco;
                    pre[y] = x;
                    idx[y] = i;

                    if(inq[y]) continue;

                    q.push(y);
                    inq[y] = true;
                }
            }
            if(pre[sink] == -1) break;

            int sfl = INT_MAX;

            for(int i=sink; i!=sour; i=pre[i]) {
                int a = pre[i], b = idx[i];

                sfl = min(sfl, adj[a][b].cap);
            }

            for(int i=sink; i!=sour; i=pre[i]) {
                int a = pre[i], b = idx[i];

                adj[a][b].cap -= sfl;
                adj[i][adj[a][b].ord].cap += sfl;

                minc += sfl * adj[a][b].sco;
            }

            maxf += sfl;
        }

        return minc;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        MCMF f; f.adj.resize(N+3);

        while(M--) {
            int a, b; cin >> a >> b;

            f.edge(a, b, INT_MAX, 1);
            f.edge(b, a, INT_MAX, 1);
        }

        int sour = N+1, sink = N+2, cnt = 0;

        for(int i=1; i<=N; i++) {
            int x; cin >> x;

            if(x == 1) cnt++, f.edge(sour, i, 1, 0);
        }

        for(int i=1; i<=N; i++) {
            int x; cin >> x;

            if(x == 1) f.edge(i, sink, 1, 0);
        }

        cout << f.mcmf(sour, sink, cnt) << "\n";
    }
}

 

이분 매칭 (+ 쾨니그의 정리) (Platinum III)

- N x N 격자에서 행과 열을 몇 개 선택하여 M개의 돌이 모두 선택되게 하는 최소 연산 횟수 구하기

- 쾨니그의 정리 : 모든 간선과 인접한 최소 노드 수 = 최대 매칭 개수 → 이분 매칭으로 최대 매칭 수를 구해주면 됨

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

vector<vector<int>> adj;
vector<int> l, r;
vector<bool> vis;

bool f(int x) {
    vis[x] = true;

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(r[y] == -1 || (!vis[r[y]] && f(r[y]))) {
            l[x] = y, r[y] = x;

            return true;
        }
    }

    return false;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    adj.resize(N+1);

    while(M--) {
        int x, y; cin >> x >> y;

        adj[x].push_back(y);
    }

    l.resize(N+1, -1);
    r.resize(N+1, -1);

    int ans = 0;

    for(int i=1; i<=N; i++) {
        vis.clear();
        vis.resize(N+1);

        if(f(i)) ans++;
    }

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

 

머지 소트 트리 (Merge Sort Tree) (Platinum III)

- 각 노드에 구간 값들이 정렬되어 있는 머지 소트 트리

- 아래의 예제는 구간에서 x보다 큰 원소의 개수를 구하는 쿼리를 처리하는 코드

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

struct mergeSortTree {
    vector<vector<int>> v;

    void init(int n, int b, int e, vector<int> &u) {
        if(b == e) {
            v[n].push_back(u[b-1]);
            return;
        }

        init(n*2, b, (b+e)/2, u);
        init(n*2+1, (b+e)/2+1, e, u);

        v[n].resize(v[n*2].size() + v[n*2+1].size());
        merge(v[n*2].begin(), v[n*2].end(), v[n*2+1].begin(), v[n*2+1].end(), v[n].begin());
    }

    int gt(int n, int b, int e, int l, int r, int x) {
        if(r < b || e < l) return 0;

        if(l <= b && e <= r)
            return v[n].end() - upper_bound(v[n].begin(), v[n].end(), x);

        return gt(n*2, b, (b+e)/2, l, r, x) + gt(n*2+1, (b+e)/2+1, e, l, r, x);
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    mergeSortTree f;
    f.v.resize(1<<18);

    int N; cin >> N;

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

    f.init(1, 1, N, v);

    int M; cin >> M;

    while(M--) {
        int a, b, c; cin >> a >> b >> c;

        int ans = f.gt(1, 1, N, a, b, c);

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

 

2-SAT (Platinum III)

- N개의 명제와 M개의 절 (xi ∧ xj)

- 식을 참으로 만들 수 있으면 1, 아니면 0 출력

- 식을 참으로 만들 수 있을 경우 tf 벡터에 각 값이 참/거짓 중 어떤 값을 가져야 하는지 구함

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int y(int x) {
    if(x < 0) return (-x)*2 - 2;
    else return x*2 - 1;
}

int n(int x) {
    x = y(x);

    if(x % 2 == 0) return x + 1;
    else return x - 1;
}

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

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

        scc.push_back(v);
    }

    return tmp;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int T = 1;

    while(T--) {
        int N, M; cin >> N >> M;

        adj.clear(); adj.resize(N*2);

        while(M--) {
            int a, b; cin >> a >> b;

            adj[n(a)].push_back(y(b));
            adj[n(b)].push_back(y(a));
        }

        nnum.clear(); nnum.resize(N*2);
        cnum.clear(); cnum.resize(N*2);
        ch.clear();   ch.resize(N*2);

        scc.clear();
        ncnt = ccnt = 0;

        for(int i=0; i<N*2; i++)
            if(nnum[i] == 0) dfs(i);

        bool check = true;

        for(int i=0; i<N; i++) {
            if(cnum[i*2] == cnum[i*2 + 1]) {
                check = false;
                break;
            }
        }

        if(check) cout << 1 << "\n";
        else {
            cout << 0 << "\n";
            return 0;
        }

        vector<pair<int, int>> p(N*2);
        for(int i=0; i<N*2; i++) p[i] = {cnum[i], i};

        sort(p.begin(), p.end(), greater<pair<int, int>>());

        vector<int> tf(N*2, -1);

        for(int i=0; i<N*2; i++) {
            int x = p[i].second;

            if(tf[x/2] == -1) {
                if(x % 2 == 1) tf[x/2] = 0;
                else tf[x/2] = 1;
            }
        }

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

 

회전하는 캘리퍼스 : 점들의 최소 폭 (Platinum III)

- N개의 점들이 무작위로 주어짐

- 점들의 집합이 가지는 최소 폭을 출력

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

struct P { double x, y; };

P operator-(P a, P b) {
    P c;
    c.x = a.x - b.x;
    c.y = a.y - b.y;
    return c;
}

vector<P> v;

double ccw(P a, P b, P c) {
    return a.x * (b.y - c.y) + b.x * (c.y - a.y) + c.x * (a.y - b.y);
}

bool cmp(P &a, P &b) {
    double val = ccw(v[0], a, b);

    if(val != 0) return val > 0;
    else if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

double dist(P a1, P a2, P b) {
    P c = b - a1;
    P d = a2 - a1;

    return sqrt(pow(c.x*d.y - c.y*d.x, 2) / (pow(d.x, 2) + pow(d.y, 2)));
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;

    for(int i=1; i<N; i++)
        if(v[i].y < v[0].y || (v[i].y == v[0].y && v[i].x < v[0].x)) swap(v[i], v[0]);

    sort(v.begin()+1, v.end(), cmp);

    stack<P> s;

    s.push(v[0]);
    s.push(v[1]);

    for(int i=2; i<N; i++) {
        while(s.size() >= 2) {
            P a = s.top(); s.pop();
            P b = s.top();

            if(ccw(b, a, v[i]) > 0) {
                s.push(a);
                break;
            }
        }
        s.push(v[i]);
    }

    vector<P> u(s.size());
    while(!s.empty()) {
        u[s.size()-1] = s.top();
        s.pop();
    }

    int l = 0, r = 0;
    for(int i=0; i<u.size(); i++) {
        if(u[i].x < u[l].x) l = i;
        if(u[i].x > u[r].x) r = i;
    }

    double ans = INT_MAX;
    P o = {0, 0};

    for(int i=0; i<u.size(); i++) {
        int nl = (l+1) % u.size();
        int nr = (r+1) % u.size();

        if(ccw(o, u[nl] - u[l], u[r] - u[nr]) > 0) {
            ans = min(ans, dist(u[l], u[nl], u[r]));
            l = nl;
        }
        else {
            ans = min(ans, dist(u[r], u[nr], u[l]));
            r = nr;
        }
    }

    cout << fixed;
    cout.precision(6);

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

 

Mo's 알고리즘 (모스 알고리즘) (Platinum II)

- N개의 수, M개의 쿼리

- a b : a ~ b 구간에 존재하는 서로 다른 수의 개수 구하기

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

int S;
struct query { int l, r, n; };

bool cmp(query a, query b) {
    if(a.l / S != b.l / S) return a.l / S < b.l / S;
    else return a.r < b.r;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    S = sqrt(N);

    int M; cin >> M;

    vector<query> Q(M);

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

        Q[i].l = a - 1, Q[i].r = b - 1, Q[i].n = i;
    }

    sort(Q.begin(), Q.end(), cmp);

    vector<int> ans(M), cnt(1e6 + 1);
    int val = 0, l = Q[0].l, r = Q[0].r;

    for(int i=l; i<=r; i++) {
        if(cnt[v[i]] == 0) val++;
        cnt[v[i]]++;
    }

    ans[Q[0].n] = val;

    for(int i=1; i<M; i++) {
        while(Q[i].l < l)
            if(cnt[v[--l]]++ == 0) val++;

        while(Q[i].r > r)
            if(cnt[v[++r]]++ == 0) val++;

        while(Q[i].l > l)
            if(--cnt[v[l++]] == 0) val--;

        while(Q[i].r < r)
            if(--cnt[v[r--]] == 0) val--;

        ans[Q[i].n] = val;
    }

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

 

가장 가까운 두 점 (Platinum II)

- 분할 정복을 이용한 O(N log N) 풀이

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

struct s { int x, y; };

bool cmpx(s a, s b) {
    if(a.x != b.x) return a.x < b.x;
    else return a.y < b.y;
}

bool cmpy(s a, s b) {
    if(a.y != b.y) return a.y < b.y;
    else return a.x < b.x;
}

int dis(s a, s b) {
    return pow(a.x - b.x, 2) + pow(a.y - b.y, 2);
}

vector<s> v;

int f(int l, int r) {
    if(l == r) return LLONG_MAX;
    if(l+1 == r) return dis(v[l], v[r]);

    int m = (l + r) / 2;
    int Min = min({dis(v[l], v[r]), f(l, m), f(m+1, r)});

    vector<s> u;
    int cen = v[m].x;

    for(int i=l; i<=r; i++)
        if(pow(v[i].x - cen, 2) < Min) u.push_back(v[i]);

    sort(u.begin(), u.end(), cmpy);

    for(int i=0; i<u.size(); i++)
        for(int j=i+1; j<u.size(); j++) {
            if(pow(u[i].y - u[j].y, 2) >= Min) break;

            if(pow(u[i].x - u[j].x, 2) < Min) Min = min(Min, dis(u[i], u[j]));
        }

    return Min;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    v.resize(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;

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

    int ans = f(0, N-1);

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

 

퍼시스턴트 세그먼트 트리 (PST, Persistent Segment Tree) (Platinum II)

- 갱신 기록 전체를 저장하고 있는 트리 (공간 복잡도 O(N log N))

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

const int MAX = 1e5 + 1;

struct node {
    node *l, *r; int x;
    node() { l = r = NULL, x = 0; }
};

node *add(node *cur, int b, int e, int idx, int val) {
    if(cur == NULL) cur = new node();

    if(idx < b || e < idx) return cur;

    if(b == e) {
        node *ret = new node();

        ret->x = cur->x + 1;

        return ret;
    }

    node *ret = new node();

    node *ln = add(cur->l, b, (b+e)/2, idx, val);
    node *rn = add(cur->r, (b+e)/2 + 1, e, idx, val);

    ret->l = ln, ret->r = rn, ret->x = ln->x + rn->x;

    return ret;
}

int sum(node *cur, int b, int e, int l, int r) {
    if(cur == NULL) return 0;

    if(r < b || e < l) return 0;
    if(l <= b && e <= r) return cur->x;

    return sum(cur->l, b, (b+e)/2, l, r) + sum(cur->r, (b+e)/2 + 1, e, l, r);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int T; cin >> T;

    while(T--) {
        int N, M; cin >> N >> M;

        vector<vector<int>> v(MAX+1);

        for(int i=0; i<N; i++) {
            int x, y; cin >> x >> y;

            v[x+1].push_back(y+1);
        }

        node *u[MAX+1];
        u[0] = new node();

        for(int i=1; i<=MAX; i++) {
            u[i] = new node();

            u[i]->l = u[i-1]->l, u[i]->r = u[i-1]->r, u[i]->x = u[i-1]->x;

            for(int j=0; j<v[i].size(); j++)
                u[i] = add(u[i], 1, MAX, v[i][j], 1);
        }

        int ans = 0;

        while(M--) {
            int a, b, c, d; cin >> a >> b >> c >> d;

            ans += sum(u[b+1], 1, MAX, c+1, d+1)
                   - sum(u[a], 1, MAX, c+1, d+1);
        }

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

 

고속 푸리에 변환 (FFT) (Platinum I)

- 쿨리-툴키 알고리즘보다 더 빠른 효율적인 코드

- complex vector a와 b 사이의 이산 곱을 구하여 complex vector c에 저장하며, round(c[i].real())로 결과 값의 i번째 항에 접근 가능함 (이 때 i는 0 ~ Size)

 

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

typedef complex<double> cpx;

void FFT(vector<cpx> &v, bool inv) {
    int S = v.size();

    for(int i=1, j=0; i<S; i++) {
        int bit = S/2;

        while(j >= bit) {
            j -= bit;
            bit /= 2;
        }
        j += bit;

        if(i < j) swap(v[i], v[j]);
    }

    for(int k=1; k<S; k*=2) {
        double angle = (inv ? M_PI/k : -M_PI/k);
        cpx w(cos(angle), sin(angle));

        for(int i=0; i<S; i+=k*2) {
            cpx z(1, 0);

            for(int j=0; j<k; j++) {
                cpx even = v[i+j];
                cpx odd = v[i+j+k];

                v[i+j] = even + z*odd;
                v[i+j+k] = even - z*odd;

                z *= w;
            }
        }
    }

    if(inv)
        for(int i=0; i<S; i++) v[i] /= S;
}

vector<int> mul(vector<int> &v, vector<int> &u) {
    vector<cpx> vc(v.begin(), v.end());
    vector<cpx> uc(u.begin(), u.end());

    int S = 2;
    while(S < v.size() + u.size()) S *= 2;

    vc.resize(S); FFT(vc, false);
    uc.resize(S); FFT(uc, false);

    for(int i=0; i<S; i++) vc[i] *= uc[i];
    FFT(vc, true);

    vector<int> w(v.size() + u.size() - 1);
    for(int i=0; i<w.size(); i++) w[i] = round(vc[i].real());

    return w;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    vector<int> v(N);

    for(int i=1; i<N; i++) v[(i * i) % N]++;

    v = mul(v, v);

    for(int i=1; i<N; i++) v[(i * i * 2) % N]++;

    int ans = 0;

    for(int i=1; i<N; i++)
        for(int j=(i*i)%N; j<v.size(); j+=N) ans += v[j];

    ans /= 2;

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

 

NTT (Number Theoretic Transform) (Platinum I)

- FFT의 modulo 연산 버전 : 두 벡터의 이산 곱의 모듈로 값을 계산하기 위해서는 NTT를 사용해야 함
- mod 값마다 대응되는 w 값이 다르므로 이를 참고할 것

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

int mod = 998244353, w = 3;

int fast_pow(int ba, int ex) {
    int ret = 1;

    while(ex > 0) {
        if(ex % 2 == 1) ret = (ret * ba) % mod;

        ba = (ba * ba) % mod;
        ex /= 2;
    }

    return ret;
}

void NTT(vector<int> &v, bool inv) {
    int S = v.size();

    vector<int> u(S / 2);

    for(int i=1, j=0; i<S; i++) {
        int bit = S / 2;

        while(j >= bit) {
            j -= bit;
            bit /= 2;
        }
        j += bit;

        if(i < j) swap(v[i], v[j]);
    }

    int angle = fast_pow(w, (mod - 1) / S);

    if(inv) angle = fast_pow(angle, mod - 2);

    u[0] = 1;

    for(int i=1; i<S/2; i++) u[i] = (u[i-1] * angle) % mod;

    for(int k=1; k<S; k*=2) {
        int z = S / (k * 2);

        for(int i=0; i<S; i+=k*2)
            for(int j=0; j<k; j++) {
                int even = v[i+j], odd = (u[z*j] * v[i+j+k]) % mod;

                v[i+j] = (even + odd) % mod;
                v[i+j+k] = (even - odd + mod) % mod;
            }
    }

    if(inv) {
        int z = fast_pow(S, mod - 2);

        for(int i=0; i<S; i++) v[i] = (v[i] * z) % mod;
    }
}

vector<int> mul(vector<int> &v, vector<int> &u) {
    vector<int> vv(v.begin(), v.end());
    vector<int> uu(u.begin(), u.end());

    int S = 2;
    while(S < v.size() + u.size()) S *= 2;

    vv.resize(S); NTT(vv, false);
    uu.resize(S); NTT(uu, false);

    for(int i=0; i<S; i++) vv[i] = vv[i] * uu[i] % mod;
    NTT(vv, true);

    vv.resize(v.size() + u.size() - 1);

    return vv;
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

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

    v = mul(v, v);

    for(int i=0; i<v.size(); i++) cout << v[i] << " ";
    cout << "\n";
}

 

폴라드 로 (큰 수 소인수분해 + 모든 약수 구하기) (Platinum I)

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

struct pollards_rho {
    __int128 power(__int128 x, __int128 y, __int128 mod) {
        x %= mod;

        __int128 ret = 1;

        while(y > 0) {
            if(y % 2 == 1) ret = (ret * x) % mod;

            x = (x * x) % mod;
            y /= 2;
        }

        return ret;
    }

    bool is_prime(__int128 n) {
        if(n == 2 || n == 3) return true;
        if(n % 2 == 0) return false;

        vector<__int128> base = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
        int sz = 4;

        bool chk = true;

        for(int i=0; i<sz; i++) {
            if(base[i] % n == 0) break;

            __int128 k = n - 1;

            while(true) {
                __int128 tmp = power(base[i], k, n);

                if(tmp == n - 1) break;
                if(k % 2 == 1) {
                    if(tmp != 1 && tmp != n - 1) chk = false;

                    break;
                }

                k /= 2;
            }

            if(!chk) break;
        }

        if(chk) return true;
        else return false;
    }

    int find_factor(__int128 n) {
        if(n % 2 == 0) return 2;
        if(is_prime(n)) return n;

        __int128 x = rand() % (n - 2) + 2, y = x, c = rand() % 10 + 1, g = 1;

        while(g == 1) {
            x = ((x * x) % n + c) % n;
            y = ((y * y) % n + c) % n;
            y = ((y * y) % n + c) % n;
            g = __gcd(abs(x - y), n);

            if(g == n) return find_factor(n);
        }

        if(is_prime(g)) return g;
        else return find_factor(g);
    }

    vector<pair<int, int>> factorization(int n) {
        vector<int> v;
        unordered_map<int, int> m;

        while(n > 1) {
            int div = find_factor(n);

            if(m[div] == 0) v.push_back(div);
            m[div]++;
            n /= div;
        }

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

        vector<pair<int, int>> u;
        for(int i=0; i<v.size(); i++) u.push_back({v[i], m[v[i]]});

        return u;
    }

    vector<int> get_divisors(int n) {
        vector<pair<int, int>> v = factorization(n);
        vector<int> u;

        if(v.size() == 0) {
            u.push_back(1);
            return u;
        }

        function<void(int, int)> dfs = [&](int idx, int cur) {
            if(idx == v.size()) {
                u.push_back(cur);
                return;
            }

            int x = v[idx].first, y = v[idx].second;

            for(int i=0; i<=y; i++) {
                dfs(idx + 1, cur);
                cur *= x;
            }
        };

        dfs(0, 1);

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

        return u;
    }
} po;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    vector<int> v = po.get_divisors(N);

    for(int i=0; i<v.size(); i++) cout << v[i] << " ";
    cout << "\n";
}

 

제곱근 분할법 (Diamond V)

- M + K개의 쿼리를 처리하는 프로그램

- 1 a b : a번째 원소를 b로 교환

- 2 a b : a ~ b 구간의 합 출력

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

vector<int> v, u;

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N, M, K; cin >> N >> M >> K;
    M += K;

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

    int S = sqrt(N); u.resize(N/S + 1);
    for(int i=0; i<N; i++) u[i/S] += v[i];

    while(M--) {
        int Q; cin >> Q;

        if(Q == 1) {
            int idx, val; cin >> idx >> val;
            idx--;

            v[idx] = val;

            u[idx/S] = 0;
            int l = (idx / S) * S, r = l + S;
            for(int i=l; i<r; i++) u[idx/S] += v[i];
        }
        else if(Q == 2) {
            int l, r; cin >> l >> r;
            l--, r--;

            int sum = 0;

            while(l % S != 0 && l <= r) sum += v[l++];
            while((r + 1) % S != 0 && l <= r) sum += v[r--];

            while(l <= r) {
                sum += u[l/S];
                l += S;
            }

            cout << sum << "\n";
        }
    }
}

 

금광 세그먼트 트리 (+ 2차원 좌표 압축 + 스위핑) (Diamond V)

-  N개의 좌표에 가중치가 주어질 때 직사각형 구간 최대 합 구하기

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

struct p { int x, y, w; };
vector<p> v;

struct node { int lsum, rsum, sum, maxsum; };
vector<node> tree;

node mer(node a, node b) {
    int lsum = max(a.lsum, a.sum + b.lsum);
    int rsum = max(b.rsum, b.sum + a.rsum);
    int sum = a.sum + b.sum;
    int maxsum = max({a.maxsum, b.maxsum, a.rsum + b.lsum});

    return {lsum, rsum, sum, maxsum};
}

void upd(int n, int b, int e, int idx, int val) {
    if(idx < b || e < idx) return;

    tree[n].lsum += val;
    tree[n].rsum += val;
    tree[n].sum += val;
    tree[n].maxsum += val;

    if(b == e) return;

    upd(n*2, b, (b+e)/2, idx, val);
    upd(n*2 + 1, (b+e)/2 + 1, e, idx, val);

    tree[n] = mer(tree[n*2], tree[n*2 + 1]);
}

node query(int n, int b, int e, int l, int r) {
    if(r < b || e < l) return {INT_MIN, INT_MIN, INT_MIN, INT_MIN};
    if(l <= b && e <= r) return tree[n];

    node ln = query(n*2, b, (b+e)/2, l, r);
    node rn = query(n*2 + 1, (b+e)/2 + 1, e, l, r);

    return mer(ln, rn);
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    int N; cin >> N;

    v.resize(N+1);
    vector<pair<int, int>> vx(N+1), vy(N+1);

    for(int i=1; i<=N; i++) {
        cin >> v[i].x >> v[i].y >> v[i].w;

        vx[i] = {v[i].x, i};
        vy[i] = {v[i].y, i};
    }

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

    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(N+1, vector<int>(N+1));
    vector<vector<pair<int, int>>> uy(N+1);

    for(int i=1; i<=N; i++) {
        u[v[i].x][v[i].y] = v[i].w;
        uy[v[i].y].push_back({v[i].x, v[i].w});
    }

    int ans = INT_MIN;
    for(int i=1; i<=ycnt; i++) {
        tree.clear();
        tree.resize((N+1)*4);

        for(int j=i; j<=ycnt; j++) {
            for(int k=0; k<uy[j].size(); k++)
                upd(1, 1, N, uy[j][k].first, uy[j][k].second);

            ans = max(ans, query(1, 1, N, 1, N).maxsum);
        }
    }

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

 

최소 외접원 / 외접구 (Smallest Enclosing Circle / Sphere) (Diamond V)

- 최소 외접원 : N개의 점을 모두 포함하는 최소 외접원의 중심 좌표와 반지름

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

struct p { double x, y; };

double dis(p a, p b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2));
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cout << fixed;
    cout.precision(3);

    int N; cin >> N;

    vector<p> v(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y;

    p cen = {0, 0};
    double r = 0;

    for(int i=0; i<N; i++) {
        if(dis(cen, v[i]) <= r) continue;

        cen = v[i], r = 0;

        for(int j=0; j<i; j++) {
            if(dis(cen, v[j]) <= r) continue;

            cen = {(v[i].x + v[j].x) / 2, (v[i].y + v[j].y) / 2};
            r = dis(cen, v[i]);

            for(int k=0; k<j; k++) {
                if(dis(cen, v[k]) <= r) continue;

                cen.x = ((pow(v[j].x, 2) - pow(v[k].x, 2) + pow(v[j].y, 2) - pow(v[k].y, 2)) * (v[i].y - v[j].y)
                         - (pow(v[j].x, 2) - pow(v[i].x, 2) + pow(v[j].y, 2) - pow(v[i].y, 2)) * (v[k].y - v[j].y))
                         / ((v[i].x - v[j].x) * (v[k].y - v[j].y) * 2 - (v[k].x - v[j].x) * (v[i].y - v[j].y) * 2);
                cen.y = ((pow(v[j].y, 2) - pow(v[k].y, 2) + pow(v[j].x, 2) - pow(v[k].x, 2)) * (v[i].x - v[j].x)
                         - (pow(v[j].y, 2) - pow(v[i].y, 2) + pow(v[j].x, 2) - pow(v[i].x, 2)) * (v[k].x - v[j].x))
                         / ((v[i]. y- v[j].y) * (v[k].x - v[j].x) * 2 - (v[k].y - v[j].y) * (v[i].x - v[j].x) * 2);
                r = dis(cen, v[i]);
            }
        }
    }

    if(abs(cen.x) < 1e-4) cen.x = 0;
    if(abs(cen.y) < 1e-4) cen.y = 0;

    cout << cen.x << " " << cen.y << "\n";
    cout << r << "\n";
}

 

- 최소 외접구: N개의 점을 모두 포함하는 최소 외접구의 중심 좌표와 반지름

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

struct p { double x, y, z; };

double dis(p a, p b) {
    return sqrt(pow(a.x - b.x, 2) + pow(a.y - b.y, 2) + pow(a.z - b.z, 2));
}

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

    cout << fixed;
    cout.precision(3);

    int N; cin >> N;

    vector<p> v(N);
    for(int i=0; i<N; i++) cin >> v[i].x >> v[i].y >> v[i].z;

    p cen = {0, 0, 0};
    double r = 0;

    for(int i=0; i<N; i++) {
        if(dis(cen, v[i]) <= r) continue;

        cen = v[i], r = 0;

        for(int j=0; j<i; j++) {
            if(dis(cen, v[j]) <= r) continue;

            cen = {(v[i].x + v[j].x) / 2, (v[i].y + v[j].y) / 2, (v[i].z + v[j].z) / 2};
            r = dis(cen, v[i]);

            for(int k=0; k<j; k++) {
                if(dis(cen, v[k]) <= r) continue;

                double ax = v[i].x, ay = v[i].y, az = v[i].z;
                double bx = v[j].x, by = v[j].y, bz = v[j].z;
                double cx = v[k].x, cy = v[k].y, cz = v[k].z;

                double Cx = bx - ax, Cy = by - ay, Cz = bz - az;
                double Bx = cx - ax, By = cy - ay, Bz = cz - az;

                double B2 = ax*ax - cx*cx + ay*ay - cy*cy + az*az - cz*cz;
                double C2 = ax*ax - bx*bx + ay*ay - by*by + az*az - bz*bz;

                double CByz = Cy*Bz - Cz*By;
                double CBxz = Cx*Bz - Cz*Bx;
                double CBxy = Cx*By - Cy*Bx;

                double zz1 = - (Bz - Cz*Bx/Cx) / (By - Cy*Bx/Cx);
                double z01 = - (B2 - Bx/Cx*C2) / ((By - Cy*Bx/Cx) * 2);
                double zz2 = - (zz1*Cy + Cz) / Cx;
                double z02 = - (z01*Cy*2 + C2) / (Cx * 2);

                cen.z = - ((z02 - ax) * CByz - (z01 - ay) * CBxz - az * CBxy) / (zz2 * CByz - zz1 * CBxz + CBxy);
                cen.x = zz2 * cen.z + z02;
                cen.y = zz1 * cen.z + z01;

                r = dis(cen, v[i]);

                for(int l=0; l<k; l++) {
                    if(dis(cen, v[l]) <= r) continue;

                    double x1 = v[i].x, x2 = v[j].x, x3 = v[k].x, x4 = v[l].x;
                    double y1 = v[i].y, y2 = v[j].y, y3 = v[k].y, y4 = v[l].y;
                    double z1 = v[i].z, z2 = v[j].z, z3 = v[k].z, z4 = v[l].z;

                    double a11 = x2 - x1, a12 = y2 - y1, a13 = z2 - z1;
                    double a21 = x3 - x2, a22 = y3 - y2, a23 = z3 - z2;
                    double a31 = x4 - x1, a32 = y4 - y1, a33 = z4 - z1;

                    double det = a11 * (a22*a33 - a23*a32) - a12 * (a21*a33 - a23*a31) + a13 * (a21*a32 - a22*a31);

                    double c11 = a22*a33 - a32*a23, c12 = - (a12*a33 - a32*a13), c13 = a12*a23 - a22*a13;
                    double c21 = - (a21*a33 - a31*a23), c22 = a11*a33 - a31*a13, c23 = - (a11*a23 - a21*a13);
                    double c31 = a21*a32 - a31*a22, c32 = - (a11*a32 - a31*a12), c33 = a11*a22 - a21*a12;

                    double xx = x2*x2 - x1*x1 + y2*y2 - y1*y1 + z2*z2 - z1*z1;
                    double yy = x3*x3 - x2*x2 + y3*y3 - y2*y2 + z3*z3 - z2*z2;
                    double zz = x4*x4 - x1*x1 + y4*y4 - y1*y1 + z4*z4 - z1*z1;

                    cen.x = (c11*xx + c12*yy + c13*zz) / (det * 2);
                    cen.y = (c21*xx + c22*yy + c23*zz) / (det * 2);
                    cen.z = (c31*xx + c32*yy + c33*zz) / (det * 2);

                    r = dis(cen, v[i]);
                }
            }
        }
    }

    if(abs(cen.x) < 1e-4) cen.x = 0;
    if(abs(cen.y) < 1e-4) cen.y = 0;
    if(abs(cen.z) < 1e-4) cen.z = 0;

    cout << cen.x << " " << cen.y << " " << cen.z << "\n";
    cout << r << "\n";
}

 

서큘레이션 (Circulation) (Diamond IV)

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

struct s { int b, e, l, r; };

struct Circulation {
    struct se { int num, cap, ord, idx; };
    vector<vector<se>> adj;

    void edge(int a, int b, int c, int d) {
        adj[a].push_back({b, c, adj[b].size(), d});
        adj[b].push_back({a, 0, adj[a].size()-1, -1});
    }

    int sz, sour, sink;
    vector<int> lv, idx;

    void init(int sz_) { sz = sz_; adj.resize(sz); }

    bool bfs() {
        lv.clear(); lv.resize(sz, -1); lv[sour] = 0;

        queue<int> q; q.push(sour);

        while(!q.empty()) {
            int x = q.front(); q.pop();

            for(auto e : adj[x]) {
                int y = e.num, cap = e.cap;

                if(lv[y] != -1 || cap == 0) continue;

                lv[y] = lv[x] + 1;
                q.push(y);
            }
        }

        if(lv[sink] != -1) return true;
        else return false;
    }

    int dfs(int x, int flo) {
        if(x == sink) return flo;

        for(int &i=idx[x]; i<adj[x].size(); i++) {
            int y = adj[x][i].num, cap = adj[x][i].cap;

            if(lv[x] + 1 != lv[y] || cap == 0) continue;

            int sfl = dfs(y, min(flo, cap));

            if(sfl == 0) continue;

            adj[x][i].cap -= sfl;
            adj[y][adj[x][i].ord].cap += sfl;

            return sfl;
        }

        return 0;
    }

    int mf(int sour_, int sink_) {
        int maxf = 0; sour = sour_, sink = sink_;

        while(bfs()) {
            idx.clear(); idx.resize(sz);

            while(true) {
                int sfl = dfs(sour, INT_MAX);

                if(sfl == 0) break;

                maxf += sfl;
            }
        }

        return maxf;
    }

    bool solve(vector<int> &ver, vector<s> &edg, vector<int> &ans) {
        int N = ver.size()-1;

        for(int i=0; i<edg.size(); i++) {
            ver[edg[i].b] += edg[i].l;
            ver[edg[i].e] -= edg[i].l;
        }

        int psum = 0, msum = 0;

        for(int i=1; i<=N; i++) {
            if(ver[i] > 0) psum += ver[i];
            else msum += ver[i];
        }

        if(psum != abs(msum)) return false;

        sour = N+1, sink = N+2;

        for(int i=1; i<=N; i++) {
            if(ver[i] < 0) edge(sour, i, abs(ver[i]), -1);
            else if(ver[i] > 0) edge(i, sink, ver[i], -1);
        }

        for(int i=0; i<edg.size(); i++)
            edge(edg[i].b, edg[i].e, edg[i].r - edg[i].l, i);

        if(mf(sour, sink) != psum) return false;

        for(int i=1; i<=N; i++)
            for(auto e : adj[i])
                if(e.idx != -1) ans[e.idx] = (edg[e.idx].r - edg[e.idx].l) - e.cap;

        for(int i=0; i<edg.size(); i++) ans[i] += edg[i].l;

        return true;
    }
};

int32_t main() {
    cin.tie(0)->sync_with_stdio(0);

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

    Circulation c; c.init(N+3);

    vector<int> ver(N+1);
    for(int i=1; i<=N; i++) cin >> ver[i], ver[i] *= -1; // 공급을 받는다 = 공급이 없었다면 원래 demand 값이 음수

    vector<s> edg(M);
    for(int i=0; i<M; i++)
        cin >> edg[i].b >> edg[i].e >> edg[i].l >> edg[i].r;

    vector<int> ans(M);
    if(!c.solve(ver, edg, ans)) {
        cout << -1 << "\n";
        return 0;
    }

    cout << 1 << "\n";
    for(int i=0; i<M; i++) cout << ans[i] << "\n";
}