이번 글에서는 평면 위에 주어진 좌표 점들을 이용해 만들 수 있는 평행사변형(parallelogram)의 개수를 계산하는 방법을 다룹니다.
평행사변형은 사각형의 한 종류로, 마주 보는 두 변이 서로 평행하며 그에 따라 마주 보는 각의 크기도 서로 같다는 성질을 가지고 있습니다.
문제 이해하기
예제를 통해 문제를 살펴보겠습니다.
입력 −
int a[] = {0, 2, 5, 5, 2, 5, 2, 5, 2};
int b[] = {0, 0, 1, 4, 3, 8, 7, 11, 10};출력 − 평면 위의 평행사변형 개수: 3
설명 − x좌표와 y좌표가 각각 배열로 주어졌습니다. 이 (x, y) 좌표 점들을 조합하면 아래 그림과 같이 총 3개의 평행사변형을 만들 수 있습니다.
입력 −
a[] = {0, 3, 1, 4, 1, 5};
b[] = {0, 1, 3, 4, 4, 4};출력 − 평면 위의 평행사변형 개수: 1
설명 − 마찬가지로 주어진 (x, y) 좌표 점들을 이용해 1개의 평행사변형만 만들 수 있습니다.
해결 방법 및 핵심 아이디어
이 문제를 효율적으로 풀려면 평행사변형의 기하학적 성질을 활용해야 합니다. 핵심은 바로 대각선의 교차점(중점)입니다.
평행사변형의 대각선은 서로를 이등분합니다. 따라서 어떤 두 선분이 같은 중점을 공유한다면, 그 두 선분을 대각선으로 하는 평행사변형이 반드시 하나 존재하게 됩니다. 즉, 같은 중점을 가지는 선분 쌍의 개수만 세면 평행사변형의 개수를 구할 수 있습니다.
프로그램의 동작 순서는 다음과 같습니다.
- x좌표 값을 담는 첫 번째 배열과 y좌표 값을 담는 두 번째 배열을 입력받습니다.
- 첫 번째 배열의 크기를 계산하고, 데이터를 함수에 전달하여 처리를 진행합니다.
- pair 형태의 key와 int 형태의 value를 저장할 map 변수를 생성합니다.
- 만들 수 있는 평행사변형의 총 개수를 저장할 임시 변수 count를 선언합니다.
- FOR 루프를 i = 0부터 배열_1의 크기까지 실행합니다.
- 그 안에서 FOR 루프를 j = i+1부터 배열_1의 크기까지 실행합니다.
- 루프 내부에서 a_mid에는 a[i] + a[j]를, b_mid에는 b[i] + b[j]를 저장합니다. 이 값은 두 점을 이었을 때 대각선 중점의 좌표 합에 해당합니다.
- map에 해당 중점 pair의 등장 횟수를 1씩 증가시킵니다.
- 모든 점 쌍을 확인한 후, map을 처음부터 끝까지 순회하는 또 다른 루프를 시작합니다.
- 루프 내부에서 해당 pair의 value(y값)를 임시 변수에 저장합니다.
- count에 temp * (temp − 1) / 2를 더합니다. 같은 중점을 가지는 선분들 중 2개를 고르는 조합의 수를 의미합니다.
- count를 반환하고 결과를 출력합니다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
//평면 위의 평행사변형 개수 세기
int parallelogram(int a[], int b[], int size){
map<pair<int, int>, int> um;
int count = 0;
for (int i=0; i<size; i++){
for (int j=i+1; j<size; j++){
int a_mid = a[i] + a[j];
int b_mid = b[i] + b[j];
um[make_pair(a_mid, b_mid)]++;
}
}
for (auto it = um.begin(); it != um.end(); it++){
int temp = it->second;
count += temp * (temp - 1) / 2;
}
return count;
}
int main(){
int a[] = {0, 3, 1, 4, 1, 5};
int b[] = {0, 1, 3, 4, 4, 4};
int size = sizeof(a) / sizeof(int);
cout << "평면 위의 평행사변형 개수: " << parallelogram(a, b, size) << endl;
return 0;
}
출력 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다 −
평면 위의 평행사변형 개수: 1
복잡도 분석
모든 점 쌍을 확인하는 이중 루프가 사용되므로 시간 복잡도는 O(n²)입니다. 여기서 n은 점의 개수입니다. map을 사용해 중점 정보를 저장하기 때문에, 단순히 모든 네 점 조합(O(n⁴))을 검사하는 완전 탐색보다 훨씬 효율적으로 문제를 해결할 수 있습니다.