볼록 껍질 ② — Graham Scan과 정렬 하한

1편의 Package Wrapping은 껍질 점 하나를 확정할 때마다 남은 점 전체를 다시 훑는다. 걸음마다 하는 일은 사실 “각도상 가장 바깥 점 찾기”로 매번 비슷하다. 그렇다면 처음에 각도 정렬을 한 번만 해 두면 어떨까? 이 아이디어가 Graham Scan이고, 결과는 $O(N \log N)$이다. 그리고 그것이 사실상 한계라는 것까지 이번 편에서 확인한다.

---

되짚어보기 — Package Wrapping의 한계

1편에서 세 점의 회전 방향을 정수 연산만으로 판정하는 CCW를 만들었고, 이를 이용해 포장지로 감싸듯 껍질을 한 변씩 찾는 Package Wrapping을 봤다. 최하단 점에서 시작해, 매 걸음 나머지 점을 전부 훑어 가장 바깥 점을 다음 껍질 점으로 확정하는 방식이었다. 걸음 하나가 $O(N)$, 걸음 수가 껍질 점 개수 $H$라서 전체 $O(NH)$였고, 최악의 경우 모든 점이 껍질 위에 있으면 $O(N^2)$이다. 1편에서 세운 네 가지 가정(점이 3개 이상이고, 모든 x좌표가 다르고, 모든 y좌표가 다르고, 한 직선 위에 점이 3개 이상 없다)은 이번 편에서도 그대로 유지한다.

이 방법의 낭비는 분명하다. 걸음마다 남은 점 전체를 다시 훑는데, 매번 하는 계산이 거의 같다. 각 걸음이 묻는 것은 결국 “현재 점 기준으로 어느 점이 가장 바깥(각도상 가장 앞)인가”이다. 이런 질문을 $H$번 반복할 거라면, 차라리 처음에 모든 점을 각도순으로 정렬해 두는 편이 낫지 않을까?

---

아이디어 — 각도 정렬을 한 번만

시작은 1편과 같다. y좌표가 가장 작은 점 $Y$ 를 잡는다. 모든 점이 $Y$보다 위에 있으므로 $Y$는 반드시 껍질 위의 점이다.

이제 나머지 $N-1$개의 점을 $Y$에서 바라본 각도 오름차순으로 정렬한다. $Y$에서 오른쪽 수평 방향을 각도 0으로 두고, 반시계 방향으로 훑으며 만나는 순서대로 번호를 매기는 셈이다.

각도를 직접 계산하지는 않는다. 1편에서 본 대로 $\arctan$은 부동소수점 오차를 부르기 때문이다. 두 점 $A$, $B$ 중 누가 각도상 앞인지는 $\text{ccw}(Y, A, B)$의 부호로 판정할 수 있다. 값이 양수면 $Y \to A \to B$가 좌회전, 즉 $A$가 $B$보다 각도가 작다(먼저 만난다). 이 비교 함수로 표준 정렬을 돌리면 끝이다.

// Y: 최하단 점, ccw(): 1편에서 정의
sort(pts.begin() + 1, pts.end(),
     [&](P a, P b) { return ccw(Y, a, b) > 0; });

정렬이 끝나면 좋은 성질이 하나 생긴다. 정렬된 순서 그대로 점을 방문하면, $Y$ 주위를 반시계로 정확히 한 바퀴 도는 순회가 된다. 껍질의 꼭짓점들도 이 순서 안에 (그 순서 그대로) 들어 있다. 남은 문제는 하나다. 이 순회에서 어떤 점이 껍질에 남고, 어떤 점이 안쪽에 묻히는지를 가려내야 한다.

---

Graham Scan — 스택으로 좌회전만 남기기

가려내는 기준은 이미 가지고 있다. 볼록 다각형을 반시계로 돌면 모든 꺾임이 좌회전이다. 거꾸로 말해, 순회 도중 우회전이 나타났다면 그 꺾임점은 안쪽으로 파인 것이므로 껍질의 꼭짓점일 수 없다.

그래서 스택을 쓴다. 정렬된 순서대로 점을 하나씩 보면서:

1. 처음 두 점($Y$와 각도가 가장 작은 점)을 스택에 넣는다.
2. 새 점이 올 때마다, 스택 위의 두 점과 새 점이 이루는 회전을 본다. 좌회전이면 새 점을 push한다.
3. 우회전이면 스택 맨 위의 점을 pop한다. 좌회전이 될 때까지 반복해서 뺀 뒤, 새 점을 push한다.

우회전이 나오는 순간이 이 알고리즘의 핵심 장면이다. 점 5까지는 순조롭게 쌓이지만 점 6이 도착하면 $4 \to 5 \to 6$이 우회전이다. 이는 점 5가 선분 $4$–$6$보다 안쪽에 있다는 뜻이다. 5는 껍질의 꼭짓점이 될 수 없으므로 pop하고, 다시 스택 위 두 점($3$, $4$)과 $6$의 회전을 본다. 이번엔 좌회전이므로 pop을 멈추고 6을 push한다.

위 도식은 이 과정을 단계로 나눠 놓았다. 마지막 단계까지 가면 스택에 남은 점이 그대로 반시계 방향 볼록 껍질을 이루고, pop된 5만 안쪽에 남는다.

1편의 네 가정 가운데 점이 3개 이상이라는 조건이 여기서 코드의 전제로 들어온다. 아래 코드는 기준점을 고르고 두 점을 미리 담아 두는 구조라 $N \ge 3$에서만 뜻이 있다. 점이 없으면 min_element가 가리킬 곳이 없고, 두 점 이하면 감쌀 다각형 자체가 없다. 작은 입력을 받아야 하는 구현이라면 스캔에 들어가기 전에 그대로 돌려주는 분기를 따로 두면 된다.

전체 코드는 정렬과 스캔 두 단계다.

// pts: 점 목록, ccw(), struct P: 1편에서 정의
vector<P> grahamScan(vector<P> pts) {
    // 1) 기준점: y가 가장 작은 점을 맨 앞으로
    swap(pts[0], *min_element(pts.begin(), pts.end(),
        [](P a, P b) { return a.y < b.y; }));
    P Y = pts[0];

    // 2) 기준점 각도순 정렬: 각도 대신 CCW로 비교
    sort(pts.begin() + 1, pts.end(),
         [&](P a, P b) { return ccw(Y, a, b) > 0; });

    // 3) 스캔: 우회전이면 좌회전이 될 때까지 pop
    vector<P> hull;                       // 스택으로 사용
    for (P p : pts) {
        while (hull.size() >= 2 &&
               ccw(hull[hull.size()-2], hull.back(), p) < 0)
            hull.pop_back();
        hull.push_back(p);
    }
    return hull;                          // 반시계 순서의 껍질
}

복잡도. 스캔 단계부터 보자. while 루프 때문에 한 점을 처리하는 데 오래 걸릴 것 같지만, 전체를 놓고 보면 각 점은 스택에 최대 한 번 들어가고 최대 한 번 나온다. push 총 $N$번, pop 총 $N$번 이하이므로 스캔 전체가 $O(N)$이다. 남는 것은 정렬뿐이므로,

$$\underbrace{O(N \log N)}_{\text{정렬}} + \underbrace{O(N)}_{\text{스캔}} = O(N \log N)$$

이다. Package Wrapping과 달리 껍질 점 개수 $H$와 무관하게 항상 $O(N \log N)$이 보장된다.

---

더 빠를 수는 없을까 — 정렬 하한

$O(N \log N)$에서 멈춰야 할까? “더 빠른 알고리즘이 아직 발견되지 않았다”와 “더 빠른 알고리즘은 존재할 수 없다”는 전혀 다른 이야기다. 후자를 보이는 것이 하한(lower bound) 증명이고, 이것이 있어야 안심하고 탐색을 멈출 수 있다.

증명 도구는 가장 가까운 점 쌍에서도 썼던 환원(reduction) 이다.

“정렬 문제가 숨어 있다”는 말이 무슨 뜻인지, 네 단계로 확인하자.

1단계: 숫자를 원 위의 점으로 바꾼다

서로 다른 양수 $v_1, \cdots, v_N$을 정렬하고 싶다고 하자. 값이 겹치면 아래 변환이 두 숫자를 같은 점으로 보내 버리므로 서로 다른 경우로 한정하는데, 비교 정렬의 하한은 서로 다른 키에 대해서도 성립하므로 논증의 힘은 그대로다.

먼저 최댓값 $M$을 찾는다. 전체를 한 번 훑으면 되니 $O(N)$이다. 그리고 각 숫자를 크기에 비례하는 각도로 바꾼다.

$$\theta_i = \frac{v_i}{M+1} \cdot 2\pi$$

$M$이 아니라 $M+1$로 나누는 이유는 사소하지만 중요하다. $M$으로 나누면 최댓값의 각도가 정확히 $2\pi$가 되는데, $2\pi$는 $0$과 같은 방향이라 가장 큰 숫자가 각도 $0$ 자리로 돌아와 버린다. $M+1$로 나누면 모든 각도가 $(0, 2\pi)$ 안에 안전하게 들어가고, 숫자가 다르면 각도도 다르다.

이제 각 각도를 반지름 $r$인 원 위의 점으로 바꾼다.

$$v_i \;\mapsto\; \left(r\cos\theta_i,\; r\sin\theta_i\right)$$

예를 들어 $3, 1, 4, 2$를 정렬한다면 $M+1 = 5$이므로, 네 숫자는 각도 $216^\circ, 72^\circ, 288^\circ, 144^\circ$ 위치의 점 4개가 된다. 작은 숫자일수록 각도 $0$에 가깝고, 큰 숫자일수록 한 바퀴에 가깝다.

2단계: 이 점들은 전부 껍질의 꼭짓점이다

원 위의 점은 하나도 빠짐없이 볼록 껍질의 꼭짓점이 된다. 아무 점 $P$나 잡고, $P$가 원에 닿는 자리에서 원의 접선을 그어 보자. 원 전체가 접선의 한쪽에 있으므로, 원 위에 있는 나머지 점들도 전부 그 한쪽에 있다. 나머지 모든 점이 한 직선의 같은 쪽에 몰려 있다면 $P$는 그 점들이 만드는 어떤 다각형에도 안쪽으로 들어갈 수 없다. 즉 $P$는 껍질의 꼭짓점이다.

버려지는 점이 없으므로, 껍질의 꼭짓점 목록은 입력한 $N$개의 점 전부다.

3단계: 껍질을 읽으면 정렬이 끝난다

이 논증은 볼록 껍질 문제의 출력 계약에 기댄다. 여기서 볼록 껍질을 구한다는 것은 꼭짓점을 모아 놓기만 하는 일이 아니라 다각형의 둘레를 도는 순서로 내놓는 일이다. Graham Scan이 실제로 그렇게 내놓는다.

순서 없는 집합으로 돌려주는 정의를 쓴다면 이 환원은 그대로 옮겨지지 않는다. 집합을 받아 둘레 순서를 알아내는 데 다시 정렬만큼의 시간이 들 수 있어서다. 그때는 대수적 결정 트리 모형에서 따로 하한을 세워야 한다. 그런데 원 위에서 둘레를 도는 순서는 곧 각도가 커지는 순서이고, 각도는 1단계에서 원래 숫자에 비례하도록 만들었다. 정리하면,

$$\text{껍질의 꼭짓점 순서} \;=\; \text{각도 순서} \;=\; \text{원래 숫자의 크기 순서}$$

이다. 껍질 출력에서 각도가 가장 작은 점을 찾아 거기서부터 순서대로 읽으면 정렬이 끝난다. 둘레를 도는 방향은 알고리즘마다 다를 수 있다. 읽어 낸 목록이 오르는지 내리는지는 이웃한 두 점을 한 번 비교하면 알 수 있고, 내리면 뒤집는다. 이 후처리 전부가 $O(N)$이다.

4단계: 그래서 하한이다

지금까지 만든 것을 조립하면 하나의 정렬기가 된다.

1. 숫자를 원 위의 점으로 변환한다. $O(N)$
2. 볼록 껍질 알고리즘을 돌린다. $T(N)$
3. 껍질 출력에서 정렬 결과를 읽는다. $O(N)$

전체 비용은 $T(N) + O(N)$이다. 그런데 정렬은 $\Omega(N \log N)$보다 빠를 수 없다는 것이 이미 증명되어 있다. 만약 볼록 껍질이 그보다 빠르게, 예컨대 $O(N)$에 풀린다면 위 정렬기는 정렬을 $O(N)$에 풀어 버리고, 이는 정렬의 하한과 모순이다. 따라서,

$$T(N) + O(N) = \Omega(N \log N) \quad\Longrightarrow\quad T(N) = \Omega(N \log N)$$

이다. 볼록 껍질은 정렬만큼 어렵다. Graham Scan의 $O(N \log N)$은 우연히 도달한 값이 아니라, 이 문제가 허용하는 최선이다.

---