문제 개요
오늘의 코딩 테스트 문제는 다각형의 면적을 구하는 알고리즘이었다. 백준 2166번 문제다. 코딩 테스트 준비와 실전 감각 유지를 위해 문제를 풀고 있다.
문제 분석
문제의 핵심은 2차원 평면상의 N개 점으로 이루어진 다각형의 면적을 구하는 것이다. 입력으로는 점의 개수 N(3 ≤ N ≤ 10,000)과 각 점의 x, y 좌표가 주어진다. 좌표값은 절댓값이 100,000을 넘지 않는 정수다.
주요 포인트:
1.
N개의 점 좌표가 x, y 형태로 주어짐
2.
N각형의 넓이를 구해야 함
3.
결과는 소수점 첫째 자리까지 출력
접근 방식
처음에는 다각형을 N-2개의 삼각형으로 나누어 각 삼각형의 면적을 구하는 방식을 고려했다. 하지만 이 방법은 구현이 복잡하고 오목 다각형 처리에 문제가 있을 수 있다고 판단했다.
결국 신발끈 공식(Shoelace formula)을 사용하기로 결정했다. 이 공식은 다각형의 꼭짓점 좌표만으로 면적을 계산할 수 있어 효율적이다.
코드 구현
#include <iostream>
#include <cmath>
#include <vector>
#include <cstdio>
using namespace std;
int main()
{
int N;
long long acc=0;
cin >> N;
vector<pair<long long, long long>> v(N);
for (int i = 0; i<N; i++)
cin >> v[i].first >> v[i].second;
for (int i = 0; i<N; i++)
{
int j = (i + 1) % N;
acc += v[i].first * v[j].second - v[j].first * v[i].second;
}
double result = abs(acc) / 2.0;
printf("%.1f\n", result);
return 0;
}
C++
복사
코드의 핵심은 신발끈 공식의 구현 부분이다. 각 점의 x좌표와 다음 점의 y좌표를 곱한 값에서 y좌표와 다음 점의 x좌표를 곱한 값을 뺀다. 이를 모든 점에 대해 반복하고 절댓값을 취한 뒤 2로 나누면 면적이 나온다.
문제 해결 과정
구현 과정에서 한 가지 문제에 부딪혔다. 문제 설명에는 좌표값이 100,000을 넘지 않는다고 했지만, int 자료형으로는 오버플로우가 발생했다. 결국 long long으로 변경하여 해결했다.
최적화 측면에서는, 처음에 각 삼각형의 면적을 개별적으로 계산하는 함수를 만들었지만, 신발끈 공식을 사용하면서 단순 for문으로 대체할 수 있었다. 이 방식은 오목 다각형도 자동으로 처리할 수 있다는 장점이 있다.
회고
이번 문제를 통해 기하학적 알고리즘의 중요성을 다시 한번 깨달았다. 단순히 구현 능력뿐만 아니라, 적절한 수학적 공식을 알고 적용하는 것이 효율적인 문제 해결의 핵심이라는 점을 실감했다.
개선할 점이 있다면, 기하 알고리즘에 대한 더 깊은 이해가 필요하다는 것이다. 다음에는 다양한 기하 문제를 더 풀어보며 이 부분을 보완해야겠다.
