2차원 평면 위에 수많은 못이 무작위로 박혀 있다고 상상해 보십시오. 이 못들을 모두 감싸도록 거대한 고무줄을 팽팽하게 당겼다 놓았을 때, 고무줄이 걸치게 되는 가장 바깥쪽 못들의 집합(다각형)을 찾는 문제를 기하학에서는 '컨벡스 헐(Convex Hull, 볼록 껍질)'이라고 부릅니다. 자율주행 자동차의 장애물 충돌 판정, 영상 인식에서의 객체 테두리 추출 등 수많은 실생활 최적화 문제의 뼈대가 되는 이 문제를 해결하기 위해, O(N^3)의 무식한 브루트 포스 방식을 단숨에 O(N log N)으로 끌어내린 우아한 알고리즘이 있습니다. 바로 로널드 그라함(Ronald Graham)이 고안한 '그라함 스캔(Graham Scan)'입니다.
1. 기준점 찾기와 각도 정렬(Polar Angle Sort)
그라함 스캔의 첫 번째 단계는 고무줄이 무조건 걸칠 수밖에 없는 '절대적인 닻(Anchor)'을 찾는 것입니다. 평면의 점들 중 y좌표가 가장 작은 점(가장 아래에 있는 점)을 찾습니다. 만약 그런 점이 여러 개라면 x좌표가 가장 작은 점을 선택합니다. 이 점은 볼록 껍질의 무조건적인 꼭짓점이 됩니다.
1-1. 반시계 방향으로 줄 세우기
기준점을 찾았다면, 나머지 모든 점들을 기준점과의 '상대적인 각도(Polar Angle)'를 기준으로 오름차순 정렬합니다. 각도가 같다면 기준점으로부터의 거리가 가까운 순(또는 먼 순, 구현에 따라 다름)으로 정렬합니다. 이렇게 정렬해 두면, 기준점에서 시작해 반시계 방향으로 점들을 하나씩 훑으며 다각형의 외곽선을 그려나갈 수 있는 완벽한 순서가 만들어집니다.
2. 스택(Stack)을 이용한 외곽선 조각하기
이제 빈 스택(Stack)을 준비하고, 기준점과 정렬된 첫 번째 점을 스택에 집어넣습니다. 그리고 두 번째 점부터 마지막 점까지 순회하며 다음의 엄격한 '좌회전(Left Turn) 검사'를 수행합니다.
2-1. CCW를 통한 꺾임 판별
- 스택의 최상단에 있는 두 점(가장 최근에 추가된 두 점)과 지금 검사하려는 새로운 점, 총 3개의 점을 연결해 봅니다.
- 이 세 점이 이루는 방향이 '반시계 방향(좌회전)'인지 확인합니다. (이때 CCW 알고리즘이 사용됩니다.)
- 좌회전이라면: 정상적으로 볼록한 외곽선을 그리고 있는 것이므로, 새로운 점을 스택에 Push(추가)하고 다음 점으로 넘어갑니다.
- 우회전(Right Turn) 또는 일직선이라면: 안쪽으로 오목하게 파고들어 갔다는 뜻입니다. 볼록 껍질의 규칙을 위반했으므로, 스택의 맨 위(Top)에 있던 점을 Pop(제거)하여 버립니다. 좌회전이 나올 때까지 이 과정을 스택에서 반복하여 오목한 부분들을 깎아냅니다.
모든 점에 대해 이 과정을 단 한 번씩만 스캔(Scan)하고 나면, 스택에 살아남은 점들이 바로 고무줄이 걸친 완벽한 컨벡스 헐의 꼭짓점들이 됩니다.
1. 컨벡스 헐(Convex Hull)은 2차원 평면의 점들을 모두 포함하는 가장 작은 볼록 다각형을 찾는 기하학적 최적화 문제입니다.
2. 그라함 스캔(Graham Scan) 알고리즘은 가장 아래쪽 점을 기준으로 나머지 점들을 각도 순으로 정렬하는 데 O(N log N)의 시간을 씁니다.
3. 정렬된 점들을 순회하며 스택(Stack)과 CCW(좌회전 판별)를 이용해 오목하게 꺾이는 점들을 제거해 나가는 방식으로, 스캔 자체는 O(N) 만에 끝나는 매우 직관적이고 효율적인 기법입니다.