문제
K-평균은 레이블 없는 데이터에서 그룹을 찾습니다. 주어진 중심에서 시작해 iterations번 반복합니다.
- 배정: 각 점을 가장 가까운 중심(유클리드 거리)의 군집에 넣습니다. 두 중심과의 거리가 같으면 인덱스가 작은 중심을 고릅니다.
- 갱신: 각 중심을 배정된 점들의 평균으로 옮깁니다. 점이 하나도 없는 중심은 그대로 둡니다.
k_means(points, centroids, iterations)를 구현하세요.
입력
points: 데이터 점들, 각 점은 좌표 리스트입니다.
centroids: k개의 초기 중심, 좌표 개수는 점과 같습니다.
iterations: 배정과 갱신을 몇 번 반복할지.
출력
최종 중심들을 원래 순서대로 반환하세요.
제약 조건
1 ≤ 점의 수 ≤ 1,000, 1 ≤ k ≤ 20, 1 ≤ 차원 수 ≤ 10
0 ≤ iterations ≤ 100
-1,000 ≤ 각 좌표 ≤ 1,000
예시
예시 1
입력:
points = [
[1.0, 1.0],
[1.5, 2.0],
[8.0, 8.0],
[9.0, 8.5]
]
centroids = [
[0.0, 0.0],
[10.0, 10.0]
]
iterations = 1
예상 출력:
expected = [
[1.25, 1.5],
[8.5, 8.25]
]입력:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{1.5, 2.0},
{8.0, 8.0},
{9.0, 8.5}
};
std::vector<std::vector<double>> centroids = {
{0.0, 0.0},
{10.0, 10.0}
};
long long iterations = 1;
예상 출력:
std::vector<std::vector<double>> expected = {
{1.25, 1.5},
{8.5, 8.25}
};입력:
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {1.5, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 8.5}
};
double[][] centroids = new double[][] {
new double[] {0.0, 0.0},
new double[] {10.0, 10.0}
};
long iterations = 1;
예상 출력:
double[][] expected = new double[][] {
new double[] {1.25, 1.5},
new double[] {8.5, 8.25}
};설명
처음 두 점은 (0, 0)에 더 가깝고 마지막 두 점은 (10, 10)에 더 가깝습니다. 새 중심은 평균입니다: ((1 + 1.5) / 2, (1 + 2) / 2) = (1.25, 1.5), ((8 + 9) / 2, (8 + 8.5) / 2) = (8.5, 8.25).
예시 2
입력:
points = [
[0.0],
[1.0],
[10.0]
]
centroids = [
[0.0],
[100.0]
]
iterations = 2
예상 출력:
expected = [
[3.666667],
[100.0]
]입력:
std::vector<std::vector<double>> points = {
{0.0},
{1.0},
{10.0}
};
std::vector<std::vector<double>> centroids = {
{0.0},
{100.0}
};
long long iterations = 2;
예상 출력:
std::vector<std::vector<double>> expected = {
{3.666667},
{100.0}
};입력:
double[][] points = new double[][] {
new double[] {0.0},
new double[] {1.0},
new double[] {10.0}
};
double[][] centroids = new double[][] {
new double[] {0.0},
new double[] {100.0}
};
long iterations = 2;
예상 출력:
double[][] expected = new double[][] {
new double[] {3.666667},
new double[] {100.0}
};설명
1회차: (100)은 모든 점에서 멀기 때문에 세 점 모두 중심 1에 배정되고, 중심 1은 (0 + 1 + 10) / 3 ≈ 3.666667로 이동합니다. 중심 2는 점이 없으므로 100에 그대로 있습니다. 2회차도 같은 배정이므로 결과는 [[3.666667], [100]]입니다.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.