얼마전 볼록껍질 문제를 해결하고 기하 문제에 관심이 생겨 백준 1077번 넓이 문제에 도전해봤다. 새로 배워야 할 개념이 많았는데 넓이를 구하는 기초적인 아이디어를 잘 구현해낸 것 같아 정리해보고자 한다. 1. 볼록다각형의 정의 이 문제를 연구하다가 새로 알게된 사실이다. 볼록다각형은 이웃하지 않는 두 점을 이은 선분이 도형 내부에 존재하는 단순다각형을 말한다. 단순다각형은 다각형을 이루는 변들이 서로 교차하지 않는 다각형을 말한다. 볼록 집합이라는 것도 있는데, 집합 내에서 어떤 두 점을 선택해도 선분이 집합 내부에 그려지게 되는 집합을 말한다. 볼록다각형은 볼록 집합을 이루는 단순다각형이기도 하다. 엄밀한 볼록다각형은 모든 내각의 크기가 180도 미만이어야 한다. 어떤 문제들은 이 조건을 명시하지만 ..

여러 객체가 주어졌을 때, 객체를 둘러싸는 껍질을 만드는 문제다. 적용되는 가장 직관적인 현상은 고무줄이다. 몇 개의 못을 박아두고 못을 전부 안쪽으로 감싸도록 고무줄을 걸어주면 고무줄이 만든 도형이 볼록껍질이 된다. 1. 문제상황 볼록껍질을 만드는 문제상황을 아래 그림을 예시로 생각해 보자. 평면상에 10개의 좌표가 주어져있고 이 점들을 감싸는 최소 면적의 볼록 다각형을 구성하는 점을 특정하는 것이 이 문제의 해가 된다. 해를 구할 수 있는 방법은 모든 점을 방문하며 확인해보는 방법도 있겠으나, 가장 널리 알려진 것은 O(NlogN)의 시간복잡도를 가진 그라함 스캔(Graham's scan)이다. 2. CCW(Counter Clock Wise) 알고리즘 그라함 스캔 알고리즘을 수행하기 위해서는 두 점으..