[알고리즘 이론] 9. 라인 스위핑
라인 스위핑 공간이나 직선 상에서 한 쪽 시작점을 기준으로 반대편 종료지점까지 스캔하면서 지나가는데, 한 번만 전체 공간을 스캔하면서 마주치는 요소들에 대해 판단기준이 되는 기준을 적용해 주면 정답이 구해지는 형태이다. 즉, 스위핑 알고리즘 문제들은 정렬된 요소들을 한 번만 순회하며 연산하면 정답이 나오게 구현하게 해야한다. 예시 라인을 1,3 / 2,5 / 3,5 / 6,7 총 4개를 준다고 가정한다. 라인들을 pair로 저장하고 pair배열에 삽입 후 정렬 처음 pair 의 시작점(1)을 start, 끝점(3)을 end 로 지정 다음 pair인 2,5 에서 시작점인 2가 끝점보다 적으므로 패스, 끝점이 5로 3보다 크므로 끝점을 5로 바꿈 다음 pair인 3,5 에서 시작점인 3이 끝점보다 작고, 5..
2023. 5. 9.