유클리드 호제법으로 최대공약수 구하기

유클리드 호제법으로 최대공약수 구하기

---

기존의 최대 공약수를 구하는 방법

---

public int getGreatestCommonDivisor(int num1, int num2) {
    int little = num1 < num2 ? num1 : num2;
    int gcd = 0;
    for(int i = 1; i <= little; i++) {
        if(num1 % i == 0 && num2 % i == 0) gcd = i;
    }
    return gcd;
}

 

이렇게 반복문을 활용해서 일일히 공약수의 자격이 있는 수를 판별하고, 그 중 가장 큰 수를 반환해서 푸는 것이 일반적인 접근 방법입니다.

물론 이 코드로도 대부분의 코드는 통과하지만, 새로운 알고리즘을 발견해 소개해보고자 글을 작성하게 되었습니다.

 

유클리드 호제법

---

유클리드 호제법(Euclidean algorithm)은 두 양의 정수 혹은 다항식에 대한 최대 공약수를 구하는 방법입니다. 인류 최초의 알고리즘으로도 유명한데요, 그 내용은 다음과 같습니다.

두 양의 정수 a, b (a > b)에 대하여 a = bq + r (0 ≤ r < b) 이라 하면, a, b의 최대공약수는 b, r의 최대공약수와 같다. 즉, gcd(a, b) = gcd(b, r) r = 0이라면 a,b의 최대공약수는 b가 된다.

 

잘 이해가 안되시죠?

 

정리해보면 다음과 같습니다.

1. 두수 a와 b(단, a > b)에 대하여, a를 b로 나눈 나머지를 r이라고 하겠습니다.
2. a = bq + r 로 나타낼 수 있습니다. (여기서 q는 몫을 나타냅니다)
3. a와 b의 공약수 d가 있다고 가정했을 때, d는 a = bq + r의 오른쪽 항인 bq와 r의 약수여야 합니다. (나머지가 없도록)
4. 반대로, d가 b와 r의 공약수라면, d는 a = bq+ r을 나머지 없이 나눌 수 있어야 합니다.
5. 따라서 a와 b의 모든 공약수는 b와 r의 공약수이며, 그 반대도 성립하게 됩니다.

위 성질을 이용해서 계속해서 반복하면 최대공약수를 구할 수 있습니다.

• 이 과정을 반복해서 b를 r로 나누고 그 다음 나머지로 나누는 과정이 연속됩니다.
• 나머지가 0이 될 때 까지 계속 진행된다면, 마지막으로 나누는 수가 최대공약수 입니다.

자바 코드로 한 번 구현해보겠습니다.

public int euclidean(int num1, int num2) {
    while (num2 != 0) {
        int r = num1 % num2; // num1을 num2로 나눈 나머지
        num1 = num2;         // 다음 계산을 위해 b를 a에 할당
        num2 = r;            // 다음 계산을 위해 나머지를 b에 할당
    }
    return num1; // 나머지가 0이 되었을 때 num1이 최대공약수!
}

 

위 성질을 이용해서 최대 공약수를 구하는 코드입니다.

재귀를 이용해서 더 간단하게 표현할 수도 있습니다.

public int euclidean(int num1, int num2) {
    if (num2 == 0) return num1;
    return euclidean(num2, num1 % num2);
}

 

다만 주의해야할 것은 유클리드 호제법이 항상 최적인 알고리즘은 아니라는 점입니다.

엄청나게 큰 수에 대해서는 오히려 시간복잡도가 증가하게 되고 다른 준선형적 알고리즘을 채택해야한다고 합니다.

하지만 기존의 방법에 비해서는 훨씬 효율적으로 느껴지기는 합니다.

 

분수를 다루는 코드를 작성하다가 이런 방법을 발견했는데요~! 다음에도 재미있는 알고리즘을 발견하면 소개하도록 하겠습니다.