이 문제에서는 2차원 평면 위에 있는 n개의 점이 주어지며, 각 점의 좌표는 (x, y)입니다. 우리가 해결해야 할 과제는 여러 개의 쿼리를 처리하는 것입니다. 각 쿼리마다 정수 R이 주어지고, 원점을 중심으로 하며 반지름이 R인 원 내부에 포함되는 점의 개수를 구해야 합니다.
문제 상세 설명
각 쿼리에 대해 n개의 점 중에서 중심이 원점 (0, 0)이고 반지름이 R인 원의 내부(경계선 포함)에 있는 점의 총 개수를 찾아야 합니다.
예시로 문제 이해하기
입력
n = 5 2 1 1 2 3 3 -1 0 -2 -2 쿼리 1: 2
출력
1
설명 − 쿼리에서 반지름은 2이며, 점 (-1, 0)만 원 안에 속하고 나머지 점들은 모두 원 밖에 있습니다.
기본 접근 방법
원의 수학적 방정식은 (x₂ − x₁)² + (y₂ − y₁)² = r² 입니다. 따라서 중심이 (0, 0)인 원 안에 점 (x, y)가 속하려면 다음 조건을 만족해야 합니다.
x² + y² ≤ r²
이 문제를 해결하는 가장 간단한 방법은 각 쿼리마다 모든 점을 순회하면서 위 공식을 이용해 해당 점이 원 내부에 있는지 여부를 확인하는 것입니다.
이 풀이의 동작을 보여주는 프로그램:
예제 코드 1
#include <iostream>
using namespace std;
int solveQuery(int x[], int y[], int n, int R) {
int count = 0;
for(int i = 0; i< n ; i++){
if(((x[i]*x[i]) + (y[i]*y[i]) ) <= (R*R) )
count++;
}
return count;
}
int main() {
int x[] = { 2, 1, 3, -1, -2 };
int y[] = { 1, 2, 3, 0, -2 };
int n = sizeof(x) / sizeof(x[0]);
int Q = 2;
int query[] = {4, 2 };
for(int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": The number of points that lie inside the circle is "<<solveQuery(x, y, n, query[i])<<"\n";
return 0;
}출력
For Query 1: The number of points that lie inside the circle is 4 For Query 2: The number of points that lie inside the circle is 1
이 접근 방식의 시간 복잡도는 O(n × Q)입니다. 각 쿼리마다 n개의 모든 점에 대해 x² + y² 값을 계산해야 하기 때문입니다.
효율적인 접근 방법
더 효율적인 풀이는 모든 n개의 점에 대해 x² + y² 값을 미리 계산(precompute)하여 배열에 저장해 두고, 이후 모든 쿼리에서 이를 재사용하는 것입니다. 성능을 더욱 최적화하려면 이 배열을 정렬한 뒤, 원 밖에 처음으로 벗어나는 첫 번째 원소를 이진 탐색으로 찾으면 됩니다. 이렇게 하면 각 쿼리를 O(log n) 시간에 처리할 수 있어 전체 복잡도가 크게 개선됩니다.
이 풀이의 동작을 보여주는 프로그램:
예제 코드 2
#include <bits/stdc++.h>
using namespace std;
int solveQuery(int points[], int n, int rad) {
int l = 0, r = n - 1;
while ((r - l) > 1) {
int mid = (l + r) / 2;
if (points[mid] > (rad * rad))
r = mid - 1;
else
l = mid;
}
if ((sqrt(points[l])) > (rad * 1.0))
return 0;
else if ((sqrt(points[r])) <= (rad * 1.0))
return r + 1;
else
return l + 1;
}
int main() {
int n = 5;
int point[n][2] = { {2, 1}, {1, 2}, {3, 3}, {-1, 0}, {-2, -2} };
int Q = 2;
int query[] = {4, 2 };
int points[n];
// 값 미리 계산 (Precomputing)
for (int i = 0; i < n; i++)
points[i] = ( point[i][0]*point[i][0] ) + ( point[i][1]*point[i][1] );
sort(points, points + n);
for(int i = 0; i < Q; i++)
cout<<"For Query "<<(i+1)<<": The number of points that lie inside the circle is "<<solveQuery(points, n, query[i])<<"\n";
return 0;
}출력
For Query 1: The number of points that lie inside the circle is 4 For Query 2: The number of points that lie inside the circle is 1
마무리
거리 제곱 값을 미리 계산하고 정렬해 두면, 각 쿼리마다 단순히 이진 탐색만으로 원 안에 있는 점의 개수를 빠르게 구할 수 있습니다. 쿼리의 개수가 많아질수록 이러한 전처리 기반 최적화가 가지는 성능상 이점이 커지므로, 실제 코딩 테스트나 경쟁 프로그래밍에서 매우 유용하게 활용될 수 있는 패턴입니다.