평면 위에 놓인 점들의 좌표 목록이 주어졌을 때, 그중 임의의 3개 점을 골라 만들 수 있는 가장 큰 삼각형의 넓이를 구하는 문제입니다.
예를 들어 입력이 [[0,0],[0,1],[1,0],[0,2],[2,0]]과 같다면, 출력은 2가 됩니다.
해결 접근 방법
이 문제는 모든 가능한 세 점의 조합을 확인하면서 각 조합으로 만들어지는 삼각형의 넓이를 계산하고, 그중 최댓값을 찾는 방식으로 해결할 수 있습니다. 삼각형의 넓이는 다음과 같은 신발끈 공식(Shoelace Formula)을 이용해 구합니다.
넓이 = 0.5 × |x₁(y₂ − y₃) + x₂(y₃ − y₁) + x₃(y₁ − y₂)|
구체적인 알고리즘 단계는 다음과 같습니다.
- 결과를 저장할 변수 res를 0으로 초기화합니다.
- N을 점 목록의 크기로 설정합니다.
- i를 0부터 N−3까지 반복하며, 그 안에서 j를 i+1부터 N−2까지, k를 i+2부터 N−1까지 반복하여 모든 세 점 조합을 탐색합니다.
- 각 조합의 좌표 (x1, y1), (x2, y2), (x3, y3)를 가져옵니다.
- 신발끈 공식으로 계산한 넓이와 기존 res 중 더 큰 값을 res에 저장합니다.
- 모든 반복이 끝나면 res를 반환합니다.
파이썬 구현 예제
class Solution:
def largestTriangleArea(self, points):
res = 0
N = len(points)
for i in range(N - 2):
for j in range(i + 1, N - 1):
for k in range(i + 2, N):
(x1, y1), (x2, y2), (x3, y3) = points[i], points[j], points[k]
res = max(res, 0.5 * abs(x1 * (y2 - y3) + x2 * (y3 - y1) + x3 * (y1 - y2)))
return res
ob = Solution()
print(ob.largestTriangleArea([[0,0],[0,1],[1,0],[0,2],[2,0]]))
입력
[[0,0],[0,1],[1,0],[0,2],[2,0]]
출력
2.0
복잡도 분석
이 알고리즘은 세 점의 모든 조합을 검사하므로 시간 복잡도는 O(N³)입니다. 점의 개수가 많아지면 실행 시간이 빠르게 증가하므로, 점 개수가 수백 개 이상인 경우에는 볼록 껍질(Convex Hull)을 먼저 계산한 뒤 껍질 위의 점들만 조합하는 방식으로 최적화할 수 있습니다. 가장 큰 삼각형의 세 꼭짓점은 항상 볼록 껍질 위에 존재하기 때문입니다.