| [ QuizWit ] in KIDS 글 쓴 이(By): mkjung (띠방탱이들) 날 짜 (Date): 2000년 6월 9일 금요일 오전 04시 25분 56초 제 목(Title): Re: 점들사이의 거리 2차원 좌표평면내에 유한한 넓이의 정사각형이 있고, 정사각형 안에 n개의 점이 있습니다. 점들을 A1, A2, ..., An 이라고 할 때, 서로간의 거리가 d 이하인 점의 쌍(Am, An)을 모두 찾고 싶습니다. 여기서 d << (정사각형의 한변의 길이) 라고 가정하면, O(n^2) 미만의 복잡도를 가지는 알고리즘이 있습니까? Divide & Conquer를 시도해봤는데 별로 깔끔해보이지 않아서.. -_-; ============= 오하하~ 이문제 옛날에 퀄리본다고 공부했던문제다! 알고리듬 구하는문제가 아니었구요.... number of such point의 확률분포를 구하는 문제였어요 점들이 unifrom distribution 이라고 주어질경우... 우히히... 이 확률문제도 풀어보세요! 일반적으로는 정사각형의 길이를 d라고 할때 임의의 r을주고 서로간의 길이가 r이하인 점들의 갯수를 random variable X로주고 요 랜덤바리에이블의 확률 분포를 구하는문제지요. 이런분야의 문제를 geometric probabilty 라구합니다. 키즈의 정신박약 개구리들을 무찌르러 이땅에 태어나신 하늘같으신 인류의 영웅 씨방돼지를 받들어모시고, 얼굴 붉게 밝히고 귀염둥이 앞세우고 개구리잡이에 앞장서자. --- 키즈인들을 위한 어린이날 교시. |