IT 방랑기

1. Convex hull Convex Hull이란, 점들로 구성된 Set을 모두 포함하는 외각 점들의 집합이다. 아래의 그림을 보자. 출처 : 위키피디아 검은 점들로 구성된 집합 `S`에서 어느 점을 선택하더라도, 파란색 선안에 포함되는 것을 알 수 있다. 이 파란색 선을 어떻게 찾아야 할까? 2. How to find convex hull Convex Hull을 찾는 가장 간단한 방법은 각 점마다 모든 점들을 순회해서 가장 외각의 것을 선택하는 것이다. 하지만 이렇게 접근한다면, 결국 `O(n^2)`이 되어서 원하는 작업을 원할히 할 수 없다. 사실 모든 점을 순회한다는 것은 가장 외각의 점을 찾기 위함이다. 따라서 이 부분을 더욱 쉽게 만들어 준어야 한다. 그런 방법들 중에서도, 외적을 이용한 `C..

1. Convex Set Convex Set이란, 집합 `S`에 포함된 어느 두 점 `p`, `q`를 선택하여 점들을 연결하는 직선을 모두 포함하는 덩어리를 의미한다. 즉, 특정 점들의 집합이 아닌, 이를 감싸고 있는 공간이라고 생각하면 된다. 아래의 그림 3개를 보자 . 그림 1, 출처 : 위키피디아 그림 2, 출처 : 위키피디아 첫번째 그림은 어느 두점 `x`,` y`를 선택하더라도 포함된다. 따라서 convex set이다. 반면 그림 2는 직선중 일부가 Set에 포함되지 않는다. 따라서 Convex Set이 아니다. 2. Convex Set의 Intersection Convex Set `A`와 `B`가 있고, 이 둘 사이의 교집합은 Convex Set일까? Yes, `A`와 `B`의 교집합이라더라도..