Move Fast

K-Goodness String

• 문제 설명: 길이가 N인 문자열 S가 주어질 때, 1 <= i <= N/2 를 인덱스(1부터 시작한다고 가정)로 가지는 문자들 중 S[i] != S[N-i-1] 를 만족하는 문자들의 개수를 goodness score 라고 한다. N, S, K 가 입력으로 주어질 때 문자열 S의 goodness score가 정확히 K가 되도록 문자들을 최소 몇 번 바꾸어야 하는지 구하라.
• 접근법: 문자열 S의 goodness score를 구하고 K와의 차이를 반환
• 시간 복잡도: O(N)

int N, K;
string S;

int solve() {
    cin >> N >> K >> S;
    int n = s.size(), cnt = 0;
    for (int i = 0; i < n >> 1; i++)
        if (S[i] != S[n-i-1])
            cnt++;
    return abs(K - cnt);
}

L Shaped Plots

• 문제 설명: 0과 1로만 구성된 2차원 배열이 주어질 때, 다음을 만족하는 L자 모양의 개수를 반환.
  • 세그먼트는 길이(=칸의 개수)가 2이상인 1로만 이루어진 연속적인 셀(=칸)들로 구성된다.
  • L자 모양을 형성할 때, 두 개의 세그먼트는 양 끝 중 1개의 셀만 공유하며 서로 직교한다.
  • L자 모양에서 두 세그먼트 A, B 에 대해 (A의 길이 = B의 길이 * 2)가 성립한다.
• 풀이: naive 한 방법으로, 1인 셀들의 각 위치에서 상하좌우로 L자 모양을 찾아서 계산한다.
• 시간 복잡도: O(R*C*max(R , C))
  • 여기서 R은 세로 길이, C는 가로 길이이다.
  • 각 위치에서 탐색하므로 R*C만큼 for문을 돌려야 하고, 1인 셀에서 최대 R, C 중 긴 길이만큼 셀을 탐색하게 되므로 시간 복잡도는 R*C*(max(R,C)) 보다 작다.

int R, C;
int A[1000][1000];
const int dy[4] = {-1,1,-1,1};
const int dx[4] = {-1,-1,1,1};

bool inRange(int i, int lo, int hi) { return i >= lo and i < hi; }

int countLShape(int y, int x) {
    int ret = 0;
    
    for (int i = 0; i < 4; i++) {
        int ny = y + dy[i], nx = x + dx[i];
        if (!inRange(nx, 0, C) or !inRange(ny, 0, R)
            or A[ny][x] == 0 or A[y][nx] == 0)
            continue;
        // 상,하 길이 = 좌,우 길이 * 2
        int shorter = 1, longer = 1;
        while (inRange(nx, 0, C) and A[y][nx] == 1) {
            shorter++;
            nx += dx[i];
        }
        while (inRange(ny, 0, R) and A[ny][x] == 1) {
            longer++;
            ny += dy[i];
            if (longer > shorter * 2) break;
            if (longer > 3 and (longer & 1) == 0) ret++;
        }
        
        // 좌,우 길이 = 상,하 길이 * 2
        ny = y + dy[i], nx = x + dx[i];
        shorter = longer = 1;
        while (inRange(ny, 0, R) and A[ny][x] == 1) {
            shorter++;
            ny += dy[i];
        }
        while (inRange(nx, 0, C) and A[y][nx] == 1) {
            longer++;
            nx += dx[i];
            if (longer > shorter * 2) break;
            if (longer > 3 and (longer & 1) == 0) ret++;
        }
    }
    
    return ret;
}

Rabbit House

• 문제 설명: 2차원 배열의 각 원소는 해당 위치에서의 높이를 의미한다. 상하좌우로 인접한 칸끼리 높이 차이가 최대 1이 되도록 높이를 올리는 작업만으로 조정할 때, 최소 작업 횟수를 구하라.
• 풀이: 높이를 내림차순으로 좌표를 정렬하여 큐에 삽입한다. BFS 로 각 좌표를 하나씩 꺼내서 인접한 좌표의 높이가 1보다 더 작은 경우에 높이를 조정하고 큐에 다시 넣는다. 높이가 최대 2 * 10^6 이고 최대 칸의 개수는 300 * 300 = 9 * 10^4 이므로 32비트 정수 범위를 넘는다. 따라서 long long 으로 변수를 선언해야 한다.
  • 처음에는 가장 높은 좌표만 큐에 넣고 BFS를 수행했는데, 그럼 현재 좌표보다 인접한 좌표 중 높이가 1보다 큰 좌표는 탐색하지 못하는 문제가 있었다.
  • 그래서 인접 좌표의 높이가 1보다 작은 경우, 인접 좌표의 높이를 조정한 뒤 큐에 넣고, 인접 좌표의 높이가 1보다 큰 경우, 현재 좌표의 높이를 조정한 뒤 인접 좌표를 큐에 넣었다. WA(Wrong Answer)가 떠서 한참 고민했다. 아마, 첫번째 좌표(최대 높이) 근처에서 멀리 떨어진 좌표들을 조정하다가 모든 인접한 좌표가 1을 만족하는 경우 첫번째 좌표 근처에서 조정이 필요한 좌표들로 BFS를 수행하지 못하는 경우가 생겨서 답이 틀린 것 같다.
• 시간 복잡도: O(R*C)
  • R은 세로 길이, C는 가로 길이이다.
  • 각 좌표는 3번 이상 탐색되지 않으므로, 시간 복잡도는 3*R*C 보다 작다.

typedef long long ll;
typedef pair<long,long> pll;
const int d[5] = {0,-1,0,1,0};

int R, C;
ll A[300][300];

ll solve() {
    cin >> R >> C;
    set<pair<ll, pii>> s;
    for (int i = 0; i < R; i++) {
        for (int j = 0; j < C; j++) {
            cin >> A[i][j];
            s.insert({A[i][j], {i, j}});
        }
    }
    
    ll ans = 0;
    queue<pii> q;
    for (auto it = s.rbegin(); it != s.rend(); it++)
        q.push(it->second);
    
    while (!q.empty()) {
        int y = q.front().first;
        int x = q.front().second;
        q.pop();
        for (int i = 0; i < 4; i++) {
            int ny = y + d[i];
            int nx = x + d[i+1];
            if (ny < 0 or ny >= R or nx < 0 or nx >= C)
                continue;
            if (A[y][x] - 1 > A[ny][nx]) {
                ans += A[y][x] - 1 - A[ny][nx];
                A[ny][nx] = A[y][x] - 1;
                q.push({ny, nx});
            }
        }
    }
    
    return ans;
}

Checksum (NOT SOLVED)

• 문제 설명: NxN 크기의 행렬 A, B 가 주어지고 1xN 크기의 행렬 R, C 가 주어진다. A의 원본 행렬을 복구하는데 필요한 최소 비용을 구하라.
  • A[i][j] := (i, j)번째 원소의 상태, 0 또는 1은 정상적인 값이며, 바이러스에 감염된 원소는 -1이다.
  • B[i][j] := (i, j)번째 원소가 바이러스에 감염되었을 때 복구하는 데 필요한 시간이다. 감염되지 않은 원소의 경우 0이다.
  • R[i] := i번째 행의 모든 원소를 XOR 연산한 결과
  • C[i] := i번째 열의 모든 원소를 XOR 연산한 결과
• 접근: 결과적으로 대회 시간 내에 풀지 못했다. 처음에 접근한 방법은 XOR 연산은 교환 법칙이 성립하기 때문에 1개의 값만 모르는 경우 원소의 행과 열의 XOR 연산 결과로 연산할 수 있다는 점을 이용했다. 현재 상태에서 비용이 가장 작은 좌표를 구하고 비용이 같은게 여러 개이면 해당 원소의 행이나 열에서 -1의 개수가 더 많은 것으로 좌표를 선택한 뒤, 행과 열에서 -1의 개수가 1개보다 많으면 B[i][j]를 더하고 아니면 A[i][j] = 2로 바꿔주었다. 전형적인 그리디 방식으로 풀었으나, 예제만 맞았다.
• 풀이
  • 아래 그림에서 A 행렬의 -1인 원소의 행과 열을 노드로 하는 그래프를 생성한다. 간선은 행과 열에 -1인 원소가 있는지의 유무이며 가중치는 B 행렬의 원소이다. 그래프는 행 노드와 열 노드의 집합으로 나뉘므로 이분 그래프가 된다.
  • 그래프에서 간선은 B 행렬의 원소를 의미하며, 간선을 선택하게 되면 그 원소의 같은 행과 또는 열에 있는 원소들 중 하나를 선택할 수 있게 된다. (두 원소는 행 또는 열을 공유하기 때문) 아무튼 이런식으로 간선 하나(=B행렬 원소 하나)를 선택했을 때 연속해서 제거할 수 있는 간선들(=원소들)을 찾을 수 있다. 따라서 최대한 많이 정점을 포함하도록 하는 간선들의 집합(둘 이상일 수수 있음)에서 가장 작은 가중치들의 합이 찾고자 하는 최소 비용이 된다.
  • 가장 작은 가중치는 어떻게 찾을 수 있을까? Maximum Spannning Tree 를 생성해서 전체 가중치 합에서 MST의 가중치 합을 빼주면 된다. MST 를 다 만들었을 때 선택되지 않은 간선들은 가중치가 크지 않고 이미 포함된 정점에 대한 것이므로 그 간선들의 가중치 합은 찾고자 하는 스패닝 트리에서 가장 작은 가중치를 가진 간선들의 합이 된다.
  • MST를 만드는 방법으로는 Union-Find를 이용한 크루스칼 알고리즘이 있다.
  • Union-Find 를 이용하면 간선을 내림차순으로 정렬했을 때, 싸이클을 형성하기 까지 가중치가 큰 간선들의 합을 쉽게 구할 수 있다. 가중치가 큰 순서대로 간선들을 하나씩 스패닝 트리에 포함하면 되기 때문이다.

typedef pair<int,int> pii;
const int MAX_N = 501;

int N;
int A[MAX_N][MAX_N];
int B[MAX_N][MAX_N];

struct DisjointSet {
    vector<int> parent, rank;
    
    DisjointSet(int V) {
        for (int i = 0; i < V; i++) parent.push_back(i);
        rank = vector<int> (V, 0);
    }
    
    int find(int u) {
        if (u == parent[u]) return u;
        return parent[u] = find(parent[u]);
    }
    
    void merge(int u, int v) {
        u = find(u);
        v = find(v);
        if (u == v) return;
        if (rank[u] > rank[v]) swap(u, v);
        parent[u] = v; // rank[u] < rank[v]
        if (rank[u] == rank[v]) rank[v]++;
    }
};

int solve() {
    cin >> N;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> A[i][j];
    
    int totalWeights = 0;
    set<pair<int, pii>> edges;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> B[i][j];
            if (B[i][j] > 0)
                edges.insert({-B[i][j], {i, j+N}});
            totalWeights += B[i][j];
        }
    }
    
    for (int i = 0, tmp; i < N; i++) cin >> tmp;
    for (int i = 0, tmp; i < N; i++) cin >> tmp;
    
    int mst = 0; // Weights of Maximum Spanning Tree
    DisjointSet ds(N*2);
    for (auto& p : edges) {
        int weight = -p.first;
        int u = p.second.first;
        int v = p.second.second;
        if (ds.find(u) == ds.find(v))
            continue;
        mst += weight;
        ds.merge(u, v);
    }
    return totalWeights - mst;
}

이분 탐색(Binary Search) 문제들 중 최적화를 위해 결정 문제로 바꿔서 푸는 매개변수 탐색 문제가 있다. 가끔 나오는 문제다보니 풀 때마다 구간의 정의(lo와 hi) 및 결정 함수를 구현하는데 삽질을 많이해서 정리할 필요성을 느낌.

이 글을 읽기 전 알아야 할 정보

• 이분 탐색 구현 방법
• 매개 변수 탐색의 개념

구글링하면 자료가 많이 나오니 개념에 대한 설명은 여기로 대체하겠다. (굉장히 설명을 잘 해주셨다.)

매개 변수 탐색에서 마주한 문제는 매개변수의 구간을 정의하는 부분과 결정 함수를 구현하는 부분이다.

먼저, 매개변수의 구간을 정의한다는 것은 이분 탐색에서 lo 와 hi 의 의미를 아는 것에서 출발할 필요가 있다.

int binary_search(int lo, int hi, int value) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (A[mid] <= value) lo = mid;
        else hi = mid;
    }
    return A[lo];
}

탐색할 배열 A가 정렬되어 있으며 value 는 항상 A 에 있다고 가정한다.

따라서 lo < hi 에서 이진 탐색을 수행하므로 while 문에 들어가기 전에 A[lo] < A[hi] 가 성립한다.

while 문에 들어갈 때 lo + 1 < hi 라는 조건때문에 반복문 불변식으로 A[lo] < A[hi] 가 항상 성립한다.

• A[mid] <= value 여서 lo = mid 가 되는 경우, mid < hi 이므로 A[lo] < A[hi] 가 성립한다.
• A[mid] > value 여서 hi = mid 가 되는 경우, lo < mid 이므로 A[lo] < A[hi] 가 성립한다.
• lo 와 hi 가 1 씩 차이나면 mid <= hi 또는 lo <= mid 가 되어 불변식이 깨질 수 있는데, 조건은 항상 hi - lo > 1 이기 때문에 그럴 일은 없다.

while 문에서 빠져나왔을 때는 lo + 1 == hi 일 텐데 어쨌든 lo < hi 이므로 A[lo] < A[hi] 가 성립한다.

(이 조건이 깨지는 경우는 lo < hi 와 같이 잘못된 조건식으로 lo > hi 가 된 상태로 반복문을 빠져나올 때이다. lo + 1 < hi 를 기억하자.)

여기서 A[mid] <= value 일 때 lo = mid 이므로 반환하는 A[lo] 는 항상 value 이다. 만약 조건을 A[mid] < value 로 했다면 A[hi] 를 반환해야 할 것이다. 즉, 값을 찾는 조건에 따라 lo 와 hi 중 하나가 정답이 된다.

| 1 | 2 | 3 | 4 | 5 | 6 |
          ↑   ↑
         lo   hi

이분 탐색에서 while (lo + 1 < hi) 조건으로 탐색할 경우 최종 lo 와 hi 는 위와 같은 모습이다.

다시 매개 변수 탐색으로 돌아와서, 일반적으로 문제에서 최종적으로 구해야 하는 최솟값/최댓값이 찾아야 하는 매개변수이다. 이를 param 이라고 하겠다. 그리고 결정 함수를 다음과 같이 정의하겠다.

fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환

여기서 param 의 범위는 이분 탐색에서 배열 A가 오름차순이라고 했던 것과 유사하게 연속이어야 하는데, param 값이 연속인 것 말고도 fn(param) 의 결과도 연속이어야 한다.

즉, param 가 구간 [lo, hi] 사이의 값일 때, fn(param) 는 [false, false, ..., false, true, ..., true, true] 또는 [true, true, ..., true, false, ..., false, false] 여야 한다. 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데 이 부분은 1번만 존재해야 하며, 만약 여러 개 있다면 이분 탐색이 아니라 삼분 탐색 등 다른 방법으로 문제를 해결해야 할 것이다. 이분 탐색은 실제로 1차 함수 f 를 가정하고 f(x) < 0 에서 f(x) > 0 으로 바뀌는 f(x) = 0 을 만족하는 x 값을 찾는 방법이다. 0은 그냥 예시이다. 정해진 값 y 가 있다면 0이 아니라 y가 될 것이다.

fn(param) 의 결과 중간에 false -> true 또는 true -> false 로 바뀌는 부분이 있는데, 여기서 true 를 반환하는 param 이 찾고자 하는 최솟값/최댓값이다.

어떤 조건을 만족하는 param 의 최솟값(=answer)을 찾는 문제를 생각해보자.

fn(param) 은 연속이라고 했기 때문에 param >= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [false, false, ..., false, true, ..., true, true] 이고, 다음이 성립한다.

• fn(answer - 1) = false
• fn(answer) = true
• fn(answer + 1) = true

여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.

| f | ... | f | t | ... | t |
            ↑   ↑
           lo   hi

param 의 구간이 [1, 6] 이라면 위와 아래는 의미가 동일하다. 단지 위의 배열은 fn(param) 의 결과이고 아래의 배열은 param 의 배열이라는 점이 차이이다.

| 1 | 2 | 3 | 4 | 5 | 6 |
          ↑   ↑
         lo   hi

어떤 조건을 만족하는 param 의 최솟값은 lo 가 아니라 hi 임을 알 수 있다. 따라서 이 경우에는 lo 가 아닌 hi 를 반환해야 한다.

bool fn(int param);

int binary_search(int lo, int hi) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (fn(mid)) hi = mid; // 참이면 왼쪽 구간을 탐색
        else lo = mid; // 거짓이면 오른쪽 구간을 탐색
    }
    return hi;
}

구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 왼쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 오른쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. false -> true 는 현재 param 보다 왼쪽에 위치하게 된다.

반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 왼쪽 구간은 전부 false 임을 알 수 있다. 따라서 false -> true 는 현재 param 보다 오른쪽에 위치하게 된다.

주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 - 1 로, hi = 구간의 최댓값 으로 정의해야 한다. hi 를 반환하기 때문에 lo = 구간의 최솟값이면 hi 는 구간의 최솟값이 될 수 없어서 (lo + 1 < hi 라는 조건에 의해) 구간의 최솟값이 정답일 경우 답을 반환할 수 없게 된다.

어떤 조건을 만족하는 param 의 최댓값(=answer)을 찾는 문제를 생각해보자.

fn(param) 은 연속이라고 했기 때문에 param <= answer 에 대해 fn(param) 은 항상 true 일 것이다. param 은 오름차순이니 fn(param) 의 결과는 param 에 따라 [true, true, ..., true, false, ..., false, false] 이고, 다음이 성립한다.

• fn(answer - 1) = true
• fn(answer) = true
• fn(answer + 1) = false

여기서 param 의 구간을 [lo, hi] 라고 정의할 때 while(lo + 1 < hi) 조건으로 반복문을 돌리면 최종적으로 아래와 같이 lo 와 hi 를 얻게 된다.

| t | ... | t | f | ... | f |
            ↑   ↑
           lo   hi

최솟값 구할 때랑 배열이 반대로 결과가 나온다. 어떤 조건을 만족하는 param 의 최댓값은 lo 임을 알 수 있다. 따라서 이 경우에는 lo를 반환해야 한다.

bool fn(int param);

int binary_search(int lo, int hi) {
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (fn(mid)) lo = mid; // 참이면 오른쪽 구간을 탐색
        else hi = mid; // 거짓이면 왼쪽 구간을 탐색
    }
    return lo;
}

배열이 반대이기 때문에 탐색하는 방법도 반대라는 것에 주의하자.

구간을 좁히는 조건문을 보면, 조건을 만족할 때마다 오른쪽 구간을 탐색하는데 그 이유는 현재 param 에 대해 fn 이 true 이면 왼쪽 구간은 전부 true 이니 볼 필요가 없기 때문이다. true -> false 는 현재 param 보다 오른쪽에 위치하게 된다.

반대로 조건을 만족하지 않으면 현재 param 에 대해 fn 이 false 이므로 오른쪽 구간은 전부 false 임을 알 수 있다. 따라서 true -> false 는 현재 param 보다 왼쪽에 위치하게 된다.

주의사항: 처음에 lo 와 hi 구간을 정의할 때, lo = 구간의 최솟값 으로, hi = 구간의 최댓값 + 1 로 정의해야 한다. lo 를 반환하기 때문에 hi 가 구간의 최댓값이면 lo 는 구간의 최댓값이 정답이어도 lo + 1 < hi 라는 조건 때문에 반환할 수 없게 된다.

정리하자면,

1. 문제에서 최종적으로 찾고자하는 최솟값/최댓값을 매개변수로 본다.
2. 결정 함수를 정의하고 구현했을 때 결과 배열이 연속인지 확인한다.
3. 최솟값이면 결정 함수의 결과가 [f,f,...,t,t] 에서 f->t 로 바뀌는 부분을 찾는다.
   • 결정 함수가 true 이면, 오른쪽 구간은 전부 true 이니, f->t 가 있는 왼쪽 구간을 탐색한다. hi = mid
   • 결정 함수가 false 이면, 왼쪽 구간은 전부 false 이니, f->t 가 있는 오른쪽 구간을 탐색한다. lo = mid
   • 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = false, fn(hi) = true 이다. 따라서 hi를 반환한다.
4. 최댓값이면 결정 함수의 결과가 [t,t,...,f,f] 에서 t->f 로 바뀌는 부분을 찾는다.
   • 결정 함수가 true 이면, 왼쪽 구간은 전부 true 이니, t->f 가 있는 오른쪽 구간을 탐색한다. lo = mid
   • 결정 함수가 false 이면, 오른쪽 구간은 전부 false 이니, t->f 가 있는 왼쪽 구간을 탐색한다. hi = mid
   • 반복문을 빠져나오면, lo < hi 이므로 fn(lo) = true, fn(hi) = false 이다. 따라서 lo 를 반환한다.

결정 함수의 구현

fn(param) := param 이 어떤 조건을 만족하면 true를 반환하고 아니면 false를 반환

"어떤 조건을 만족" 하는 것은 param 이상/이하일 때 M개의 그룹으로 나눌 수 있는가 또는 M개로 분할할 수 있는가 등을 묻는 것이라고 볼 수 있다. (대개 문제들이 그렇다.) 여기서 fn(param)의 결과 배열에 따라 즉, 최솟값/최댓값인지에 따라 M 에 대한 조건이 달라진다.

두 가지 흔한 예제를 살펴보자.

예제1) BOJ 2110번: 공유기 설치

문제 요약: C개의 공유기를 N개의 집에 적당히 설치해서, 가장 인접한 두 공유기 사이의 거리를 최대화

"가장 인접한 두 공유기의 거리를 최대(=answer)화" 하라는 의미는 모든 인접한 두 공유기의 간격이 answer 보다는 크거나 같아야 함을 의미한다. param 을 두 공유기의 간격이라고 하면 결정 함수는 다음과 같이 정의할 수 있다.

param := 두 공유기의 간격

fn(param) := 인접한 두 공유기 사이의 거리 >= param 이 되도록 C 개의 공유기를 설치할 수 있는가

위와 같이 결정 함수를 정의하면 최대 param (=answer) 이하로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있게 된다. 즉, 거리가 3이상이 되도록 C개를 설치할 수 있으면 당연히 거리가 2이상이 되도록 C개를 설치할 수 있다.

이제 fn(param) 의 결과 배열이 [true, true, ..., true, false, ..., false, false] 인 것을 알았다.

true -> false 를 찾자.

int search() {
    // X는 오름차순 정렬이라 가정
    int lo = 1, hi = X[N-1] + 1;
    while (lo + 1 < hi) {
        int mid = (lo + hi) << 1;
        if (fn(mid)) lo = mid; // 현재 cond 보다 오른쪽 구간에 t->f 가 존재
        else hi = mid; // 현재 cond 보다 왼쪽 구간에 t->f 가 존재
    }
    return lo; // 반복문 불변식: fn(lo) = t, fn(hi) = f.
}

결정 함수를 구현할 때는 설치된 공유기 개수가 C 개 인지 확인하는 조건에 주의해야 한다.

두 집 사이의 거리 >= param 을 만족할 때마다 공유기를 설치한다고 하자.

공유기가 C개 보다 많이 설치된 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param을 늘려주어야 한다. 따라서 true 를 반환해야 현재 param 보다 오른쪽 구간에서 param 을 탐색할 수 있다.

공유기가 C개 보다 적게 설치된 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param을 줄여야 한다. 따라서 false 를 반환해야 현재 param 보다 왼쪽 구간에서 param 을 탐색할 수 있다.

공유기 개수가 C개이면 조건을 만족하니 true 를 반환한다.

bool fn(int param) {
    int cnt = 1, prev = 0; // 첫번째 집에 공유기를 설치했다고 가정
    for (int i = 1; i < N; i++) {
        if (X[i] - X[prev] >= param) {
            cnt++;
            prev = i;
        }
    }
    return cnt >= C;
}

예제2) BOJ 2613: 숫자구슬

문제 요약: M개의 그룹으로 N개의 숫자구슬을 나눌 때, 그룹의 합의 최댓값을 최소화

param := 그룹의 합

fn(param) := 그룹의 합 <= param 이 되도록 M 개의 그룹으로 나눌 수 있는가

위와 같이 결정 함수를 정의하면 최소 param (=answer) 이상으로는 모든 fn(param) = true 가 되므로 이분 탐색으로 문제를 해결할 수 있다. 예를 들어, 그룹의 합이 4 이하가 되도록 M 개의 그룹으로 나눌 수 있으면, 합이 5 이하가 되도록 M 개의 그룹으로 나눌 수 있다.

이제 fn(param) 의 결과 배열이 [false, false, ..., false, true, ..., true, true] 인 것을 알았다.

false -> true 를 찾자.

int search() {
    int lo = 0, hi = accumulate(A, A + N, 0);
    while (lo + 1 < hi) {
        int mid = (lo + hi) >> 1;
        if (!fn(mid)) lo = mid; // 현재 param 보다 오른쪽 구간에 f -> t 가 존재
        else hi = mid; // 현재 param 보다 왼쪽 구간에 f -> t 가 존재
    }
    return hi;
}

결정 함수를 구현할 때는 그룹의 개수가 M 개인지 확인하는 조건에 주의해야 한다.

숫자 구슬의 합 > param 을 만족할 때마다 그룹을 나눈다고 하자.

그룹이 M 개 보다 많이 나뉘어진 경우, param 이 작아서 조건을 만족하는 경우가 많다는 의미로, param 을 늘려야 한다. 따라서 false 를 반환해야 현재 param보다 오른쪽 구간에서 param 을 탐색한다.

그룹이 M 개 보다 적게 나뉘어진 경우, param 이 커서 조건을 만족하는 경우가 적다는 의미로, param 을 줄여야 한다. 따라서 true 를 반환해야 현재 param보다 왼쪽 구간에서 param 을 탐색한다.

딱 M개인 경우 조건을 만족하므로 true 를 반환한다.

bool fn(int param) {
    int cnt = 1; // 그룹의 개수는 1개부터 시작
    for (int i = 0, psum = 0; i < N; i++) {
        if (A[i] > param) return false; // 숫자구슬 1개가 이미 param 을 넘어서면 false
        if (psum + A[i] > param) {
            psum = A[i];
            cnt++;
        } else psum += A[i];
    }
    return cnt <= M;
}

참고로 A[i] > param 일 때는 무조건 false 를 반환해야 한다. 아니면 계속 반복문이 수행될 수 있어서 결과가 잘못나올 수 있다.

이 문제는 그룹마다 구슬이 몇 개 들어있는지도 출력해야 하는데, 최솟값을 찾고나면 최솟값을 넘지 않도록 그룹 지은 다음 그룹의 개수가 M 보다 작으면 그룹의 합이 최대인 그룹을 제외하고 그룹 내 구슬을 1개씩 다른 그룹으로 나눠주면 된다.

기타 예제)

BOJ 3079 입국심사

BOJ 2805 나무자르기

BOJ 1654 랜선자르기

접미사 배열

• 접미사 배열이란 어떤 문자열의 접미사를 사전식 순서대로 나열한 배열을 말한다. by Wikipedia
• 문자열 "banana" 의 접미사는 다음과 같다.

Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

• 사전순으로 정렬하면 다음과 같다.

Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana

Naive Method

• 모든 접미사 문자열에 대해 비교한 경우: 비교할 때 O(N) 이 걸리고, 정렬할 경우 O(N*log(N)) 이 걸린다.
• 다음과 같은 방법으로 접미사 배열을 얻을 경우 O(N^2 * log(N)) 의 시간 복잡도를 갖는다.
• 일반적으로 문자열의 접미사를 모두 저장하기 보다는 접미사의 시작 위치만 저장하여 메모리를 절약한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct NaiveComparator {
  const string& s;
  NaiveComparator(const string& s) : s(s) {}
  bool operator() (int i, int j) {
    const char* ptr = s.c_str();
    return strcmp(ptr + i, ptr + j) < 0;
  }
};

// O(N^2 * log(N)), where N is the length of the given string.
vector<int> getSuffixArray(const string& s) {
  vector<int> sfx(s.size());
  generate(sfx.begin(), sfx.end(), [x=0]() mutable { return x++; });
  sort(sfx.begin(), sfx.end(), NaiveComparator(s));
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Manber-Myers Algorithm

• 접미사 배열 생성 시, O(N * log(N)^2) 의 시간복잡도를 갖는다.
• 아이디어는 정렬 시 매 비교마다 각 접미사의 t번째 글자를 기준으로 정렬을 해주는 것이다. 이 때 t는 2배씩 증가한다.
• 정렬을 여러 번 하는데도 빠르게 동작하는 이유는 이전에 비교한 결과를 이용하여 두 문자열의 대소비교를 O(1) 만에 끝낼 수 있기 때문이다. 즉, 정렬할 때 두 문자열의 모든 문자들을 살펴볼 필요가 없다.
• 아래에서 사용된 group[i]은 s[i]부터 시작하는 접미사가 속한 그룹으로, 첫 글자가 같으면 같은 그룹 번호를 가지는 것으로 시작한다. 따라서 초기값은 별도의 번호 없이 s[i]를 그룹 번호로 가진다.
  • 그리고 매 t번째 글자를 기준으로 정렬한 후, t번째 글자가 같은 것끼리 같은 그룹으로 묶는다. 즉, 처음 나뉜 그룹에서 인접한 접미사들이 다음 글자마다 그룹핑되는 것이다.
  • 매 정렬 후, 새 그룹 번호를 할당하는 이유는 t번째 글자마다 그룹핑을 다시하기 때문이다.
  • 비교되는 두 문자열 중 하나가 t보다 짧은 경우를 대비하여 group[n] = -1로 고정시켜놓음으로써 항상 i+t 와 j+t 가 n을 넘기지 않도록 해놓는다. t가 길이를 넘기기 이전에 맨 앞으로 보내지기 때문에 operator() 함수의 if문에서 필터링된다.
• t = 1 일 때 정렬하면, 첫 글자가 같은 접미사들은 sfx 배열 내에서 인접한 위치에 있게 된다.
• t = 2 일 때 정렬하면, 이미 첫 글자가 같은 접미사는 같은 그룹이므로 두번째 글자만 비교하여 순서가 바뀌게 된다.
• 4 < t < n 인 동안 위와 같이 계속 반복한다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

// O(N * log(N))
vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i];
    sfx[i] = i;
  }
  
  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      // 사전순으로 앞에 위치하면 현재 그룹 번호를 이전 그룹 번호보다 1 증가
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "banana";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

• 중간 결과를 출력해보면 t 가 증가할 때마다 정렬 결과가 변경되는 것을 알 수 있다.

Initial: 0 1 2 3 4 5 
Suffix Array:
0: banana
1: anana
2: nana
3: ana
4: na
5: a

[t = 1] sfx: 5 1 3 0 2 4 
Suffix Array:
5: a
1: anana
3: ana
0: banana
2: nana
4: na      <--- 아직 첫번째 글자만 비교했기 때문에 na 는 뒤에 있다.
----------------
[t = 2] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na      <--- 두번째 글자를 비교한 후 na가 앞으로 옮겨졌다.
2: nana
----------------
[t = 4] sfx: 5 3 1 0 4 2 
Suffix Array:
5: a
3: ana
1: anana
0: banana
4: na
2: nana
----------------

• "mississipi" 에서 t번째 글자마다 그룹핑을 다시하여 그룹 번호가 변경된다.

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
using namespace std;

struct Comparator {
  vector<int> group;
  int t;
  Comparator(vector<int>& group, int t) : group(group), t(t) {}
  bool operator() (int i, int j) {
    if (group[i] != group[j]) return group[i] < group[j];
    return group[i+t] < group[j+t];
  }
};

vector<int> getSuffixArray(const string& s) {
  int n = s.size(), t = 1;
  vector<int> group(n+1, -1), sfx(n);
  for (int i = 0; i < n; i++) {
    group[i] = s[i]-'a';
    sfx[i] = i;
  }
  
  // DEBUG
  cout << "Initial: ";
  for (int i = 0; i < n; i++) cout << sfx[i] << " ";
  cout << endl << "Suffix Array:" << endl;
  for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
  cout << endl;

  while (t < n) {
    Comparator comparator(group, t);
    sort(sfx.begin(), sfx.end(), comparator);
    t *= 2;
    vector<int> newGroup(n+1, -1);
    newGroup[sfx[0]] = 0;
    for (int i = 1; i < n; i++) {
      newGroup[sfx[i]] = newGroup[sfx[i-1]];
      if (comparator(sfx[i-1], sfx[i])) newGroup[sfx[i]]++;
    }
    
    // DEBUG
    cout << "t = " << t << ": ";
    for (int i = 0; i < n; i++) cout << sfx[i] << " ";
    cout << endl << "Suffix Array:" << endl;
    for (auto i : sfx) cout << "Group[" << i << "] = " << group[i] << ": " << s.substr(i) << endl;
    cout << "----------------" << endl;
    
    group = newGroup;
  }
  return sfx;
}

int main() {
  string s = "mississipi";
  vector<int> sfx = getSuffixArray(s);
  return 0;
}

Initial: 0 1 2 3 4 5 6 7 8 9 
Suffix Array:
Group[0] = 12: mississipi
Group[1] = 8: ississipi
Group[2] = 18: ssissipi
Group[3] = 18: sissipi
Group[4] = 8: issipi
Group[5] = 18: ssipi
Group[6] = 18: sipi
Group[7] = 8: ipi
Group[8] = 15: pi
Group[9] = 8: i

t = 2: 9 7 1 4 0 8 3 6 2 5 
Suffix Array:
Group[9] = 8: i
Group[7] = 8: ipi
Group[1] = 8: ississipi
Group[4] = 8: issipi
Group[0] = 12: mississipi
Group[8] = 15: pi
Group[3] = 18: sissipi
Group[6] = 18: sipi
Group[2] = 18: ssissipi
Group[5] = 18: ssipi
----------------
t = 4: 9 7 1 4 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[1] = 2: ississipi      <---- 같은 그룹 내에서 4번째 글자 기준으로 그룹핑이 다시 된다.
Group[4] = 2: issipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 5: sissipi
Group[5] = 6: ssipi
Group[2] = 6: ssissipi
----------------
t = 8: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 2: ississipi
Group[0] = 3: mississipi
Group[8] = 4: pi
Group[6] = 5: sipi
Group[3] = 6: sissipi
Group[5] = 7: ssipi
Group[2] = 8: ssissipi
----------------
t = 16: 9 7 4 1 0 8 6 3 5 2 
Suffix Array:
Group[9] = 0: i
Group[7] = 1: ipi
Group[4] = 2: issipi
Group[1] = 3: ississipi
Group[0] = 4: mississipi
Group[8] = 5: pi
Group[6] = 6: sipi
Group[3] = 7: sissipi
Group[5] = 8: ssipi
Group[2] = 9: ssissipi
----------------

최장 공통 접두사 배열

• 접미사 배열에서 이전 접미사와 공통되는 접두사의 길이를 저장한 배열이다. by Wikipedia
• 알고리즘 대회에서는 어떤 문자열이 주어질 때 2번 이상 반복되는 연속되는 부분 문자열의 최대 갈이를 구할 때 주로 사용된다.
  • 해결책은 어떤 부분 문자열은 주어진 문자열의 접미사의 접두사라는 점을 이용하여 인접한 접미사끼리 공통되는 부분 중 가장 긴 것을 찾아내는 것이다.
• LCP 배열의 경우, 문자열의 길이가 길면 접미사를 비교하는데 시간이 오래걸리는 점을 보완하기 위해 인접한 접미사끼리 비교할 때 공통되는 문자들은 건너뛰어 시간을 절약한다. 예를 들면, mississipi 에서 접미사 ipi 와 issipi 를 비교할 때 이전에 i와 ipi 가 비교되었기 때문에 i는 세지 않고 바로 다음 글자인 p와 s부터 길이를 측정하는 것이다.
• 주의할 점은 LCP 배열을 만들 때, 문자열 비교 시간을 절약하기 위해 첫번째 위치에서부터 비교해야 하므로 prevSfx 처럼 접미사 배열에서 이전 접미사의 위치를 저장할 필요가 있다. 0번째 접미사는 이전 접미사가 없으므로 -1을 저장한다.

// 위와 동일

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s = "mississipi";
    vector<int> sfx = getSuffixArray(s);
    for (int x : sfx) cout << s.substr(x) << endl;
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    int maxLen = 0, start = 0;
    for (int i = 0; i < lcp.size(); i++) {
        if (maxLen < lcp[i]) {
            maxLen = lcp[i];
            start = i;
        }
    }
    cout << "LongestCommonPrefix: " << s.substr(start, maxLen) << endl;
    return 0;
}

/*
i
ipi
issipi
ississipi
mississipi
pi
sipi
sissipi
ssipi
ssissipi
LongestCommonPrefix: issi
*/

• 소스 코드: 익명 함수 사용 시, 훨씬 빠르다.

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

vector<int> getSuffixArray(const string& s) {
    int n = s.size();
    vector<int> g(n+1, -1), sfx(n), ng;
    for (int i = 0; i < n; i++) { g[i] = s[i]; sfx[i] = i; }
    
    for (int t = 1; t < n; t <<= 1, g = ng) {
        auto cmp = [&](int i, int j)->bool {
            if (g[i] != g[j]) return g[i] < g[j];
            return g[i+t] < g[j+t];
        };
        sort(sfx.begin(), sfx.end(), cmp);
        ng.clear(); ng.resize(n+1, -1); ng[sfx[0]] = 0;
        for (int i = 1; i < n; i++) {
            ng[sfx[i]] = ng[sfx[i-1]];
            if (cmp(sfx[i-1], sfx[i])) ng[sfx[i]]++;
        }
    }
    
    return sfx;
}

vector<int> getLongestCommonPrefix(const string& s, const vector<int>& sfx) {
    int n = s.size();
    vector<int> plcp(n), prevSfx(n), lcp(n);
    prevSfx[sfx[0]] = -1;
    for (int i = 1; i < n; i++) prevSfx[sfx[i]] = sfx[i-1];
    for (int i = 0, common = 0; i < n; i++) {
        if (prevSfx[i] == -1) plcp[i] = 0;
        else {
            while (s[i+common] == s[prevSfx[i]+common]) common++;
            plcp[i] = common;
            if (common > 0) common--;
        }
    }
    for (int i = 0; i < n; i++) lcp[i] = plcp[sfx[i]];
    return lcp;
}

int main() {
    string s; cin >> s;
    vector<int> sfx = getSuffixArray(s);
    vector<int> lcp = getLongestCommonPrefix(s, sfx);
    for (int x : sfx) cout << x+1 << " ";
    cout << endl << "x" << " ";
    for (int i = 1; i < lcp.size(); i++) cout << lcp[i] << " ";
    cout << endl;
    return 0;
}

Algorithmic Problem Solving Strategies - Chapter 04

• vector operation

const double PI = 2.0 *acos(0.0);

struct vector2 {
    double x, y;

    // 생성자를 explicit 으로 저장하면 vector2 를 넣을 곳에 잘못해
    // 실수가 들어가는 일을 방지해준다.
    explicit vector2(double x_ = 0, double y_ = 0) : x(x_), y(y_)
    {}

    // 두 벡터의 비교
    bool operator == (const vector2 &rhs) const {
        return x == rhs.x && y == rhs.y;
    }

    bool operator < (const vector2 &rhs) const {
        return x != rhs.x ? x < rhs.x : y < rhs.y;
    }

    // 벡터의 덧셈과 뺄셈
    vector2 operator + (const vector2 &rhs) const {
        return vector2(x + rhs.x, y + rhs.y);
    }

    vector2 operator - (const vector2 &rhs) const {
        return vector2(x - rhs.x, y - rhs.y);
    }

    // 실수로 곱셈
    vector2 operator * (double rhs) const {
        return vector2(x * rhs, y * rhs);
    }

    // 벡터의 길이를 반환
    double norm() const { return hypot(x, y); }

    // 방향이 같은 단위 벡터(unit vector)를 반환한다.
    // 영벡터에 대해 호출한 경우 반환 값은 정의되지 않는다.
    vector2 normalize() const {
        return vector2(x / norm(), y / norm());
    }

    // x축의 양의 방향으로부터 이 벡터까지 반시계 방향으로 잰 각도
    double polar() const {
        return fmod(atan2(y,x) + 2*PI, 2*PI);
    }

    // 내적
    double dot(const vector2 &rhs) const {
        return x * rhs.x + y * rhs.y;
    }

    // 외적
    double cross(const vector2 &rhs) const {
        return x * rhs.y - y * rhs.x;
    }

    // 이 벡터를 rhs 에 사영한 결과
    vector2 project(const vector2 &rhs) const {
        vector2 r = rhs.normalize();
        return r * r.dot(*this);
    }
};

// 점 p,a,b 가 주어졌을 때 a 가 b 보다 p 에 얼마나 더 가까운가.
double howMuchCloser(vector2 p, vector2 a, vector2 b) {
    return (b - p).norm() - (a - p).norm();
}

// 두 벡터의 방향성을 판단하는 함수
// 원점에서 벡터 b가 벡터 a의 반시계 방향이면 양수, 시계 방향이면 음수,
// 평행이면 0을 반환
double ccw(vector2 a, vector2 b) {
    return a.cross(b);
}

// 점 p를 기준으로 벡터 b가 벡터 a의 반시계 방향이면 양수,
// 시계 방향이면 음수, 평행이면 0을 반환한다.
double ccw(vector2 p, vector2 a, vector2 b) {
    return ccw(a - p, b - p);
}


// 두 직선의 교차점을 계산하는 함수
// (a,b) 를 포함하는 선과 (c,d)를 포함하는 선의 교점을 x 에 반환
// 두 선이 평행이면 (겹치는 경우를 포함) 거짓을, 아니면 참을 반환
bool lineIntersection(vector2 a, vector2 b,
                      vector2 c, vector2 d,
                      vector2 &x)
{
    // a + pb = c + qd 방정식을 이용해서
    // x값과 y값 각각에 해당되는 연립 방정식을 얻으면
    // 분모가 0 인 경우를 제외하고 아래의 식대로 p를 얻는다.
    // p = ((c-a)*d)/(b*d)
    // 여기서 구한 p를 a + pb 에 대입해 원하는 점을 구한다.
    double det = (b - a).cross(d - c); // 행렬식
    // 두 선이 평행한 경우: 행렬식 = 0
    if (fabs(det) < EPSILON) return false;
    double p = ((c - a).cross(d - c) / det);
    x = a + (b-a) * p;
    return true;
}


// 선분과 선분의 교차점을 계산하는 함수
// (a,b)와 (c,d)가 평행한 두 선분일 때 이들이 한 점에서 겹치는지 확인한다.
bool parallelSegments(vector2 a, vector2 b,
                      vector2 c, vector2 d,
                      vector2 &p)
{
    // 평행일 때 가능한 경우의 수
    // 1. 두 선분이 서로 겹치지 않음
    // 2. 두 선분이 한 점에서 닿음
    // 3. 두 선분이 겹쳐짐
    // 4. 한 선분이 다른 선분 안에 포함됨
    if (b < a) swap(a, b);
    if (d < c) swap(c, d);
    // 한 직선 위에 없거나 두 선분이 겹치지 않는 경우를 우선 걸러낸다.
    if (ccw(a,b,c) != 0 || b < c || d < a) return false;
    // 두 선분이 확실히 겹치므로, 교차점을 찾는다.
    if (a < c) p = c; // a와 b 사이에 c가 있는 경우
    else p = a; // c와 d 사이에 a가 있는 경우
    return true;
}

// p가 (a,b)를 감싸면서 각 변이 x, y축에 평행한 최소 사각형 내부에 있는지 확인
// a, b, p 는 일직선 상에 있다고 가정한다.
bool inBoundingRectangle(vector2 p, vector2 a, vector2 b) {
    if (b < a) swap(a, b);
    return p == a || p == b || (a < p && p < b);
}

// (a,b) 선분과 (c,d) 선분의 교점을 p에 반환한다.
// 교점이 여러 개일 경우 아무 점이나 반환한다.
// 두 선분이 교차하지 않을 경우 false를 반환한다.
bool segmentIntersection(vector2 a, vector2 b,
                         vector2 c, vector2 d,
                         vector2 &p)
{
    // 두 직선이 평행인 경우를 우선 예외로 처리한다.
    if (!lineIntersection(a,b,c,d,p))
        return parallelSegments(a,b,c,d,p);
    // p가 두 선분에 포함되어 있는 경우에만 참을 반환한다.
    return inBoundingRectangle(p,a,b) &&
           inBoundingRectangle(p,c,d);
}


// 선분과 선분의 교차점을 계산하는 함수 (교차점이 필요 없을 때)
bool segmentIntersects(vector2 a, vector2 b,
                       vector2 c, vector2 d)
{
    // 교차한다면, a를 기준으로 b는 c와 d 사이에 있어야 한다.
    // 즉, c가 b에서 떨어진 방향과 d가 떨어진 방향은 곱했을 때 음수어야 한다.
    double ab = ccw(a,b,c) * ccw(a,b,d);
    double cd = ccw(c,d,a)  * ccw(c,d,b);
    // 두 선분이 한 직선 위에 있거나 끝점이 겹치는 경우
    if (ab == 0 && cd == 0) {
        if (b < a) swap(a,b);
        if (d < c) swap(c,d);
        return !(b < c || d < a);
    }
    return ab <= 0 && cd <= 0;
}


// 점과 선분 사이의 거리를 계산하는 함수
// 점 p에서 (a,b) 직선에 내린 수선의 발을 구한다.
vector2 prependicularFoot(vector2 p, vector2 a, vector2 b) {
    return a + (p - a).project(b - a);
}

// 점 p와 (a,b) 직선 사이의 거리를 구한다.
double pointToLine(vector2 p, vector2 a, vector2 b) {
    return (p - prependicularFoot(p,a,b)).norm();
}

• polygon operation using vector

typedef vector<vector2> polygon;

// 단순 다각형의 넓이를 구하는 함수
// 주어진 단순 다각형 p의 넓이를 구한다.
// p는 각 꼭지점의 위치 벡터의 집합으로 주어진다.
double area(const polygon &p) {
    double result = 0;
    for (int i=0; i<p.size(); i++) {
        int j = (i+1) % p.size();
        result += p[i].x * p[j].y - p[j].x * p[i].y;
    }
    return fabs(result) / 2.0; // 오목 다각형을 고려하여 절댓값으로 반환
}

// 주어진 점이 단순 다각형 내부에 포함되어 있는지 확인하는 함수
// 점 q가 다각형 p 안에 포함되어 있을 경우 참, 아닌 경우 거짓을 반환
// q가 다각형의 경계 위에 있는 경우의 반환 값은 정의되어 있지 않다.
bool isInside(vector2 q, const polygon &p) {
  int crosses = 0;
  for (int i=0; i<p.size(); i++) {
    int j = (i + 1) % p.size();
    // (p[i], p[j])가 반직선을 세로로 가로지르는가?
    if ((p[i].y > q.y) != (p[j].y > q.y)) {
      // 가로지르는 경우: x 좌표를 계산 (직선의 방정식 이용)
      double atX = (p[j].x - p[i].x) * (q.y - p[i].y) / (p[j].y - p[i].y) + p[i].x;
      if (q.x < atX) {
        crosses++;
      }
    }
  }
  return crosses % 2 > 0; // 홀수 개면 안에, 짝수 개면 밖에 있음.
}

// 반평면과 단순 다각형의 교집합을 구한다.
// (a,b)를 포함하는 직선으로 다각형 p를 자른 뒤, (a,b)의 왼쪽에 있는 부분들을 반환
polygon cutPoly(const polygon &p,
                const vector2 &a, const vector2 &b)
{
    int n = p.size();
    // 각 점이 반평면 내에 있는지 여부를 우선 확인
    vector<bool> inside(n);
    for (int i=0; i<n; i++)
      inside[i] = ccw(a,b,p[i]) >= 0;
    polygon ret;
    // 다각형의 각 변을 순회하면서 결과 다각형의 각 점을 발견
    for (int i=0; i<n; i++) {
      int j = (i+1) % n;
      // 반평면 내에 있는 점 p[i]는 항상 결과 다각형에 포함
      if(inside[i]) ret.push_back(p[i]);
      // 변 p[i] - p[j] 가 직선과 교차하면 교차점을 결과 다각형에 포함
      if (inside[i] != inside[j]) {
        vector2 cross;
        assert(lineIntersection(p[i], p[j], a, b, cross));
        ret.push_back(cross);
      }
    }
    return ret;
}


// 서덜랜드-호지맨 (Sutherland-Hodgman) 알고리즘을 이용한 다각형 클리핑
polygon intersection(const polygon &p, double x1, double y1,
                     double x2, double y2)
{
    vector2 a(x1, y1), b(x2, y1), c(x2, y2), d(x1, y2);
    polygon ret = cutPoly(p, a, b);
    ret = cutPoly(ret, b, c);
    ret = cutPoly(ret, c, d);
    ret = cutPoly(ret, d, a);
    return ret;
}

// 두 볼록 다각형의 교차 여부를 확인하는 함수
// 두 다각형이 서로 닿거나 겹치는지 여부를 반환한다.
// 한 점이라도 겹친다면 true를 반환
bool polygonIntersects(const polygon &p, const polygon &q) {
  int n = p.size(), m = q.size();
  // 우선 한 다각형이 다른 다각형에 포함되어 있는 경우를 확인하자.
  if (isInside(p[0], q) || isInside(q[0], p)) return true;
  // 이 외의 경우, 두 다각형이 서로 겹친다면 서로 닿는 두 변이 반드시 존재한다.
  for (int i=0; i<n; i++)
      for (int j=0; j<m; j++)
        if (segmentIntersects(p[i], p[(i+1)%n], q[j], q[(j+1)%m]))
          return true;
  return false;
}