[Algorithm] 기하 알고리즘 해결을 위한 수학 공식 및 정리 모음 with Java

 

 

 

 

 

 

기하학 알고리즘 관련 정리 및 공식

 

 

들어가며

최근 대학수학을 복습하면서, 기하 알고리즘 문제를 풀 때 반복적으로 등장하는 개념과 공식을 정리할 필요성을 느꼈습니다.
이번 글에서는 기하 알고리즘 문제 해결에 자주 사용되는 핵심 개념들을, 기초적인 내용부터 대학수학 수준까지 정리해보려고 합니다.
증명은 생략하고, 수학적 설명과 자바(Java) 코드를 중심으로 설명할 예정입니다.
새롭게 공부하며 추가된 내용은 글 하단에 이어서 정리하고, 분량이 많거나 난이도가 높은 주제는 별도의 글로 분리해서 링크를 적어놓겠습니다.

 

 

---

 

 

피타고라스 정리(Pythagorean theorem)

1. 의미

직각삼각형에서 빗변과 나머지 두 변에 대한 관계를 나타낸 식입니다.

서로 직각을 이루는 두 변의 길이가 a, b이고 빗변의 길이가 c일 때 아래의 관계를 가집니다.

$$a^2+b^2=c^2$$

피타고라스 정리인 $a^2+b^2=c^2$를 역으로도 이용할 수 있습니다. 삼각형의 세 변의 길이가 주어졌을 때 피타고라스 정리를 만족하면 직각삼각형임을 알 수 있습니다.

또한, 피타고라스 정리는 두 점 사이의 거리를 구할 때도 많이 사용합니다. n차원에 놓인 두 점 사이의 거리를 구할 때 아래처럼 직각삼각형으로 만든 뒤 x 좌표의 변화량과 y 좌표의 변화량을 구하고 피타고라스 정리를 적용하면 두 점 사이의 거리를 구할 수 있습니다.

 

2. 자바 코드 예시

추가 예정

 

3. 백준 예제

• 4153번 직각삼각형: https://www.acmicpc.net/problem/4153
• 1711번 직각삼각형: https://www.acmicpc.net/problem/1711

 

 

헤론의 공식(Heron's formula)

1. 의미

삼각형의 세 변의 길이를 알 때 삼각형의 넓이를 구할 수 있는 공식입니다.

세 변의 길이가 각각 a, b, c일 때 둘레의 절반을 $\alpha=\Large\frac{a+b+c}{2}$라고 하면 삼각형의 넓이는 아래와 같습니다.

$$S=\sqrt{s(s-a)(s-b)(s-c)}$$

 

2. 자바 코드 예시

추가 예정

 

 

신발끈 공식(Shoelace formula)

1. 의미

좌표평면상 점의 좌표를 이용하여 다각형의 넓이를 계산하는 공식입니다. 다각형의 각 꼭짓점을 시계 반대 방향 순서로 $P_1,\ P_2,\ \cdots,\ P_n$라고 할 때, 아래와 같이 다각형의 넓이를 구할 수 있습니다.

$$S=\frac{1}{2}\begin{vmatrix}x_1 & x_2 & x_3 & \cdots & x_n & x_1 \\y_1 & y_2 & y_3 & \cdots & y_n & y_1\end{vmatrix}$$

$$=\frac{1}{2} \small((x_1y_2 + x_2y_3 + \cdots + x_{n-1}y_n + x_ny_1) - (x_2y_1 + x_3y_2 + \cdots + x_{n}y_{n-1} + x_1y_n) )$$

위의 계산식에 규칙이 존재합니다. 빨간색 화살표끼리 곱한 것을 모두 더하고 파란색 화살표끼리 곱한 것을 모두 뺀 뒤 절반이 삼각형의 넓이입니다. 위의 식을 계산하는 게 마치 신발끈을 묶는 모양과 같아서 신발끈 공식으로 불립니다.

 

2. 자바 코드 예시

추가 예정

 

3. 백준 예제

• 2166번 다각형의 면적: https://www.acmicpc.net/problem/2166

 

 

픽의 정리(Pick's theorem)

1. 의미

격자점 위의 단순 다각형에서 내/외부 격자 수와 그 다각형의 넓이 사이의 관계를 설명하는 정리입니다.

격자점 위의 다각형의 넓이를 A, 다각형의 내부에 있는 격자 점의 수를 i, 변 위에 있는 점의 수를 b라고 하면 아래의 식이 성립합니다.

$$A=i+\frac{b}{2}-1$$

간단하게 밑변의 길이가 7이고, 높이가 5인 삼각형을 예시로 들겠습니다.

먼저 삼각형 내부의 점의 개수 i는 12입니다. 그리고 변 위에 있는 점의 개수 b는 13개입니다. 픽의 정리를 이용하면 $12+\frac{13}{2}-1=\frac{35}{2}$이므로 실제 삼각형의 넓이와 동일한 것을 알 수 있습니다.

 

2. 자바 코드 예시

추가 예정

 

3. 백준 예제

• 7694번 Triangle: https://www.acmicpc.net/problem/7694
• 16057번 Water Testing: https://www.acmicpc.net/problem/16057

 

 

다면체의 오일러 공식

1. 의미

볼록다면체에서 꼭짓점(V)의 수, 변(E)의 수, 면(F)의 수 사이의 관계를 설명하는 공식입니다.

3가지 기하량의 관계는 아래와 같습니다.

$$V-E+F=2$$

정육면체로 예를 들면 정육면체는 꼭짓점의 수가 $V=8$이고, 변의 수가 $E=12$이고, 면의 수가 $F=6$이므로 $8-12+6=2$으로 성립하는 것을 알 수 있습니다.

 

2. 자바 코드 예시

추가 예정

 

3. 백준 예제

• 10569번 다면체: https://www.acmicpc.net/problem/10569

 

 

CCW

[Algorithm] CCW 알고리즘 with JAVA

 

 

삼각형의 내심 좌표

1. 개요

삼각형의 세 꼭짓점의 좌표와 세 변의 길이를 이용해서 내심 좌표를 구하는 공식입니다.

삼각형의 꼭짓점의 좌표가 $A(x_1,y_1)$, $B(x_2,y_2)$, $C(x_3,y_3)$로 주어지고, 각 꼭짓점들이 마주보고 있는 변의 길이를 $a, b, c$라고 한다면 내심의 좌표는 다음과 같습니다.

$$I=(\frac{ax_1+bx_2+cx_3}{a+b+c}, \frac{ay_1+by_2+cy_3}{a+b+c})$$

 

2. 자바 코드 예시

추가 예정

 

 

삼각형의 외심 좌표

1. 개요

삼각형의 외심 좌표는 세 꼭짓점에 이르는 거리가 모두 같다는 점을 이용해서 구할 수도 있지만 아래처럼 행렬을 이용해 구할 수 있습니다.

삼각형의 꼭짓점의 좌표가 $A(x_1,y_1)$, $B(x_2,y_2)$, $C(x_3,y_3)$로 주어지면 외심의 좌표는 다음과 같습니다.

$D=2\begin{vmatrix} x_1&y_1&1\\x_2&y_2&1\\ x_3&y_3&1 \end{vmatrix}$라고 할 때

$$O=(\frac{\begin{vmatrix} x_1^2+y_1^2&y_1&1\\ x_2^2+y_2^2&y_2&1\\ x_3^2+y_3^2&y_3&1 \end{vmatrix}}{D}, \frac{\begin{vmatrix} x_1&x_1^2+y_1^2&1\\x_2&x_2^2+y_2^2&1\\x_3&x_3^2+y_3^2&1 \end{vmatrix}}{D})$$

 

2. 자바 코드 예시

추가 예정

 

 

오일러의 삼각형 정리(Euler's trianlge theorem): 삼각형의 내심과 외심 사이의 거리

1. 개요

삼각형의 외접원의 반지름 길이와 내접원의 반지름 길이가 주어질 때 외심과 내심 사이의 거리는 유일하게 결정됩니다.

외접원의 반지름 길이를 R, 내접원의 반지름 길이를 r이라고 하면 내심과 외심 사이의 거리는 아래와 같습니다.

$$IO=\sqrt{R(R-2r)}$$

 

2. 자바 코드 예시

추가 예정

 

3. 백준 예제

• 16480번 외심과 내심은 사랑입니다: https://www.acmicpc.net/problem/16480

 

 

세 벡터로 만들어지는 평행육면체의 부피

1. 개요

네 개의 점 $O, A, B, C$가 주어지고 네 개의 점으로 만들어지는 세 개의 벡터 $\vec{OA}$, $\vec{OB}$, $\vec{OC}$를 이용해 만들어지는 평행육면체의 부피를 쉽게 구할 수 있습니다.

$$V=(\vec{OA}\times\vec{OB})\cdot\vec{OC}$$

또한, 세 개의 벡터로 만들어진 사면체의 부피는 평행육면체 부피의 $\frac{1}{6}$과 같습니다.

 

2. 자바 코드 예시

추가 예정

 

 

.

.

.

 

마치며

최근 대학수학 공부하느라 블로그와 PS 전부 못했습니다. 이제 다시 열심히 달려보겠습니다!

피드백과 질문은 언제든지 환영합니다. 😊