알고리즘_클러스터링(근사)

1. 클러스터링 문제

입력 n개의 점을 K개의 그룹으로 나눌때 중심점을 K개 선택하는 문제
단, 가장 큰 반경을 가진 그룹의 지름이 최소가 되도록 해야함

1.2 클러스터링 문제 해결

1. 임의의 점 하나를 선택한다
2. 위에서 선택된 모든 점과 가장 먼 점을 선택 K번 반복
   

점의 갯수 k
중심점의 갯수 n
시간 복잡도 = O(kn)

d = 중심점의 갯수가 k+1일 경우 중심점의 선택되는 점과 
현재 그 점이 속해있는 중심점 사이의 거리

어떤 점이더라도 자신으로부터 가장 가까운 센터까지의 거리가 d보다 크지 않다
근사비율 = 2