문제
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
예시
입력:
points = [
[1.0, 1.0],
[2.0, 2.0],
[8.0, 8.0],
[9.0, 9.0]
]
labels = ["A", "A", "B", "B"]
query = [3.0, 3.0]
k = 3
예상 출력:
expected = "A"
입력:
std::vector<std::vector<double>> points = {
{1.0, 1.0},
{2.0, 2.0},
{8.0, 8.0},
{9.0, 9.0}
};
std::vector<std::string> labels = {"A", "A", "B", "B"};
std::vector<double> query = {3.0, 3.0};
long long k = 3;
예상 출력:
std::string expected = "A";
입력:
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[] labels = new string[] {"A", "A", "B", "B"};
double[] query = new double[] {3.0, 3.0};
long k = 3;
예상 출력:
string expected = "A";
설명
(3, 3)에서의 거리: (2, 2) ≈ 1.41, (1, 1) ≈ 2.83, (8, 8) ≈ 7.07. 가장 가까운 3개의 레이블은 A, A, B이므로 답은 A입니다.
입력:
points = [
[0.0, 0.0],
[4.0, 0.0],
[0.0, 4.0],
[4.0, 4.0]
]
labels = ["red", "blue", "blue", "red"]
query = [1.0, 1.0]
k = 2
예상 출력:
expected = "red"
입력:
std::vector<std::vector<double>> points = {
{0.0, 0.0},
{4.0, 0.0},
{0.0, 4.0},
{4.0, 4.0}
};
std::vector<std::string> labels = {"red", "blue", "blue", "red"};
std::vector<double> query = {1.0, 1.0};
long long k = 2;
예상 출력:
std::string expected = "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[] labels = new string[] {"red", "blue", "blue", "red"};
double[] query = new double[] {1.0, 1.0};
long k = 2;
예상 출력:
string expected = "red";
설명
가장 가까운 점은 (0, 0)(red)입니다. 다음 두 점 (4, 0)과 (0, 4)는 거리가 같으므로 인덱스가 작은 (4, 0)(blue)이 선택됩니다. red와 blue가 한 표씩이고 red의 점이 먼저 나왔으므로 답은 red입니다.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
각 point와 query 사이의 Euclidean distance를 구한 뒤, 작은 index가 tie를 깨도록 distance 순으로 정렬하세요.
힌트 2
정렬된 처음 k개만 vote하므로, 최종 label은 training set의 아주 작은 부분에 의해 결정됩니다.
힌트 3
vote count가 같으면, 기여한 nearest point가 sorted neighbor list에서 더 앞에 나오는 label을 고르세요.
예상 복잡도
시간 O(n log n), 추가 공간 O(n)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.