모든 챌린지
보통 1명 해결 정답률 100.0%

K-최근접 이웃 분류기

가장 가까운 k개 학습 점의 다수결로 레이블을 예측합니다.

배우게 될 내용

  • 가장 가까운 학습 데이터 찾기
  • 다수결로 예측하기
  • 동점을 정해진 방식으로 처리하기

문제

원문 보기 (영어)

K-최근접 이웃(KNN)은 새 점에 가장 가까운 k개의 학습 점을 보고 가장 흔한 레이블로 분류합니다.

  1. query에서 모든 점까지의 유클리드 거리를 계산합니다.
  2. 점들을 거리순으로 정렬합니다. 거리가 같으면 인덱스가 작은 점이 먼저입니다.
  3. 앞의 k개 점을 골라 레이블을 셉니다.
  4. 표가 가장 많은 레이블을 반환합니다. 동점이면, 정렬된 순서에서 가장 가까운 점이 먼저 나오는 레이블을 반환합니다.

knn_predict(points, labels, query, k)를 구현하세요.

입력

points: 학습 점들, 각 점은 좌표 리스트입니다.

labels: 각 점의 레이블.

query: 분류할 점.

k: 투표할 이웃의 수.

출력

예측한 레이블을 반환하세요.

제약 조건

1 ≤ k ≤ 점의 수 ≤ 1,000

1 ≤ 차원 수 ≤ 20

-1,000 ≤ 각 좌표 ≤ 1,000

예시

예시 1
입력:
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입니다.

예시 2
입력:
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에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.

코더마다 가장 좋은 통과 풀이입니다. 더 빠르고, 메모리를 덜 쓰고, 평가가 좋은 풀이가 위에 옵니다.

# 코더 언어 시간 메모리 AI 평가 풀이
1 ННикита Python 930 ms - 5/5 코드 보기

다른 사람의 풀이 보기

커뮤니티 솔루션

스포일러: 아래에 1개 전체 솔루션 있음 먼저 직접 풀어보세요. 다른 개발자의 코드와 AI 리뷰도 참고할 수 있습니다. 로그인하고 문제를 풀면 토론에 참여할 수 있습니다.