[Java] 백준1934 최대공약수와 최소공배수 구하기 : 유클리드 호제법

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

두 개의 자연수 또는 정수의 최대공약수 (GCD : Greatest Common Divisor) 을 구하는 가장 빠르고 효율적인 알고리즘이다. 호제법은 '서로 나누는 방법' 이라는 뜻이다.

 

두 수 A와 B의 최대공약수는 B와 A를 B로 나눈 나머지의 최대공약수와 같다. 

 

예를 들어 보자. 1112 와 695의 최대공약수를 구할 때, 

1. 큰 수를 작은 수로 나눈다. (반복)
   1. 1112 % 695 = 417 (나머지)
   2. 695 % 417 = 278 (나머지)
   3. 417 % 278 = 139 (나머지)
   4. 278 % 139 = 0 (나머지)

나머지가 0이 나온 시점에 나누는 수로 사용된 139가 1112와 695의 최대공약수이다.

 

 

위 내용을 코드로 구현하면 아래와 같다.

 

public static int getGcd(int num1, int num2) {
    while (num2 != 0) {
        int temp = num1 % num2; // 나머지 계산
        num1 = num2;            // 나누는 수를 피제수 자리로
        num2 = temp;            // 나머지를 나누는 수 자리로
    }
    return num1; // num2가 0이 될 때의 num1 값이 최대공약수
}

 

 

num2 (나누는 수) 가 0이 될때까지 루프를 반복한다.

 

 

나머지 연산의 특성

이 때, num1 이 num2 보다 작아도 문제가 없다. 작은 수를 큰 수로 나누면, 나머지는 자기 자신 (작은 수) 가 된다.

 

num1이 12 이고, num2 가 18일 때를 예로 들어보자.

1. 12 % 18 = 12 (나머지)
2. 18 % 12 = 6 (나머지)
3.  ... (생략) ...

2번까지 과정에서, 나누기 과정 한 번만에 큰 수가 앞으로 오게 된다.

 

 

최대공약수를 이용한 최소 공배수 구하기

최대공약수를 이용하여, 최소 공배수를 쉽게 구할 수 있다.

(A x B) / (A와 B의 최대공약수)

두 수를 곱한 값을 최대공약수로 나누면 최소공배수가 된다.

 

 

끝 ~!