[주제 제안] O(N log N) Euclidean MST

[justiceHui]

주제 이름

• O(N log N) Euclidean MST

주제 소개 (관련 자료 링크 포함)

2차원 평면 상에 N개의 점이 주어지고, 간선의 가중치가 유클리드 거리로 정의되었을 때 MST를 구하는 문제 들로네 삼각분할을 이용해 O(N log N)에 간선을 3N개 이하로 줄이는 방법을 통해 O(N log N)에 구할 수 있음

대략적인 난이도

• 루비 4 정도

관련 문제 링크

*

[kimjg1119]

집어감