서로 다른 여러 개의 삼각형이 배열로 주어져 있다고 가정해 보겠습니다. 각 삼각형은 triangles[i] = [ai, bi, ci] 형태로 표현되며, 여기서 ai, bi, ci는 i번째 삼각형의 세 변의 길이를 의미합니다. 이번 글에서는 이 삼각형들을 면적을 기준으로 오름차순 정렬하는 C 프로그램을 작성해 보겠습니다.
세 변의 길이만 알고 있을 때 삼각형의 면적을 구하는 대표적인 방법은 헤론의 공식(Heron's Formula)입니다. 먼저 반둘레 p = (a + b + c) / 2를 계산한 뒤, 면적 = √(p × (p − a) × (p − b) × (p − c)) 공식을 적용하면 됩니다.
예를 들어 입력이 (7, 24, 25), (5, 12, 13), (3, 4, 5)라면 출력은 다음과 같습니다.
(3, 4, 5), (5, 12, 13), (7, 24, 25)
문제 해결 단계
- 세 변 a, b, c를 멤버로 가지는 삼각형 구조체(struct)를 정의합니다.
- 삼각형 t를 인자로 받는 square() 함수를 정의합니다.
- 함수 안에서 a = t.a, b = t.b, c = t.c로 값을 가져옵니다.
- (a + b + c) × (a + b − c) × (a − b + c) × (−a + b + c) 값을 반환합니다.
- 메인 함수에서 이중 반복문으로 모든 삼각형 쌍을 비교하고, 앞쪽 삼각형의 면적이 더 크면 두 요소를 교환합니다(버블 정렬 방식).
참고: 위 식은 실제 면적의 제곱값에 해당합니다. 제곱근 연산은 단조 증가 함수이므로, 굳이 √를 취하지 않고 제곱값끼리 비교해도 정렬 결과는 동일합니다. 덕분에 부동소수점 연산이나 math.h 라이브러리 없이 정수 연산만으로 빠르고 정확하게 처리할 수 있습니다.
예제 코드
아래 구현 예시를 통해 더 자세히 이해해 보겠습니다.
#include <stdio.h>
#define N 3
struct Triangle{
int a, b, c;
};
int square(struct Triangle t){
int a = t.a, b = t.b, c = t.c;
return (a + b + c)*(a + b - c)*(a - b + c)*(-a + b + c);
}
void solve(struct Triangle* a){
for (int i = 0; i < N; i++)
for (int j = i + 1; j < N; j++)
if (square(a[i]) > square(a[j])){
struct Triangle temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
int main(){
struct Triangle triangles[N] = {{7, 24, 25}, {5, 12, 13}, {3, 4, 5}};
solve(triangles);
for (int i = 0; i < N; i++){
printf("(%d, %d, %d)\n", triangles[i].a, triangles[i].b, triangles[i].c);
}
}입력
{{7, 24, 25}, {5, 12, 13}, {3, 4, 5}}출력
(3, 4, 5) (5, 12, 13) (7, 24, 25)
복잡도 분석
이 프로그램은 버블 정렬 방식을 사용하므로 시간 복잡도는 O(N²)입니다. 삼각형의 개수가 많아지는 경우에는 qsort() 함수와 사용자 정의 비교 함수를 활용하면 O(N log N)으로 성능을 개선할 수 있습니다.