콘텐츠로 이동

반평면 교집합

이 글에서는 반평면 집합의 교집합을 계산하는 문제를 다룹니다. 이러한 교집합은 볼록 영역/다각형으로 편리하게 나타낼 수 있으며, 그 내부의 모든 점은 모든 반평면의 내부에도 속합니다. 우리가 찾거나 구성하려는 것이 바로 이 다각형입니다. 먼저 이 문제에 대한 직관을 제시하고, Sort-and-Incremental 알고리즘으로 알려진 $O(N \log N)$ 접근법을 설명한 뒤, 이 기법의 몇 가지 응용 예시를 소개합니다.

독자는 기본적인 기하 요소와 연산(점, 벡터, 직선의 교차)에 익숙해 두기를 강력히 권장합니다. 또한 볼록 껍질이나 볼록 껍질 트릭에 대해 알고 있으면 이 글의 개념을 이해하는 데 도움이 될 수 있지만, 결코 필수 선행 지식은 아닙니다.

사전 설명과 정의

이 글 전체에서 (별도로 명시하지 않는 한) 다음과 같은 몇 가지 가정을 합니다:

  1. 주어진 집합에 있는 반평면의 개수를 $N$으로 정의합니다.
  2. 직선과 반평면은 하나의 점과 하나의 벡터(주어진 직선 위에 있는 임의의 점과 그 직선의 방향 벡터)로 나타냅니다. 반평면의 경우, 모든 반평면은 자신의 방향 벡터 왼쪽 영역을 허용한다고 가정합니다. 또한 반평면의 각도를 그 방향 벡터의 편각으로 정의합니다. 예시는 아래 그림을 참고하십시오.
  3. 결과로 얻는 교집합은 항상 유계이거나 공집합이라고 가정합니다. 유계가 아닌 경우를 처리해야 한다면, 충분히 큰 경계 상자를 정의하는 반평면 4개를 추가하기만 하면 됩니다.
  4. 편의를 위해 주어진 집합에 평행한 반평면이 없다고 가정합니다. 글의 끝부분에서 이러한 경우를 처리하는 방법을 다룹니다.

반평면 $y \geq 2x - 2$는 점 $P = (1, 0)$과 방향 벡터 $PQ = Q - P = (1, 2)$로 나타낼 수 있습니다

브루트 포스 접근법 - $O(N^3)$

가장 단순하고 명백한 풀이 중 하나는 모든 반평면 쌍에 대해 그 직선들의 교점을 계산하고, 각 교점이 다른 모든 반평면의 내부에 있는지 확인하는 것입니다. 교점이 $O(N^2)$개 있고 각 교점마다 $O(N)$개의 반평면을 확인해야 하므로, 전체 시간 복잡도는 $O(N^3)$입니다. 그런 다음 실제 교집합 영역은, 예를 들어 모든 반평면에 포함된 교점들의 집합에 볼록 껍질 알고리즘을 적용하여 재구성할 수 있습니다.

이 방법이 왜 올바르게 동작하는지는 쉽게 알 수 있습니다. 결과로 얻는 볼록 다각형의 정점은 모두 반평면 직선들의 교점이며, 각 정점은 당연히 모든 반평면에 속합니다. 이 방법의 주요 장점은 교집합이 비어 있는지만 확인하면 되는 경우에 이해하고 기억하기 쉬우며 즉석에서 구현하기도 쉽다는 점입니다. 하지만 이 방법은 매우 느려서 대부분의 문제에 적합하지 않으므로, 더 빠른 방법이 필요합니다.

점진적 접근법 - $O(N^2)$

또 다른 꽤 간단한 접근법은 반평면들의 교집합을 한 번에 하나씩 점진적으로 구성하는 것입니다. 이 방법은 기본적으로 볼록 다각형을 직선으로 $N$번 자르면서 매 단계마다 불필요한 반평면을 제거하는 것과 같습니다. 이를 위해 볼록 다각형을 선분들의 리스트로 표현할 수 있습니다. 반평면으로 다각형을 자를 때는 선분들과 반평면 경계선의 교점을 찾고(직선이 다각형과 제대로 교차한다면 교점은 두 개뿐입니다), 두 교점 사이의 선분들을 모두 해당 반평면에 대응하는 새 선분으로 교체하기만 하면 됩니다. 이러한 절차는 선형 시간에 구현할 수 있으므로, 큰 경계 상자에서 시작하여 각 반평면으로 차례로 잘라 나가기만 하면 되며, 전체 시간 복잡도는 $O(N^2)$입니다.

이 방법은 올바른 방향으로 크게 한 걸음 나아간 것이지만, 매 단계마다 $O(N)$개의 반평면을 순회해야 한다는 점은 낭비처럼 느껴집니다. 다음으로, 몇 가지 영리한 관찰을 통해 이 점진적 접근법의 아이디어를 재활용하여 $O(N \log N)$ 알고리즘을 만들 수 있음을 살펴보겠습니다.

정렬 후 점진적 구성 알고리즘 - $O(N \log N)$

저희가 찾을 수 있었던 이 알고리즘에 대한 최초의 제대로 문서화된 출처는 Zeyuan Zhu가 2006년 중국 대표 선발 대회(Chinese Team Selecting Contest)를 위해 작성한 반평면 교집합을 위한 새로운 알고리즘과 그 실용적 가치(New Algorithm for Half-plane Intersection and its Practical Value)라는 제목의 논문입니다. 다음에 설명할 접근법도 이 알고리즘에 기반합니다. 다만 교집합의 아래쪽 절반과 위쪽 절반에 대해 교집합을 따로 두 번 계산하는 대신, 덱(양방향 큐)을 사용하여 한 번의 순회로 전체를 한꺼번에 구성합니다.

이름에서 짐작할 수 있듯이, 이 알고리즘은 반평면들의 교집합으로 생기는 영역이 볼록하다는 사실을 활용합니다. 따라서 그 영역은 각도순으로 정렬된 반평면들의 일부 선분들로 이루어집니다. 이로부터 중요한 관찰을 얻을 수 있습니다. 반평면들을 각도순으로(최종 교집합 도형에 나타나는 순서대로) 점진적으로 교차시키면서 양방향 큐에 저장하면, 반평면을 제거할 때 덱의 앞과 뒤에서만 제거하면 됩니다.

이 사실을 더 잘 시각화하기 위해, 각도순으로 정렬된 반평면 집합(여기서는 $-\pi$부터 $\pi$까지 정렬되어 있다고 가정합니다)에 대해 앞서 설명한 점진적 접근법을 수행하는 중이며, 임의의 $k$번째 단계를 막 시작하려 한다고 가정합시다. 이는 처음 $k-1$개 반평면의 교집합을 이미 구성했다는 뜻입니다. 이제 반평면들이 각도순으로 정렬되어 있으므로, $k$번째 반평면이 무엇이든 $(K-1)$번째 반평면과 볼록한 회전을 이룬다고 확신할 수 있습니다. 그러므로 다음과 같은 몇 가지 일이 일어날 수 있습니다.

  1. 교집합의 뒤쪽에 있는 반평면 중 일부(하나도 없을 수도 있습니다)가 불필요해질 수 있습니다. 이 경우, 이제 쓸모없어진 이 반평면들을 덱의 뒤에서 꺼내야 합니다.
  2. 앞쪽에 있는 반평면 중 일부(하나도 없을 수도 있습니다)가 불필요해질 수 있습니다. 경우 1과 마찬가지로, 이들을 덱의 앞에서 꺼내기만 하면 됩니다.
  3. (경우 1 또는 2, 혹은 둘 다를 처리한 뒤) 교집합이 비게 될 수 있습니다. 이 경우, 교집합이 비어 있다고 보고하고 알고리즘을 종료하면 됩니다.

반평면이 교집합에 아무런 기여도 하지 않으면 그 반평면을 "불필요하다"고 합니다. 이러한 반평면은 제거해도 결과 교집합이 전혀 바뀌지 않습니다.

다음은 그림을 곁들인 작은 예시입니다.

$H = \{ A, B, C, D, E \}$를 현재 교집합에 존재하는 반평면들의 집합이라고 합시다. 또한 $P = \{ p, q, r, s \}$를 H에서 인접한 반평면들의 교점들의 집합이라고 합시다. 이제 아래 그림과 같이 이를 반평면 $F$와 교차시키려 한다고 가정합시다.

반평면 $F$로 인해 교집합에서 $A$와 $E$가 불필요해진다는 점에 주목하십시오. 따라서 $A$와 $E$를 각각 교집합의 앞과 뒤에서 제거하고, $F$를 끝에 추가합니다. 그러면 마침내 $P = \{ q, r, t, u \}$인 새로운 교집합 $H = \{ B, C, D, F\}$를 얻습니다.

이 모든 것을 염두에 두면 알고리즘을 실제로 구현하는 데 필요한 것은 거의 다 갖추었지만, 아직 몇 가지 특수한 경우를 다루어야 합니다. 글의 앞부분에서 교집합이 유계가 아닐 수 있는 경우를 처리하기 위해 경계 상자를 추가하겠다고 했으므로, 실제로 처리해야 하는 까다로운 경우는 평행한 반평면뿐입니다. 이는 두 가지 하위 경우로 나뉩니다. 두 반평면은 같은 방향으로 평행할 수도 있고, 반대 방향으로 평행할 수도 있습니다. 이 경우를 따로 처리해야 하는 이유는, 어떤 반평면이 불필요한지 확인하려면 반평면 직선들의 교점을 계산해야 하는데 평행한 두 직선에는 교점이 없으므로 이들을 다루는 특별한 방법이 필요하기 때문입니다.

반대 방향으로 평행한 반평면의 경우: 유계가 아닌 경우를 처리하기 위해 경계 상자를 추가하므로, 정렬 후 반대 방향의 평행한 두 반평면이 인접하는 경우도 함께 처리된다는 점에 주목하십시오. 이 두 반평면 사이에는 경계 상자의 반평면이 적어도 하나 있어야 하기 때문입니다(반평면들이 각도순으로 정렬되어 있다는 점을 기억하십시오).

  • 그러나 덱의 뒤쪽에서 반평면 몇 개를 제거하고 나면 반대 방향으로 평행한 두 반평면이 서로 붙게 될 수 있습니다. 구체적으로 이 경우는 두 반평면의 교집합이 공집합일 때에만 발생합니다. 이 마지막 반평면 때문에 덱의 모든 원소가 제거되기 때문입니다. 이 문제를 피하려면 평행한 반평면을 직접 확인해야 하며, 두 반평면의 방향이 반대라면 즉시 알고리즘을 멈추고 빈 교집합을 반환하면 됩니다.

따라서 실제로 처리해야 하는 경우는 같은 각도를 가진 반평면이 여러 개 있는 경우뿐이며, 이 경우는 꽤 쉽게 처리할 수 있습니다. 나머지는 어차피 완전히 불필요하므로 가장 왼쪽의 반평면만 남기고 나머지를 지우면 됩니다. 정리하면, 전체 알고리즘은 대략 다음과 같습니다.

  1. 먼저 반평면 집합을 각도순으로 정렬하며, 이는 $O(N \log N)$ 시간이 걸립니다.
  2. 반평면 집합을 순회하면서 각 반평면에 대해 증분 절차를 수행하고, 필요에 따라 양방향 큐의 앞과 뒤에서 원소를 꺼냅니다. 모든 반평면은 한 번씩만 추가되거나 제거될 수 있으므로, 이는 전체적으로 선형 시간이 걸립니다.
  3. 마지막으로, 교집합으로 얻어지는 볼록 다각형은 절차가 끝났을 때 덱에서 인접한 반평면들의 교점을 계산하여 간단히 얻을 수 있습니다. 이 역시 선형 시간이 걸립니다. 2단계에서 이러한 점들을 저장하여 이 단계를 완전히 생략할 수도 있지만, 저희는 (구현 측면에서) 그때그때 계산하는 편이 조금 더 쉽다고 생각합니다.

전체적으로 $O(N \log N)$의 시간 복잡도를 달성했습니다. 병목은 분명히 정렬이므로, 반평면이 미리 각도순으로 정렬되어 주어지는 특수한 경우에는 알고리즘이 선형 시간에 동작하도록 만들 수 있습니다(이러한 경우의 예로 볼록 다각형을 정의하는 반평면들을 구하는 경우를 들 수 있습니다).

직접 구현

다음은 대부분의 부분을 설명하는 주석이 달린 알고리즘의 직접 구현 예시입니다.

간단한 점/벡터 및 반평면 구조체:

// Redefine epsilon and infinity as necessary. Be mindful of precision errors.
const long double eps = 1e-9, inf = 1e9; 

// Basic point/vector struct.
struct Point { 

    long double x, y;
    explicit Point(long double x = 0, long double y = 0) : x(x), y(y) {}

    // Addition, subtraction, multiply by constant, dot product, cross product.

    friend Point operator + (const Point& p, const Point& q) {
        return Point(p.x + q.x, p.y + q.y); 
    }

    friend Point operator - (const Point& p, const Point& q) { 
        return Point(p.x - q.x, p.y - q.y); 
    }

    friend Point operator * (const Point& p, const long double& k) { 
        return Point(p.x * k, p.y * k); 
    } 

    friend long double dot(const Point& p, const Point& q) {
        return p.x * q.x + p.y * q.y;
    }

    friend long double cross(const Point& p, const Point& q) { 
        return p.x * q.y - p.y * q.x; 
    }
};

// Basic half-plane struct.
struct Halfplane { 

    // 'p' is a passing point of the line and 'pq' is the direction vector of the line.
    Point p, pq; 
    long double angle;

    Halfplane() {}
    Halfplane(const Point& a, const Point& b) : p(a), pq(b - a) {
        angle = atan2l(pq.y, pq.x);    
    }

    // Check if point 'r' is outside this half-plane. 
    // Every half-plane allows the region to the LEFT of its line.
    bool out(const Point& r) { 
        return cross(pq, r - p) < -eps; 
    }

    // Comparator for sorting. 
    bool operator < (const Halfplane& e) const { 
        return angle < e.angle;
    } 

    // Intersection point of the lines of two half-planes. It is assumed they're never parallel.
    friend Point inter(const Halfplane& s, const Halfplane& t) {
        long double alpha = cross((t.p - s.p), t.pq) / cross(s.pq, t.pq);
        return s.p + (s.pq * alpha);
    }
};

알고리즘: 

// Actual algorithm
vector<Point> hp_intersect(vector<Halfplane>& H) { 

    Point box[4] = {  // Bounding box in CCW order
        Point(inf, inf), 
        Point(-inf, inf), 
        Point(-inf, -inf), 
        Point(inf, -inf) 
    };

    for(int i = 0; i<4; i++) { // Add bounding box half-planes.
        Halfplane aux(box[i], box[(i+1) % 4]);
        H.push_back(aux);
    }

    // Sort by angle and start algorithm
    sort(H.begin(), H.end());
    deque<Halfplane> dq;
    int len = 0;
    for(int i = 0; i < int(H.size()); i++) {

        // Remove from the back of the deque while last half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[len-1], dq[len-2]))) {
            dq.pop_back();
            --len;
        }

        // Remove from the front of the deque while first half-plane is redundant
        while (len > 1 && H[i].out(inter(dq[0], dq[1]))) {
            dq.pop_front();
            --len;
        }

        // Special case check: Parallel half-planes
        if (len > 0 && fabsl(cross(H[i].pq, dq[len-1].pq)) < eps) {
            // Opposite parallel half-planes that ended up checked against each other.
            if (dot(H[i].pq, dq[len-1].pq) < 0.0)
                return vector<Point>();

            // Same direction half-plane: keep only the leftmost half-plane.
            if (H[i].out(dq[len-1].p)) {
                dq.pop_back();
                --len;
            }
            else continue;
        }

        // Add new half-plane
        dq.push_back(H[i]);
        ++len;
    }

    // Final cleanup: Check half-planes at the front against the back and vice-versa
    while (len > 2 && dq[0].out(inter(dq[len-1], dq[len-2]))) {
        dq.pop_back();
        --len;
    }

    while (len > 2 && dq[len-1].out(inter(dq[0], dq[1]))) {
        dq.pop_front();
        --len;
    }

    // Report empty intersection if necessary
    if (len < 3) return vector<Point>();

    // Reconstruct the convex polygon from the remaining half-planes.
    vector<Point> ret(len);
    for(int i = 0; i+1 < len; i++) {
        ret[i] = inter(dq[i], dq[i+1]);
    }
    ret.back() = inter(dq[len-1], dq[0]);
    return ret;
}

구현에 대한 논의

특히 주의할 점은, 같은 점에서 교차하는 반평면이 여러 개 있는 경우 이 알고리즘이 최종 다각형에서 반복되는 인접한 점들을 반환할 수 있다는 것입니다. 그러나 이는 교집합이 공집합인지 여부를 올바르게 판단하는 데 아무런 영향을 주지 않으며, 다각형의 넓이에도 전혀 영향을 주지 않습니다. 이후에 수행해야 하는 작업에 따라 이러한 중복을 제거하는 편이 좋을 수 있습니다. 이는 std::unique로 매우 쉽게 할 수 있습니다. 넓이가 0인 교집합(예를 들어 한 점, 직선 또는 선분으로 이루어진 교집합)을 올바르게 계산할 수 있도록 알고리즘을 실행하는 동안에는 반복되는 점들을 유지하려고 합니다. 교집합이 한 점이나 직선이 되는 작은 경우를 직접 만들어 시험해 보시기를 권합니다.

한 가지 더 다뤄야 할 것은 반평면이 선형 제약 조건의 형태(예를 들어 $ax + by + c \leq 0$)로 주어졌을 때 어떻게 해야 하는지입니다. 이 경우에는 두 가지 방법이 있습니다. 이러한 표현을 다룰 수 있도록 알고리즘을 적절히 수정하여 구현하거나(본질적으로 자신만의 반평면 구조체를 만드는 것으로, 볼록 껍질 트릭에 익숙하다면 상당히 간단할 것입니다), 각 직선에서 임의의 두 점을 취하여 직선을 이 글에서 사용한 표현으로 변환할 수 있습니다. 일반적으로는 추가적인 정밀도 문제를 피하기 위해 문제에서 주어진 표현을 그대로 사용하는 것을 권장합니다.

문제, 과제 및 응용

반평면 교집합으로 풀 수 있는 많은 문제는 반평면 교집합 없이도 풀 수 있지만, (대개) 더 복잡하거나 흔하지 않은 접근법이 필요합니다. 일반적으로 반평면 교집합은 다각형(주로 볼록 다각형), 평면에서의 가시성, 2차원 선형 계획법과 관련된 문제를 다룰 때 등장할 수 있습니다. 다음은 이 기법으로 풀 수 있는 몇 가지 예시 과제입니다:

볼록 다각형의 교집합

반평면 교집합의 고전적인 응용 중 하나입니다: $N$개의 다각형이 주어질 때, 모든 다각형의 내부에 포함되는 영역을 구하십시오.

반평면 집합의 교집합은 볼록 다각형이므로, 반대로 볼록 다각형을 반평면의 집합으로 나타낼 수도 있습니다(다각형의 모든 간선은 어떤 반평면의 경계선 위의 선분입니다). 모든 다각형에 대해 이러한 반평면을 생성하고 전체 집합의 교집합을 구하십시오. 전체 시간 복잡도는 $O(S \log S)$이며, 여기서 S는 모든 다각형의 변의 총 개수입니다. 이론적으로는 힙을 사용해 $N$개의 반평면 집합을 병합한 뒤 정렬 단계 없이 알고리즘을 실행하여 $O(S \log N)$에 풀 수도 있지만, 이러한 풀이는 단순한 정렬보다 상수 인자가 훨씬 나쁘며 매우 작은 $N$에 대해서만 약간의 속도 향상을 제공합니다.

평면에서의 가시성

"평면 위의 어떤 점(들)에서 일부 선분들이 보이는지 판단하라"와 같은 류의 것을 요구하는 문제는 대개 반평면 교집합 문제로 정식화할 수 있습니다. 예를 들어 다음 과제를 생각해 봅시다: 어떤 단순 다각형(반드시 볼록일 필요는 없음)이 주어질 때, 다각형 내부에 그 점에서 다각형의 경계 전체를 관찰할 수 있는 점이 존재하는지 판단하십시오. 이는 다각형의 커널을 찾는 문제로도 알려져 있으며, 다각형의 각 간선을 반평면으로 취한 뒤 그 교집합을 구하는 단순한 반평면 교집합으로 풀 수 있습니다.

다음은 Artem Vasilyev가 자신의 Brazilian ICPC Summer School 강의 중 하나에서 소개한, 관련 있으면서 더 흥미로운 문제입니다: 평면 위의 점 $p_1, p_2\ \dots \ p_n$으로 이루어진 집합 $p$가 주어질 때, $p$의 모든 점을 인덱스가 증가하는 순서대로 왼쪽에서 오른쪽으로 볼 수 있는 위치인 점 $q$가 존재하는지 판단하십시오.

이러한 문제는 어떤 점 $p_i$가 $p_j$의 왼쪽에 보인다는 것이 $p_i$에서 $p_j$로 향하는 선분의 오른쪽 면을 볼 수 있다는 것(또는 동등하게, $p_j$에서 $p_i$로 향하는 선분의 왼쪽 면을 볼 수 있다는 것)과 같다는 점에 주목하여 풀 수 있습니다. 이를 염두에 두면, 모든 선분 $p_i p_{i+1}$(또는 선택한 방향에 따라 $p_{i+1} p_i$)에 대해 반평면을 만들고 전체 집합의 교집합이 비어 있는지 확인하기만 하면 됩니다.

또 다른 흔한 활용은 반평면 교집합을 이진 탐색 절차의 조건을 검증하는 도구로 사용하는 것입니다. 다음은 이러한 문제의 예시로, 역시 앞서 언급한 같은 강의에서 Artem Vasilyev가 소개한 것입니다: 볼록 다각형 $P$가 주어질 때, 그 내부에 내접할 수 있는 가장 큰 원을 구하십시오.

닫힌 형태의 해, 번거로운 공식, 또는 난해한 알고리즘적 풀이를 찾는 대신, 답에 대해 이진 탐색을 시도해 봅시다. 어떤 고정된 $r$에 대해, 반지름이 $r$인 원이 $P$ 내부에 내접할 수 있는 것은 $P$ 내부에 $P$의 경계 위의 모든 점까지의 거리가 $r$ 이상인 점이 존재할 때뿐이라는 점에 주목하십시오. 이 조건은 다각형을 안쪽으로 $r$만큼 "축소"한 뒤 다각형이 퇴화하지 않고 남아 있는지(또는 그 자체로 점/선분인지) 확인하여 검증할 수 있습니다. 이러한 과정은 다각형의 변에 해당하는 반평면들을 반시계 방향 순서로 취하고, 각각을 그것이 허용하는 영역 방향으로(즉, 반평면의 방향 벡터에 수직인 방향으로) $r$만큼 평행 이동한 뒤, 교집합이 비어 있지 않은지 확인하는 방식으로 시뮬레이션할 수 있습니다.

당연히 반지름이 $r$인 원을 내접시킬 수 있다면, 반지름이 $r$보다 작은 다른 모든 원도 내접시킬 수 있습니다. 따라서 반지름 $r$에 대해 이진 탐색을 수행하고 각 단계를 반평면 교집합으로 검증할 수 있습니다. 또한 볼록 다각형의 반평면들은 이미 각도순으로 정렬되어 있으므로, 알고리즘에서 정렬 단계를 생략할 수 있다는 점에 유의하십시오. 따라서 전체 시간 복잡도는 $O(NK)$가 되며, 여기서 $N$은 다각형의 정점 수이고 $K$는 이진 탐색의 반복 횟수입니다(실제 값은 가능한 답의 범위와 원하는 정밀도에 따라 달라집니다).

2차원 선형 계획법

반평면 교집합은 두 변수에 대한 선형 계획법에도 응용할 수 있습니다. 두 변수에 대한 모든 선형 제약 조건은 $Ax + By + C \leq 0$ 꼴로 나타낼 수 있습니다(부등호의 종류는 달라질 수 있습니다). 이러한 제약 조건은 분명히 반평면일 뿐이므로, 선형 제약 조건 집합에 실현 가능한 해가 존재하는지는 반평면 교집합으로 확인할 수 있습니다. 또한 주어진 선형 제약 조건 집합에 대해 실행 가능한 해의 영역(즉, 반평면들의 교집합)을 계산한 뒤, 제약 조건 하에서 어떤 선형 함수 $f(x, y)$를 최대화/최소화하는 여러 쿼리에 이진 탐색을 사용하여 쿼리당 $O(\log N)$에 답할 수 있습니다(볼록 껍질 트릭과 매우 유사합니다).

선형 제약 조건 집합에 실행 가능한 해가 존재하는지 여부를 확인하고, 주어진 제약 조건 하에서 어떤 선형 함수를 최대화/최소화할 수 있는 꽤 간단한 무작위 알고리즘도 존재한다는 점을 언급할 가치가 있습니다. 이 무작위 알고리즘 역시 앞서 언급한 강의에서 Artem Vasilyev가 잘 설명하였습니다. 관심 있는 독자를 위해 이에 관한 추가 자료를 소개합니다: CG - 강의 4, 파트 4와 5 및 Petr Mitrichev의 블로그(아래 연습 문제 목록에서 가장 어려운 문제의 풀이를 포함합니다).

연습 문제

고전 문제, 직접 응용

더 어려운 문제

추가 문제

  • 40th Petrozavodsk Programming Camp, Winter 2021 - Day 1: Jagiellonian U Contest, Grand Prix of Krakow - Problem B: (Almost) Fair Cake-Cutting. 이 글을 작성할 당시 이 문제는 비공개였으며 Programming Camp 참가자만 접근할 수 있었습니다.

참고 문헌 및 기타 자료

주요 자료

좋은 블로그 (중국어)

무작위 알고리즘