C++로 원점에서 가장 가까운 K개의 점 찾기

2차원 평면상에 여러 개의 점이 주어졌을 때, 원점(0, 0)에서 가장 가까운 K개의 점을 찾는 문제를 생각해 봅시다. 예를 들어 점들이 (3, 3), (5, -1), (-2, 4)라고 할 때, 가장 가까운 두 점(K = 2)은 (3, 3)과 (-2, 4)입니다.

해결 방법

이 문제는 각 점의 유클리드 거리(Euclidean distance)를 기준으로 점 목록을 정렬한 뒤, 정렬된 목록에서 앞쪽 K개의 요소를 선택하는 방식으로 해결할 수 있습니다. 정렬 후 상위 K개의 점이 바로 원점에 가장 가까운 K개의 점입니다.

여기서 한 가지 최적화 팁을 덧붙이자면, 실제 거리의 제곱근을 계산할 필요는 없습니다. 제곱근 함수는 단조 증가하므로, x² + y² 값만 비교해도 동일한 순서로 정렬됩니다. 이렇게 하면 불필요한 연산을 줄일 수 있습니다.

예제 코드

#include<iostream>
#include<algorithm>
using namespace std;

class Point {
private:
    int x, y;
public:
    Point(int x = 0, int y = 0) {
        this->x = x;
        this->y = y;
    }
    void display() {
        cout << "(" << x << ", " << y << ")";
    }
    friend bool comparePoints(Point &p1, Point &p2);
};

// 두 점의 거리 제곱값을 비교하는 함수
bool comparePoints(Point &p1, Point &p2) {
    float dist1 = (p1.x * p1.x) + (p1.y * p1.y);
    float dist2 = (p2.x * p2.x) + (p2.y * p2.y);
    return dist1 < dist2;
}

// 원점에서 가장 가까운 K개의 점을 출력하는 함수
void closestKPoints(Point points[], int n, int k) {
    sort(points, points + n, comparePoints);
    for (int i = 0; i < k; i++) {
        points[i].display();
        cout << endl;
    }
}

int main() {
    Point points[] = {{3, 3}, {5, -1}, {-2, 4}};
    int n = sizeof(points) / sizeof(points[0]);
    int k = 2;
    closestKPoints(points, n, k);
}

실행 결과

(3, 3)
(-2, 4)

코드 설명

위 코드의 핵심은 comparePoints 함수입니다. 이 함수는 각 점에 대해 x 좌표의 제곱과 y 좌표의 제곱을 더한 값을 계산하여, 이 값을 기준으로 오름차순 정렬을 수행합니다. 이 값은 원점까지의 실제 거리의 제곱에 해당하므로, 값이 작을수록 원점에 가깝다는 의미입니다.

정렬이 완료되면 closestKPoints 함수는 배열의 처음부터 K번째 요소까지 차례대로 출력합니다. 시간 복잡도는 정렬에 의해 지배되므로 O(n log n)입니다. 만약 n이 매우 크고 k가 작다면, 힙(heap) 자료구조나 부분 정렬(partial_sort)을 활용하면 O(n log k)로 성능을 개선할 수 있습니다.