다른 방법으로 풀어보는 가장 가까운 점 찾기~
divde&conquer는 아님!
Plane Sweeping - 평면을 쓸다
그림으로 설명하기 어려운 문제 중 하나임
직선을 만들고 오른쪽으로 밀면서 풀겠다.
직선으로 미는 것을 컴퓨터로 어떻게 구현할 것인가?
실제 직선은 제일 왼쪽 끝 점에서 시작한다.
다음 점으로 jump => 직선을 총 n개를 왼쪽에서부터 순서대로 그리게 된다.
1. 직선을 x좌표로 sorting한다. n log n
직선 안에 어떤 자료구조가 저장이 되어 있다고 생각하자
왼쪽부분에 이 문제를 푸는데에 필요한 정보가 저장이 되어 있다.
문제마다 어떤 자료구조가 저장되어 있을 것인지 다르다.
여기까지 왔다고 치자.
2. 왼쪽 점부터 순서대로 (n번)
다음 점에 갔을 때, 재귀적으로(수학점 귀납법으로) 최소거리를 알고 있다고 생각
최소거리 d만큼의 거리
3. 현재까지 본 점들의 제일 오른쪽 폭 d인 Band내의 점들을
Balanced Bianary Tree에 y좌표로 sorted하여 저장
점은 하나가 추가되지만
점이 여러개 빠질 수 있음.
하지만 전체를 봤을 때 점 하나당 한번 들어오고 한번 나간다 nlog n
새로운 직선이 생기면서 Band도 같은 거리만큼 이동한다.
BBT에서 빠져야 하는 점이 생긴다. (점은 x좌표로 sorting 되어 있으므로 알 수 있다.)
4. 다음 점에 갈 때 Band를 이동하고 Tree에서 점 제거
5개찾기 (log n)
지난 시간 처럼 5개랑만 거리를 재면 된다,
d가 안바뀌면 이상태로 끝. 바뀌면 폭을 줄이고 점이 일부 빠지면 되는 것
정리: 23:32
