코틀린 코딩테스트 강좌, 다각형의 면적 구하기

오늘의 강좌에서는 다각형의 면적을 구하는 문제에 대해 설명하겠습니다. 이 문제는 코딩 테스트에서 자주 출제되는 문제 중 하나로, 다양한 형태의 다각형이 주어졌을 때 그 면적을 계산하는 알고리즘을 구현하는 방법에 대해 알아보겠습니다.

문제 설명

주어진 여러 점을 이용하여 다각형을 구성할 때, 이 다각형의 면적을 계산하는 알고리즘을 작성하세요. 점은 2D 평면상의 좌표로 표현되며, 점들이 시계방향 또는 반시계방향으로 주어진다고 가정합니다.

예시 입력

    4
    0 0
    4 0
    4 3
    0 4
    

예시 출력

    14.0
    

여기서 면적은 다각형을 구성하는 꼭짓점의 좌표에 따라 결정됩니다. 위 예제에서 주어진 점들은 (0,0), (4,0), (4,3), (0,4)로 이루어진 다각형의 꼭짓점입니다. 이 경우 다각형의 면적은 14.0입니다.

알고리즘 설명

다각형의 면적을 구하는 방법은 여러 가지가 있으나, 일반적으로 사용되는 방법 중 하나는 ‘셔플의 공식’ (Shoelace Formula)입니다. 이 공식을 사용하면 시간 복잡도 O(n)으로 면적을 계산할 수 있습니다.

셔플의 공식

셔플의 공식은 다음과 같이 표현됩니다.

A = 0.5 * | ∑(xiyi+1 - xi+1yi) |

여기서 x_i, y_i는 다각형의 i번째 꼭짓점의 x, y 좌표입니다. 다각형의 꼭짓점이 n개일 때, i는 0부터 n-1까지 증가합니다. 마지막 꼭짓점은 첫 번째 꼭짓점으로 닫습니다 (즉, i+1을 할 때 n으로 돌아갑니다).

문제 풀이 과정

1. 입력 데이터 처리

먼저 입력으로 주어진 다각형의 꼭짓점 수와 꼭짓점 좌표를 읽어야 합니다. 코틀린에서는 리스트를 사용하여 좌표를 저장할 수 있습니다.