백준에서 3600문제 넘게 풀면서 루비 난이도 문제를 처음으로 푼 기념으로 이 문제만 별개의 포스트로 정리해본다. 무려 월드 파이널 문제이며 그 해 문제 중에서도 solved.ac 기준으로 난이도가 가장 높은 문제이다. 백준 BOJ 10058번 : 센서 네트워크 문제 난이도 : Ruby V 알고리즘 분류 : 기하학, 이분 매칭 2차원 좌표 평면 상에 N개의 점이 주어질 때, 어떤 두 점의 거리도 M 이하가 되게 하는 점들의 집합의 최대 크기와 그 때의 점들의 번호 목록을 구하는 문제이다. 가장 naive하게 생각할 수 있는 풀이는 각 점을 집합에 포함시키거나 시키지 않은 뒤 해당 집합에서 가장 먼 두 점 사이의 거리가 M 이하라면 집합의 최대 크기를 비교하여 갱신해주는 방식이 있다. 이 때의 시간 복잡도..