22875번 - UCP-Clustering 스페셜 저지다국어
| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 (추가 시간 없음) | 1024 MB (추가 메모리 없음) | 72 | 24 | 19 | 36.538% |
문제
군집화(clustering) 알고리즘은 같은 클러스터에는 최대한 비슷한 데이터가 묶이고, 서로 다른 클러스터 사이에는 다른 데이터들이 위치하도록 하는 알고리즘이다. UCP-Clustering은 군집화 알고리즘 중 하나로, 2차원 평면 위에 $n$개의 데이터가 주어질 때 다음과 같은 방식으로 데이터를 $k$개의 클러스터로 나눈다.
- 각 클러스터는 구심점이 되는 중심 좌표를 하나씩 가진다. $n$개의 데이터 중 서로 다른 $k$개를 무작위로 선택하고, 각 데이터의 좌표를 중심 좌표로 갖는 $k$개의 빈 클러스터를 만든다.
- 아래의 과정을 반복한다.
- 각각의 데이터에 대하여 유클리드 거리가 가장 가까운 클러스터의 중심 좌표를 선택하고, 그에 해당하는 클러스터에 그 데이터를 포함시킨다. 가장 가까운 중심 좌표가 여러 개라면 그중에서 가장 작은 것을 선택한다. 좌표 $(x_1, y_1)$이 $(x_2, y_2)$보다 작다는 것은 $x_1 < x_2$거나, $x_1=x_2$이고 $y_1<y_2$인 경우를 의미한다.
- 각각의 클러스터에 대하여 클러스터의 새로운 중심 좌표를 계산한다. 각 클러스터의 새로운 중심 좌표는 그 클러스터에 포함된 모든 데이터의 좌표들로부터 각 차원별로 중앙값을 계산하여 결정된다. 단, 값의 개수가 짝수일 경우, 중앙값은 값들을 정렬했을 때 가운데 두 값의 평균으로 계산된다.
- 만약 모든 클러스터의 새로운 중심 좌표가 원래의 중심 좌표와 같다면 알고리즘을 종료한다. 그렇지 않다면 클러스터 구성을 초기화하고, 이 새로운 중심 좌표들을 중심 좌표로 갖는 $k$개의 빈 클러스터를 새로 만든다.
예를 들어, 3개의 데이터 $\{(1, 2), (3, 4), (5, 6)\}$를 UCP-Clustering 알고리즘을 이용해 두 개의 클러스터로 나누는 상황을 생각해 보자. $(1, 2)$와 $(3, 4)$를 초기 중심 좌표로 선택하면 $\{(1, 2)\}$와 $\{(3, 4), (5, 6)\}$ 두 개의 클러스터로 나뉘고, 두 클러스터의 중심 좌표는 각각 $(1, 2)$, $(4, 5)$가 된다. 다른 예시로 $(1, 2)$와 $(5, 6)$을 초기 중심 좌표로 선택하면 $\{(1, 2), (3, 4)\}$와 $\{(5, 6)\}$으로 나뉘고, 두 클러스터의 중심 좌표는 각각 $(2, 3)$, $(5, 6)$이 된다. 예시에서 알 수 있듯이, 초기에 클러스터의 중심 좌표를 어떻게 선택하느냐에 따라 알고리즘의 실행 결과가 달라지며, 위의 두 경우에서는 2번 과정이 모두 2번 반복된다.
$k=2$로 고정한다면 가능한 초기 중심 좌표의 경우의 수는 총 $n(n-1)/2$ 가지이다. 알고리즘을 완료했을 때 두 클러스터의 중심 좌표로 가능한 경우를 모두 찾고, 각 경우에 대해 수렴하는 데까지 걸리는 2번 과정의 반복 횟수의 기댓값을 구하시오.
입력
첫 번째 줄에 데이터의 수 $N$이 주어진다. ($2 \leq N \leq 512$)
그 후 $N$개의 줄에 $i$번째 데이터의 좌표인 $(x_i, y_i)$가 공백을 사이에 두고 주어진다. 모든 좌표는 정수이며, 모든 데이터의 좌표는 서로 다르다. ($-10^6 \leq x_i, y_i \leq 10^6$)
출력
두 클러스터의 최종 중심 좌표 $\mu_1 = (x^{\mu}_{1}, y^{\mu}_{1})$, $\mu_2 = (x^{\mu}_{2}, y^{\mu}_{2})$와 클러스터의 중심 좌표가 두 좌표로 수렴하는 데까지 걸리는 2번 과정의 반복 횟수의 기댓값을 공백을 사이에 두고 출력한다. 단, 두 좌표 중 더 작은 쪽을 $\mu_1$으로 둔다. 가능한 좌표 쌍이 여러 개 존재하는 경우 $\mu_1$이 작은 것부터, $\mu_1$이 같은 경우는 $\mu_2$가 작은 것부터 출력한다. 출력하는 값의 절대 오차 또는 상대 오차는 $10^{-6}$까지 허용한다.
주어지는 모든 데이터에서 처음에 클러스터의 중심 좌표가 되는 데이터를 어떻게 고르더라도 UCP-Clustering이 실패하는 상황, 즉 두 클러스터의 중심 좌표가 같아지거나, 한쪽 클러스터가 비거나, 클러스터의 중심 좌표가 수렴하지 않게 되는 상황이 발생하지 않음이 보장된다.
예제 입력 1
3 1 2 3 4 5 6
예제 출력 1
1.0 2.0 4.0 5.0 2.000000 2.0 3.0 5.0 6.0 2.000000
예제 입력 2
4 0 0 0 3 3 0 3 3
예제 출력 2
0.0 0.0 3.0 3.0 1.000000 0.0 1.5 3.0 1.5 2.000000 0.0 3.0 3.0 0.0 1.000000 1.5 0.0 1.5 3.0 2.000000
노트
첫 번째 예제에서, 알고리즘은 다음과 같이 동작한다.
- 초기 두 클러스터의 중심 좌표로 $(1, 2)$, $(3, 4)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(1, 2)$, $(4, 5)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.
- 초기 두 클러스터의 중심 좌표로 $(1, 2)$, $(5, 6)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(2, 3)$, $(5, 6)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.
- 초기 두 클러스터의 중심 좌표로 $(3, 4)$, $(5, 6)$를 선택한 경우: 첫 번째 반복을 통해 두 클러스터의 중심 좌표가 각각 $(2, 3)$, $(5, 6)$으로 바뀌고, 두 번째 반복에서 클러스터의 중심 좌표가 바뀌지 않아 알고리즘이 종료된다.
세 가지 경우를 모두 고려했을 때, 중심 좌표가 $\mu_1=(1, 2)$와 $\mu_2=(4, 5)$로 수렴하는 데에 걸리는 평균 반복 횟수는 2회이다. 마찬가지로, $\mu_1=(2, 3)$과 $\mu_2=(5, 6)$으로 수렴하는 데에 걸리는 평균 반복 횟수 또한 2회이다. 두 $\mu_1$ 중 $(1, 2)$가 $(2, 3)$보다 작으므로 $(1, 2)$와 $(4, 5)$로 수렴하는 경우부터 출력한다.
© 2023 All Rights Reserved. 주식회사 스타트링크 | 서비스 약관 | 개인정보 보호 | 결제 이용 약관 | 도움말 | 광고 문의 | 업데이트 노트 | 이슈 | TODO
- 사업자 등록 번호: 541-88-00682
- 대표자명: 최백준
- 주소: 서울시 서초구 서초대로74길 29 서초파라곤 412호
- 전화번호: 02-521-0487 (이메일로 연락 주세요)
- 이메일: contacts@startlink.io
- 통신판매신고번호: 제 2017-서울서초-2193 호