C++에서 배열의 최대 유리수(분수) 구하기

이 문제에서는 유리수가 한 줄에 하나씩 담겨 있는 2차원 배열이 주어집니다. 우리의 과제는 C++를 사용하여 이 배열에서 최대 유리수(또는 분수)를 계산하는 프로그램을 작성하는 것입니다.

문제 설명

주어진 2차원 배열은 [n][2] 형태입니다. 각 행에는 두 개의 정수 값이 있으며, 이는 유리수 식 a/b에서 분자 a와 분모 b를 나타냅니다. 우리는 이 모든 유리수 중에서 가장 큰 값을 찾아야 합니다.

예제로 문제 이해하기

입력

rat[][] = {
    {3, 2},
    {5, 7},
    {1, 9},
    {11, 4}
}

출력

11 4

설명

3/2 , 5/7 , 1/9 , 11/4

위 네 개의 유리수 중 최댓값은 11/4입니다.

해결 접근 방식

이 문제를 풀려면 각 숫자의 실제 값을 계산한 뒤 서로 비교해야 합니다. 하지만 이 방법에는 오류 가능성이 있습니다. 예를 들어 float 자료형을 사용하면 정밀도 차이가 미세한 경우 두 유리수를 구분할 수 없습니다. 즉, 34.12313431123과 34.12313431124 같은 값은 float로는 정확하게 비교되지 않습니다.

따라서 다른 방법으로 값을 비교하는 것이 좋습니다. 바로 모든 분모의 LCM(최소공배수)을 구하고, 그에 맞춰 분자들을 변환하는 방식입니다. 이렇게 하면 분자들만 비교하여 최댓값을 쉽게 찾을 수 있습니다.

구현 예제

#include <bits/stdc++.h>
using namespace std;
const int n = 4;
int findMaxRatNum(int ratNum[n][2]){
    int numArray[n];
    int LCM = 1;
    int mavVal = 0, index = 0;
    for (int i = 0; i < n; i++)
        LCM = (LCM * ratNum[i][1]) / __gcd(LCM, ratNum[i][1]);
    for (int i = 0; i < n; i++) {
        numArray[i] = (ratNum[i][0]) * (LCM / ratNum[i][1]);
        if (mavVal < numArray[i]) {
            mavVal = numArray[i];
            index = i;
        }
    }
    return index;
}
int main(){
    int ratNum[n][2] = {{3, 2},{5, 7},{1, 9},{11, 4}};
    int i = findMaxRatNum(ratNum);
    cout<<"The maximum rational number from an array is "<<ratNum[i][0]<<"/"<<ratNum[i][1];
}

출력 결과

The maximum rational number from an array is 11/4

코드 동작 원리

이 프로그램의 핵심 로직은 다음과 같습니다.

먼저, __gcd() 함수를 활용해 모든 분모의 최소공배수(LCM)를 계산합니다. 그다음, 각 분수의 분모가 LCM이 되도록 분자를 비율에 맞게 곱해 변환합니다. 변환된 분자들은 모두 동일한 분모를 공유하므로 단순히 분자 값만 비교하면 됩니다. 가장 큰 분자를 가진 인덱스를 반환하면, 해당 인덱스의 원래 분수가 곧 최대 유리수입니다.

이 방식은 부동소수점 연산 없이 정수 연산만으로 정확한 비교가 가능하기 때문에, 정밀도 오류 없이 안정적으로 최대 유리수를 찾을 수 있다는 장점이 있습니다.