컴퓨터에서 기하학(Geometry) 문제를 풀 때 가장 피해야 할 것은 무엇일까요? 바로 $\sin$, $\cos$ 같은 삼각함수나 나눗셈을 무분별하게 사용하는 것입니다. 부동소수점(Floating Point)의 미세한 오차가 누적되는 순간, 교차해야 할 선분이 교차하지 않는다고 판정되는 끔찍한 오답의 늪에 빠지게 됩니다. 오차 없이 오직 정수들의 덧셈, 뺄셈, 곱셈만으로 2차원 공간상에 놓인 세 점의 방향 관계를 완벽하게 판독해 내는 기하학의 마스터키가 있습니다. 바로 외적(Cross Product)의 원리를 차용한 CCW(Counter Clock Wise, 반시계 방향) 알고리즘입니다.
1. CCW의 수학적 본질: 2차원 벡터의 외적
점 $A(x_1, y_1)$, $B(x_2, y_2)$, $C(x_3, y_3)$가 순서대로 주어졌을 때, 선분 AB에서 선분 BC로 꺾이는 방향이 어느 쪽인지 알고 싶다면 벡터 $\vec{AB}$와 벡터 $\vec{BC}$의 외적(Cross Product)을 구하면 됩니다. 3차원 공간에서 z좌표를 0으로 둔 외적 공식을 전개해 보면, 놀랍도록 단순한 하나의 수식이 탄생합니다.
$$CCW = (x_2 - x_1)(y_3 - y_1) - (x_3 - x_1)(y_2 - y_1)$$
1-1. 마법의 판별식 (결과값의 부호)
이 식을 계산하여 나온 결과값의 부호(Sign)만 보면 세 점의 방향 관계를 100% 확신할 수 있습니다.
- 양수 (+) : 점 C가 선분 AB의 왼쪽에 있습니다. 즉, A → B → C로 갈 때 반시계 방향(좌회전)으로 꺾입니다.
- 음수 (-) : 점 C가 선분 AB의 오른쪽에 있습니다. 즉, A → B → C로 갈 때 시계 방향(우회전)으로 꺾입니다.
- 0 : 점 A, B, C가 완전히 일직선상(Collinear)에 놓여 있습니다.
2. CCW의 무궁무진한 실전 응용
이 단순한 수식 하나가 코딩 테스트의 악랄한 기하 문제들을 전부 박살 내는 핵심 무기가 됩니다.
2-1. 선분 교차 판정 (Line Intersection)
두 선분 AB와 CD가 서로 교차하는지(X자로 겹치는지) 어떻게 알 수 있을까요? 선분의 방정식을 세워서 연립방정식을 푸는 것은 부동소수점 오차 때문에 자살 행위입니다. 대신 CCW를 4번 쓰면 됩니다.
1. 선분 AB를 기준으로 점 C와 점 D가 서로 반대 방향에 있어야 합니다. CCW(A, B, C) * CCW(A, B, D) < 0
2. 동시에 선분 CD를 기준으로 점 A와 점 B도 서로 반대 방향에 있어야 합니다. CCW(C, D, A) * CCW(C, D, B) < 0
이 두 조건이 모두 성립하면 두 선분은 완벽하게 교차합니다. (단, 일직선상에서 겹치는 예외 케이스는 좌표의 대소 비교로 따로 걸러주어야 합니다.)
2-2. 다각형의 넓이 구하기 (신발끈 공식)
다각형의 꼭짓점들이 반시계 방향으로 순서대로 주어졌을 때, 원점과 다각형의 각 선분을 이루는 세 점에 대해 CCW 값을 모두 구해서 더한 뒤 2로 나누면? 놀랍게도 그 볼록/오목 다각형의 정확한 넓이(Area)가 튀어나옵니다. 이것이 바로 그 유명한 '신발끈 공식(Shoelace Formula)'의 기하학적 원리입니다.
1. CCW(Counter Clock Wise)는 실수 연산을 철저히 배제하고 정수들의 곱셈과 뺄셈만으로 세 점의 방향성(좌회전, 우회전, 일직선)을 오차 없이 판별하는 식입니다.
2. 수식의 결괏값이 양수이면 반시계 방향, 음수이면 시계 방향, 0이면 일직선상에 존재함을 의미합니다.
3. 이 단순한 부호 판별 로직을 조합하여 선분 교차 판정, 컨벡스 헐 검증, 다각형 내부의 점 판별, 다각형 넓이 계산 등 거의 모든 기하 알고리즘의 베이스캠프로 활용됩니다.