볼록 껍질 (Convex Hull)

평면에 흩뿌려진 점들을 고무줄로 통째로 감싸서 놓으면 나오는 모양. 그 고무줄이 닿는 바깥쪽 점들을 순서대로 이은 것이 볼록 껍질이다. 모든 점을 포함하는 가장 작은 볼록 다각형이며, 내부 각이 전부 180°보다 작다.

1. 직접 그려 보기 — Andrew 모노톤 체인

캔버스를 클릭해 점을 추가하거나 「무작위」를 누른다. 「한 단계」를 누르면 알고리즘이 점을 하나씩 검사한다. 마지막에 추가된 두 점이 우회전(시계 방향)을 만들면, 가운데 점은 껍질이 될 수 없으므로 스택에서 빼낸다(pop). 왼쪽→오른쪽으로 아래쪽 껍질을 만든 뒤, 오른쪽→왼쪽으로 위쪽 껍질을 만들어 합친다.

2. 핵심 도구 — 외적으로 방향 판정 (CCW test)

세 점 O → A → B가 왼쪽으로 꺾이는지(반시계, CCW) 오른쪽으로 꺾이는지(시계, CW)를 알아야 한다. 벡터 OA와 OB의 2D 외적(cross product) 부호가 답이다.

• cross > 0 → 좌회전 (CCW) · 세 점이 반시계 방향
• cross < 0 → 우회전 (CW) · 가운데 점 A는 껍질에서 제거
• cross = 0 → 일직선 (공선) · 보통 가운데 점 제거

3. 알고리즘 흐름 (Andrew's Monotone Chain)

1. 정렬 — 모든 점을 x 좌표 기준(같으면 y)으로 정렬한다. O(n log n), 여기가 전체 비용의 대부분.
2. 아래쪽 껍질 — 왼쪽 점부터 순서대로 스택에 넣는다. 새 점을 넣기 전, 스택 맨 위 두 점과 새 점이 우회전(≤0)이면 맨 위 점을 pop. 더 이상 우회전이 아닐 때까지 반복 후 push.
3. 위쪽 껍질 — 오른쪽 점부터 거꾸로 같은 과정을 반복한다.
4. 합치기 — 두 체인을 이어 붙이면(각 체인의 마지막 점은 중복이라 제외) 반시계 방향 볼록 다각형 완성.

정렬이 끝난 뒤의 스택 처리는 각 점이 많아야 한 번 push, 한 번 pop 되므로 O(n). 총 시간 복잡도는 정렬에 지배되어 O(n log n), 추가 메모리는 O(n).

4. 코드 (Python)

def cross(o, a, b):
    # >0: 좌회전(CCW), <0: 우회전(CW), 0: 일직선
    return (a[0]-o[0])*(b[1]-o[1]) - (a[1]-o[1])*(b[0]-o[0])

def convex_hull(points):
    pts = sorted(set(points))          # x, 그다음 y 로 정렬 + 중복 제거
    if len(pts) <= 2:
        return pts

    lower = []
    for p in pts:
        while len(lower) >= 2 and cross(lower[-2], lower[-1], p) <= 0:
            lower.pop()
        lower.append(p)

    upper = []
    for p in reversed(pts):
        while len(upper) >= 2 and cross(upper[-2], upper[-1], p) <= 0:
            upper.pop()
        upper.append(p)

    return lower[:-1] + upper[:-1]   # 각 체인 끝점은 중복 → 제외

5. 다른 볼록 껍질 알고리즘

6. 실제 활용