Algorithm/G. Geometry (8) 썸네일형 리스트형 104. Voronoi Diagram & Delaunay Triangulation 보로노이 다이어그램(Voronoi Diagram)은 $2$차원 좌표평면에 점들이 존재할 때 평면을 그 위치에서 가장 가까운 점에 따라 분할한 것을 의미한다. 다음 그림은 점 $20$개가 있는 보로노이 다이어그램의 예시이다. 보로노이 다이어그램은 거리가 가까운 점들의 수직이등분선을 적절하게 이으면 그릴 수 있다. 들로네 삼각분할(Delaunay Triangulation)은 $2$차원 좌표평면에 점들이 존재할 때 점들을 이어서 여러 개의 삼각형을 만드는데 삼각형의 외접원이 삼각형의 세 꼭짓점 외의 다른 점을 포함하는 경우가 생기지 않게 하는 분할 방법이다. 다음 그림은 점 $10$개가 있는 들로네 삼각분할의 예시이다. 보로노이 다이어그램과 들로네 삼각분할은 쌍대 관계(Duality)에 있으며 둘 중 하나를 .. 100. Rotating Calipers 볼록 껍질을 이용해서 $2$차원 좌표에서 가장 먼 두 점을 찾는 방법을 알아보자. 점이 $n$개인 경우 $\frac{n(n-1)}{2}$개의 쌍을 전부 다 확인하는 방법이 있지만, 점의 개수가 $10$만 개 정도를 넘어가면 속도가 너무 느리다. 이럴 때 사용할 수 있는 방법으로 회전하는 캘리퍼스(Rotating Calipers)라는 알고리즘이 잘 알려져 있다. 캘리퍼스는 길이를 잴 때 사용하는 컴퍼스와 비슷하게 생긴 도구이고, 회전하는 캘리퍼스라고 하면 이런 도구를 회전시키면서 길이를 잰다는 의미로 해석할 수 있다. 실제 알고리즘의 동작 과정도 이와 비슷하며 다음과 같다. 1. 점들의 볼록 껍질을 찾고, 여기에 속하는 점들을 꼭짓점으로 하는 볼록 다각형이 있다고 가정한다. 볼록 껍질에 $k$개의 점이 속.. 99. Andrew's Algorithm 앤드류 알고리즘(Andrew's Algorithm)은 점 $n$개의 볼록 껍질을 $\Theta(n\text{ lg }n)$ 시간에 찾는 또다른 알고리즘으로, 앞에서 소개한 그레이엄의 스캔보다 구현이 간단한 편이다. 모노톤 체인(Monotone Chain)이라는 이름으로도 알려져 있다. 이 알고리즘은 점들을 정렬하는 기준을 각도 대신 좌표로 하며, 위쪽 껍질과 아래쪽 껍질을 따로 구하게 된다. 구체적인 작동 방법은 다음과 같다. 1. 점들을 $x$좌표가 증가하는 순서대로, $x$좌표가 같다면 $y$좌표가 증가하는 순서대로 정렬한다. 2. 점을 앞쪽부터 차례로 확인하면서 그레이엄의 스캔과 같은 방식으로 볼록 껍질을 찾는다. 마지막 점까지 확인하면 볼록 껍질의 윗부분이 완성된다. 3. 점을 뒤쪽부터 차례로 확.. 98. Graham Scan 그레이엄의 스캔(그라함 스캔, Graham Scan)은 점 $n$개의 좌표가 주어졌을 때 $\Theta(n\text{ lg }n)$ 시간에 볼록 껍질을 찾는 알고리즘이다. 이 알고리즘은 기준점을 잡고 남은 점들을 각도 순으로 정렬한 다음 차례로 확인하는 방식으로 작동한다. 이전 글에 나온 점들의 볼록 껍질을 그레이엄의 스캔으로 구하는 과정은 다음과 같다. 이 블로그에서는 $x$좌표가 가장 작은 점, 그러한 점이 여러 개일 경우 그중 $y$좌표가 가장 작은 점을 기준점으로 했다. $x$좌표가 가장 작은 점 $1$을 기준점으로 잡고 나머지 점들을 각도 순으로 정렬한다. 그러면 점 $6$ - 점 $8$ - 점 $4$ - 점 $2$ - 점 $7$ - 점 $5$ - 점 $9$ - 점 $3$ 순서가 된다. 이제 이.. 97. Convex Hull $2$차원 좌표평면에 $3$개 이상의 점이 존재하고 모든 점이 한 직선 위에 있지 않을 때, 이중 몇 개의 점을 선택한 뒤 이으면 볼록다각형이 되면서 나머지 모든 점이 다각형 내부에 존재하도록 할 수 있는데, 이 볼록다각형을 볼록 껍질(Convex Hull)이라고 한다. 다음 예시를 보자. 점들의 위치가 위와 같을 때 다음과 같은 볼록 껍질을 찾을 수 있다. 점들의 좌표가 주어졌을 때 볼록 껍질을 찾아내는 것 역시 기하 문제에서 종종 접할 수 있는데, 모든 선분 쌍을 하나씩 확인하는 등의 방법은 점의 개수가 많다면 비효율적이다. 다음 두 글에서 볼록 껍질을 빠르게 찾아내는 알고리즘에 대해 살펴볼 것이다. → solved.ac tag: convex_hull 96. Line Intersection 기하 문제 중에는 두 선분이 서로 교차하는지를 알아내야 하는 것들이 꽤 있다. 선분의 교차 여부를 프로그램으로 구현하려고 하면 그리 만만하지 않은데, 앞에서 설명한 CCW 함수를 이용하면 비교적 간단하게 선분 교차 여부를 확인할 수 있다. $2$차원 좌표평면에 네 점 $\text{A}(x_1, y_1), \text{B}(x_2, y_2), \text{C}(x_3, y_3), \text{D}(x_4, y_4)$가 존재하고 선분 $\overline{\text{AB}}$와 선분 $\overline{\text{CD}}$의 교차 여부를 판별해야 하는 경우를 생각해 보자. 점들의 위치가 다음과 같을 때, 선분 $\overline{\text{AB}}$와 선분 $\overline{\text{CD}}$는 교차한다. 만약.. 95. Counterclockwise Function 기하 문제를 풀 때 필요한 가장 기본적인 개념 중 하나가 CCW 함수(Counterclockwise Function)이다. 이 함수는 $x$축, $y$축이 존재하는 $2$차원 평면상의 세 점 $\text{A}(x_1, y_1), \text{B}(x_2, y_2), \text{C}(x_3, y_3)$가 주어졌을 때 점 $\text{C}$가 벡터 $\overset{\longrightarrow}{\text{AB}}$를 기준으로 왼쪽(반시계 방향, CCW)/오른쪽(시계 방향, CW) 중 어느 쪽에 있는지를 판별하는 함수이다. 확인 대상이 점인 경우 판별이 막연할 수 있으나 확인 대상을 점 $\text{C}$ 대신 벡터 $\overset{\longrightarrow}{\text{AC}}$로 해도 결과가 같기 때문.. 94. Geometry Intro 카테고리 G에서는 기하에 관한 내용을 다룬다. 앞에서 선형대수학에 대한 글을 작성하면서 벡터에 대한 설명을 미뤄두었는데, 이제 벡터를 설명할 때가 되었다. 벡터의 넓은 의미는 선형대수적 관점에서 이해할 수 있는데, 이에 따르면 벡터(Vector)는 벡터 공간(Vector Space)의 원소이며, 벡터 공간은 벡터에서 성립하는 연산 법칙이 정의된 공간이다. 이때의 연산 법칙은 벡터의 덧셈 및 스칼라곱이 정의되어 있으며 덧셈에 대한 항등원(이 항등원을 영벡터(Zero Vector)라고 한다) 및 역원이 존재한다는 것과 덧셈의 결합법칙 및 교환법칙이 성립한다는 것을 의미한다. 표기는 일반적으로 볼드체를 사용한다. 실제로는 변칙적인(?) 표기가 매우 많이 존재하지만, 여기서는 수학적 벡터를 볼드체로 표기하였다... 이전 1 다음
