라인 스위핑
-
Line Sweep 알고리즘 :: 마이구미알고리즘 2018. 2. 11. 19:09
이 글은 Line Sweep 알고리즘을 다룬다.Line Sweep, Sweep Line, 라인 스위핑 등과 같이 불려진다.일반적으로 가장 가까운 두 점을 찾는 문제에서 출발한다.다음 링크의 문제 풀이를 통하여 알고리즘을 설명할 것이다.( 백준 2261번 "가장 가까운 두 점" )참고 - https://www.acmicpc.net/blog/view/25 수 많은 점들 중에서 가장 가까운 두 점을 찾는 문제가 존재한다.이러한 문제의 시나리오는 다음과 같다. See the Pen line sweeping by leejunghyun (@mygumi) on CodePen. 순수한 접근으로 점들 중에서 가장 가까운 두 점을 찾는 방법은 간단하다.모든 점들을 확인하면 된다.하지만 이러한 경우 시간복잡도는 O(N^2)..