유클리드 호제법

유클리드 호제법이란?

유클리드 호제법은 수학에서 두 수의 최대공약수를 구하는 가장 효율적인 알고리즘 중 하나입니다.

이번 글에서는 이를 활용해 분수 계산에서 기약분수로 변환하는 과정을 설명하겠습니다.

---

유클리드 호제법을 이용한 최대공약수 구하기

유클리드 호제법은 큰 수와 작은 수를 나눈 나머지를 반복적으로 계산하며, 나머지가 0이 될 때 작은 수가 최대공약수가 됩니다.

간단히 다음과 같은 규칙을 따릅니다.

1. 두 수 중 큰 수를 a, 작은 수를 b로 정합니다.
2. a % b가 0이 될 때까지, a와 b를 재귀적으로 교환하며 계산합니다.
3. 최종적으로 나머지가 0이 되는 순간, b가 최대공약수(GCD)입니다.

다음은 자바로 구현한 유클리드 호제법의 코드입니다.

int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

---

분수 계산에서 유클리드 호제법 적용하기

문제 상황

두 분수 5/6과 7/9의 합을 계산한다고 가정해봅시다. 이를 분수의 덧셈 공식에 따라 계산하면:

• 분자: (5 * 9) + (7 * 6) = 45 + 42 = 87
• 분모: 6 * 9 = 54

결과는 87/54가 됩니다. 그러나, 분수의 계산은 종종 "기약분수" 형태로 나타내야 하는데, 이를 위해 분자와 분모의 최대공약수로 나눠야 합니다.

---

코드 구현

유클리드 호제법을 이용해 위의 분수를 기약분수로 변환하는 코드는 다음과 같습니다.

class FractionCalculator {
    public int[] calculateFraction(int numer1, int denom1, int numer2, int denom2) {
        int[] result = new int[2];

        // 분자와 분모 계산
        int numer = (numer1 * denom2) + (numer2 * denom1);
        int denom = denom1 * denom2;

        // 최대공약수 구하기
        int gcdValue = gcd(numer, denom);

        // 기약분수로 변환
        result[0] = numer / gcdValue;
        result[1] = denom / gcdValue;

        return result;
    }

    private int gcd(int num1, int num2) {
        if (num2 == 0) return num1;
        return gcd(num2, num1 % num2);
    }
}

---

실행 예시

위 코드를 실행해 보면, 다음과 같은 결과를 얻을 수 있습니다.

public class Main {
    public static void main(String[] args) {
        FractionCalculator calculator = new FractionCalculator();

        // 두 분수: 5/6 + 7/9
        int[] result = calculator.calculateFraction(5, 6, 7, 9);

        System.out.println("결과: " + result[0] + "/" + result[1]);
    }
}

출력 결과:

결과: 29/18