돌이 코딩하는 방

가장 먼 두 점의 거리를 구할때 사용되어지는 알고리즘인 로테이팅 캘리퍼스(회전하는 캘리퍼스)에 대해서 소개하려고 한다. 수학을 좋아하고 잘하는 사람들은 수학에서 이미 접해봤을 수도 있는 내용이다. 로테이팅 캘리퍼스란? rotating + callipers의 합성어로 rotating은 돌아가는, 회전하는이란 뜻이고, callipas는 길이를 재는 도구이다. 즉, 놓여있는 점들 중 가장 먼 두 점의 거리를 구할때 돌면서 구하겠다는 뜻이다. two pointer기반으로 이루어지며 몇가지 수학적 사실들을 기반으로 이루어지게 된다. 진행 방식 일단 점들중 가장 거리가 먼 두 점이 있다면 그 두 점은 모두 볼록 껍질 위에 있다라는 사실을 전제로 한다. 완벽히 증명은 되지 않아도 어느정도 직관적으로 이해할 수 있는 ..

문제 태그 : https://www.acmicpc.net/problem/10903 문제 소개 원의 갯수와, 원의 반지름과 각 원의 중심의 위치가 주어진다. (모든 원은 반지름이 같다.) 이때 모든 원을 포함하는 도형의 최소 둘레를 구하시오. 문제 풀이 이 문제를 보자마다 딱 이러한 형태의 그림이 떠올랐다. 그림을 보면 알겠지만, 바깥의 전체 둘레의 길이는 원하나의 둘레+ 점 들 사이의 거리의 합이다. 이 그림을 고려하며 문제를 다시 보면, 볼록껍질을 이루는 점들의 이웃한 거리의 합 + 원 하나의 둘레가 정답이 된다는 것을 알 수 있다. 볼록껍질을 잡는 것은 이 글을 통해서 배울 수 있다. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24..

'트리는 센트로이드, 그래프는 SCC를 잡고 보면 편해진다' 라는 말이 있듯이 '기하는 컨벡스 헐을 잡고 보면 편해진다' 라는 말이 있다. 그 만큼 컨벡스 헐은 기하 문제에서 굉장히 중요한 역할을 한다. 이번 글에서는 무작위 점들에서 컨벡스 헐을 잡는 대표적인 방법인 그라함 알고리즘을 소개하려고 한다. 컨벡스 헐(Convex Hull)이란? 한국어로는 볼록 껍질이고, 볼록 껍질이란 말이 이 단어의 의미를 정말 잘 설명해 준다고 생각한다. 말 그대로 '볼록' 한 '껍질'이다. 점들이 막 주어져 있을때 모든 점을 포함하는 볼록한 다각형을 의미한다. 그리고 보통 그 다각형의 꼭짓점을 모두 구하는 것을 '컨벡스 헐을 잡는다'라고 이야기 한다. 왼쪽 그림과 같이 점 들이 놓여져 있을때 오른쪽의 빨간 직선으로 이루..

이번 글에서는 어떤 점이 도형의 내부에 있는지 판별하는 알고리즘을 설명하려고 한다. 엄청 많이 쓰이는 것도, 엄청 까다로운 것도 아니지만 나름 중요하며, 어쩌면 쉬어가는 타임으로 받아들일 수도 있다. 도형에서의 점의 내부 판별 들어본 사람은 들어봤을만한 문제이다. 꼭 정보가 아니어도 한 번쯤은 책이나 어디에선가 점이 도형의 내부에 있는지 외부에 있는지에 대해서 설명한 것을 봤을만하다. 점에서 외부로 선을 그었을 때 도형과 짝수번 만나면 외부, 홀수번 만나면 내부이다. 위의 그림에서 확인하고 싶은 점에 대해서 먼 점을 찍으면 그 둘을 이은 선분이 도형을 한 번 지나칠때 마다 내부와 외부가 바뀐다는 사실을 알 수 있다. 따라서 전 글에 나와있는 선분 교차 알고리즘을 이용하면 쉽게 문제를 해결할 수 있다. 이..

문제 태그 : https://www.acmicpc.net/problem/2162 문제 소개 만나는 선분끼리 싹다 그룹을 만들어서 그룹의 갯수와 최대 그룹의 크기를 출력하는 문제 문제 풀이 선분 교차 알고리즘을 이용해 만나는 선분을 판별하고, union & find를 이용하여 그룹을 만들어 주는 문제. 출력처리는 조상의 번호별로 갯수를 세면 간단하게 할 수 있는 것 같다. 선분교차와 union&find를 모른다면 각각 이글과 이글을 참고하자. 코드 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52..

이번 글부터 지금까지 공부한 기하 알고리즘들에 대해서 정리를 하고 넘어가려고 한다. 솔직히 나는 기하를 잘 못한다. 많은 사람들이 기하를 어려워 하지만, 나의 꼼꼼한 코딩을 잘 못한다는 약점이 기하의 어려운 점을 더 부각시킨다. 또한, 기본적으로 기하 알고리즘을 많이 알고 있지도 않다. 그래서 아는 기하 알고리즘들을 한 번 정리하고 넘어가려고 한다. 기하 알고리즘? 기하 문제를 푸는 데 쓰이는 알고리즘 들이다. n차원으로 나아가기도 하지만, 보통 좌표평면 상에서 이루어지며, 점, 선 ,도형들 간의 관계, 상태를 표현하는 알고리즘들이 많다. 기본적으로 수학에서의 기하의 지식이 있으면 전체적으로 도움이 될 수 있다. 기하 구현 모든 기하 문제는 일단 기본적으로 점을 잡고 시작한다. 보통 pair형을 사용하여..