C언어로 N개의 분수 곱을 기약분수 형태로 구하는 방법

N개의 분수가 각각 분자(num)와 분모(den)로 주어졌을 때, 이 분수들의 곱을 구하고 그 결과를 기약분수(약분된 형태)로 출력하는 것이 이번 문제의 목표입니다.

예를 들어 아래 그림과 같이 "4/5"와 "3/4"라는 두 분수가 있을 때, 첫 번째 분수의 분자와 두 번째 분수의 분자를 곱하고, 첫 번째 분수의 분모와 두 번째 분수의 분모를 곱하면 결과는 "12/20"이 됩니다. 이 값은 약분이 가능하므로 최종 출력은 "3/5"가 되어야 합니다. 이처럼 주어진 문제를 해결하는 프로그램을 작성해야 합니다.

입력 및 출력 예시

예시 1

입력

fraction f[3] = {{1,2},
{2,1},
{5,6}}

출력

5/6

설명 − 1/2 × 2/1 × 5/6 = 10/12이며, 이를 약분하면 5/6이 됩니다.

예시 2

입력

fraction f[2] = {{2, 3},
{1,4}}

출력

1/6

설명 − 2/3 × 1/4 = 2/12이며, 이를 약분하면 1/6이 됩니다.

문제 해결 접근 방법

이 문제는 다음과 같은 방식으로 해결할 수 있습니다.

먼저 모든 분자를 서로 곱한 값과 모든 분모를 서로 곱한 값을 각각 변수 prod_num(최종 분자)과 prod_den(최종 분모)에 저장합니다. 그다음 기약분수 형태를 만들기 위해 prod_num과 prod_den의 최대공약수(GCD)를 구하고, 두 값을 각각 최대공약수로 나누어 주면 됩니다.

알고리즘

Start
Declare a struct fraction with following elements
    1. num, 2. den
In function int GCD(int a, int b)
    Step 1→ If a == 0 then,
        Return b
    Step 2→ Return GCD(b % a, a)
In function int product(int n, fraction f[])
    Step 1→ Initialize prod_num = 1 prod_den = 1
    Step 2→ Loop For i = 0; i < n; i++
        prod_num = prod_num * f[i].num
        prod_den = prod_den * f[i].den
    Step 3→ Declare and initialize gcd = GCD(prod_num, prod_den)
    Step 4→ prod_num = prod_num / gcd
    Step 5→ prod_den = prod_den / gcd
    Step 6→ Print prod_num, prod_den
In Function int main()
    Step 1→ Declare struct fraction f[3] = {
        {1,2},
        {2,1},
        {5,6}}
    Step 2→ Declare and initialization n as sizeof(f)/sizeof(f[0])
    Step 3→ product(n, f)
Stop

C 언어 구현 예제

#include <stdio.h>
struct fraction{
    int num;
    int den;
};
// a와 b의 최대공약수(GCD)를 반환하는 함수
int GCD(int a, int b){
    if (a == 0)
        return b;
    return GCD(b % a, a);
}
// 결과를 계산하여 출력하는 함수
int product(int n, fraction f[]){
    int prod_num = 1, prod_den = 1;
    // 모든 분자와 분모의 곱을 구함
    for (int i = 0; i < n; i++) {
        prod_num *= f[i].num;
        prod_den *= f[i].den;
    }
    // 새로운 분자와 분모의 최대공약수를 구함
    int gcd = GCD(prod_num, prod_den);
    // 기약분수 형태로 만듦
    prod_num /= gcd;
    prod_den /= gcd;
    printf("%d/%d\n", prod_num, prod_den);
    return 0;
}
int main(){
    struct fraction f[3] = {
        {1,2},
        {2,1},
        {5,6}};
    int n = sizeof(f)/sizeof(f[0]);
    product(n, f);
    return 0;
}

실행 결과

위 코드를 실행하면 다음과 같은 출력이 생성됩니다.

5/6

마무리

이 알고리즘은 유클리드 호제법을 활용해 최대공약수를 재귀적으로 구하기 때문에 효율적입니다. 시간 복잡도는 분수의 개수를 N이라 할 때 O(N + log(max(prod_num, prod_den)))으로, 분수들의 곱을 한 번씩만 순회하면 되므로 매우 빠르게 동작합니다. 다만 분자와 분모의 곱이 커질 경우 정수 오버플로우에 유의해야 하며, 필요하다면 long long 타입 사용을 고려할 수 있습니다.