문제 정의
2차원 평면 위에 여러 개의 점이 주어졌을 때, 같은 직선 위에 존재하는 점들의 최대 개수를 구하는 문제입니다.
예를 들어 다음과 같은 점들이 있다고 가정해 보겠습니다.
{(1,1), (3,2), (5,3), (4,1), (2,3), (1,4)}
이 경우 직선 위에 놓일 수 있는 최대 점의 개수는 4개입니다.
접근 방법
이 문제는 두 점이 만드는 직선의 기울기(slope)를 이용해 해결할 수 있습니다. 세 점 (x1, y1), (x2, y2), (x3, y3)가 한 직선 위에 있으려면 다음 조건을 만족해야 합니다.
(y3 − y2) × (x2 − x1) = (y2 − y1) × (x3 − x2)
나눗셈 대신 교차 곱셈(cross multiplication)을 사용하면 부동소수점 오차 없이 정수 연산만으로 정확하게 비교할 수 있다는 장점이 있습니다.
알고리즘 단계
- 점의 개수를 n이라 할 때, n < 3이면 그대로 n을 반환합니다.
- 정답 변수 ans를 2로 초기화합니다.
- i를 1부터 n−1까지 반복하면서 인접한 두 점 p1(i−1번째)과 p2(i번째)를 선택합니다.
- p1과 p2가 같은 좌표라면, 전체 점 목록에서 해당 좌표와 일치하는 점의 개수를 셉니다.
- 그렇지 않다면 모든 점 p3에 대해 위의 교차 곱셈 조건을 검사하여 같은 직선 위에 있는 점의 개수를 셉니다.
- 매 반복마다 ans를 count와 비교해 더 큰 값으로 갱신합니다.
- 모든 반복이 끝나면 ans를 반환합니다.
C++ 구현 코드
아래 코드를 통해 실제 구현 방법을 확인할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
int maxPoints(vector<vector<int>>& points) {
int n = points.size();
if(n < 3) return n;
int ans = 2;
for(int i = 1; i < n; i++){
int count = 0;
lli x1 = points[i-1][0];
lli x2 = points[i][0];
lli y1 = points[i-1][1];
lli y2 = points[i][1];
if(x1 == x2 && y1 == y2){
// 두 점이 동일한 경우, 같은 좌표의 점 개수를 셈
for(int j = 0; j < n; j++){
if(points[j][0] == x1 && points[j][1] == y1) count++;
}
} else {
// 교차 곱셈으로 세 점의 일직선 여부 판별
for(int j = 0; j < n; j++){
int x3 = points[j][0];
int y3 = points[j][1];
if((y3 - y2) * (x2 - x1) == (y2 - y1) * (x3 - x2)) count++;
}
}
ans = max(ans, count);
}
return ans;
}
};
int main(){
Solution ob;
vector<vector<int>> v = {{1,1},{3,2},{5,3},{4,1},{2,3},{1,4}};
cout << (ob.maxPoints(v));
}실행 결과
입력
[{1,1},{3,2},{5,3},{4,1},{2,3},{1,5}]출력
4
복잡도 분석
- 시간 복잡도: O(n²) — 서로 다른 두 점의 조합마다 나머지 모든 점을 검사합니다.
- 공간 복잡도: O(1) — 추가적인 자료구조 없이 상수 공간만 사용합니다.
좌표값이 클 때 곱셈 과정에서 오버플로우가 발생할 수 있으므로, 코드에서처럼 long long int 타입을 사용하는 것이 안전합니다.