C++로 k개의 점을 원 안에 포함하는 최소 반지름 구하기

여러 개의 좌표 점과 하나의 정수 k가 주어졌을 때, 중심이 (0, 0)인 원이 최소한 k개의 점을 포함하도록 만드는 최소 반지름을 구하는 문제를 살펴보겠습니다.

예를 들어, 점들이 (1, 1), (-1, -1), (1, -1)로 주어지고 k = 3이라면, 세 점을 모두 원 안에 넣기 위해 필요한 최소 반지름은 2가 됩니다.

접근 방법

이 문제의 핵심 아이디어는 매우 간단합니다.

원의 중심이 항상 원점 (0, 0)에 고정되어 있으므로, 각 점과 원점 사이의 유클리드 거리만 계산하면 됩니다. 그런 다음 계산된 거리들을 오름차순으로 정렬하고, 정렬된 배열에서 k번째 값을 반환하면 그것이 곧 k개의 점을 모두 포함할 수 있는 최소 반지름이 됩니다.

거리 제곱값을 사용하면 실제로 sqrt 연산 없이도 상대적인 크기 비교가 가능하므로, 코드에서는 x² + y² 값을 그대로 저장하여 효율성을 높였습니다.

C++ 구현 예제

#include<iostream>
#include<algorithm>
using namespace std;
struct point{
    int x, y;
};
int minRadius(int k, point points[], int n) {
    int dist[n];
    for (int i = 0; i < n; i++)
    dist[i] = points[i].x * points[i].x + points[i].y * points[i].y;
    // 거리(제곱값) 오름차순 정렬
    sort(dist, dist + n);
    return dist[k - 1];
}
int main() {
    int k = 3;
    point points[] = {{1, 1}, {-1, -1}, {1, -1}};
    int n = sizeof(points)/sizeof(points[0]);
    cout << "Minimum radius: " << minRadius(k, points, n) << endl;
}

실행 결과

Minimum radius: 2

코드 설명

minRadius 함수는 먼저 모든 점에 대해 원점까지의 거리 제곱(x² + y²)을 계산하여 dist 배열에 저장합니다. 이후 C++ STL의 sort 함수를 사용해 배열을 오름차순으로 정렬한 뒤, 인덱스 k - 1 위치의 값을 반환합니다.

예제에서 세 점의 거리 제곱값은 각각 2, 2, 2이며, k = 3이므로 세 번째로 작은 값인 2가 결과로 출력됩니다.

시간 복잡도

n개의 점에 대해 거리 계산은 O(n), 정렬은 O(n log n)이 소요되므로 전체 시간 복잡도는 O(n log n)입니다. 추가적으로 더 빠른 성능이 필요하다면 퀵셀렉트(Quickselect) 알고리즘을 활용해 평균 O(n) 시간에 k번째 거리를 찾는 것도 가능합니다.