문제
K-최근접 이웃(KNN)은 새 점에 가장 가까운 k개의 학습 점을 보고 가장 흔한 레이블로 분류합니다.
query에서 모든 점까지의 유클리드 거리를 계산합니다.- 점들을 거리순으로 정렬합니다. 거리가 같으면 인덱스가 작은 점이 먼저입니다.
- 앞의 k개 점을 골라 레이블을 셉니다.
- 표가 가장 많은 레이블을 반환합니다. 동점이면, 정렬된 순서에서 가장 가까운 점이 먼저 나오는 레이블을 반환합니다.
knn_predict(points, labels, query, k)를 구현하세요.
입력
points: 학습 점들, 각 점은 좌표 리스트입니다.
labels: 각 점의 레이블.
query: 분류할 점.
k: 투표할 이웃의 수.
출력
예측한 레이블을 반환하세요.
제약 조건
1 ≤ k ≤ 점의 수 ≤ 1,000
1 ≤ 차원 수 ≤ 20
-1,000 ≤ 각 좌표 ≤ 1,000
예시
예시 1
입력:
k = 3
query = [3.0, 3.0]
labels = ["A", "A", "B", "B"]
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
예상 출력:
expected = "A"입력:
long long k = 3;
std::vector<double> query = {3.0, 3.0};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
예상 출력:
std::string expected = "A";입력:
long k = 3;
double[] query = new double[] {3.0, 3.0};
string[] labels = new string[] {"A", "A", "B", "B"};
double[][] points = new double[][] {
new double[] {1.0, 1.0},
new double[] {2.0, 2.0},
new double[] {8.0, 8.0},
new double[] {9.0, 9.0}
};
예상 출력:
string expected = "A";설명
(3, 3)에서의 거리: (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. 가장 가까운 3개의 레이블은 A, A, B이므로 답은 A입니다.
예시 2
입력:
k = 2
query = [1.0, 1.0]
labels = ["red", "blue", "blue", "red"]
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
예상 출력:
expected = "red"입력:
long long k = 2;
std::vector<double> query = {1.0, 1.0};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
예상 출력:
std::string expected = "red";입력:
long k = 2;
double[] query = new double[] {1.0, 1.0};
string[] labels = new string[] {"red", "blue", "blue", "red"};
double[][] points = new double[][] {
new double[] {0.0, 0.0},
new double[] {4.0, 0.0},
new double[] {0.0, 4.0},
new double[] {4.0, 4.0}
};
예상 출력:
string expected = "red";설명
가장 가까운 점은 (0, 0)(red)입니다. 다음 두 점 (4, 0)과 (0, 4)는 거리가 같으므로 인덱스가 작은 (4, 0)(blue)이 선택됩니다. red와 blue가 한 표씩이고 red의 점이 먼저 나왔으므로 답은 red입니다.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.