[알고리즘] 유클리드 호제법 - 최소공배수, 최대공약수 구하기

유클리드 호제법

유클리드 호제법이란, 두 개의 수가 주어졌을 때, 최대공약수를 구하는 알고리즘입니다.

최소공배수는 주어진 두 개의 수를 곱한 값을, 그 두 개의 수의 최대공약수로 나누어 구할 수 있습니다.

최대공약수 : GCD(greatest common divisor)
최소공배수 : LCM(largest common multiple)

 

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

1980과 168의 최소공배수를 유클리드 호제법을 이용하면 다음과 같은 과정을 거치게 됩니다. 

1. 1980을 168로 나눕니다.

2. 1980을 168로 나눈 나머지 132와 168을 다시 나눕니다.

3. 168을 132로 나눈 나머지 36과 132를 다시 나눕니다.

4. 나머지가 0이 될때까지 반복합니다.

5. 나머지가 0이 되었을 시 나누는 값이 두 수의 최소공배수 ( GCD ) 가 됩니다.

 

---

Java - 최소 공배수와 최대 공약수 구하기

 

위 유클리드호제법을 이용해 최대공약수를 구하고 최소공배수를 구하는 코드는 다음과 같습니다.

( 프로그래머스 Lv1 - 최대공약수와 최소공배수 문제입니다 )

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int bigNum = Math.max(n, m);
        int smallNum = Math.min(n, m);
        
        answer[0] = gcp(bigNum, smallNum); // 최대공약수
        answer[1] = bigNum*smallNum / answer[0]; // 최소공배수
        
        return answer;
    }
    
    // 유클리드 호재법
    private static int gcd(int a, int b) {
        if (a%b == 0) {
            return b;
        }
        return gcp(b, a%b);
    }
}

주어지는 매개변수 값이 n : 3, m : 12라고 가정하고 설명하겠습니다.

 

1. bigNum에 n과 m 중 큰 값 12를 대입합니다.

2. smallNum에 n과 m 중 작은 값 3을 대입합니다.

3. answer[0] 번째에 gcp() 메서드에 12와 3을 매개변수로 주어 메서드를 실행하여 대입합니다.

4. gcp() 메서드는 두개의 정수를 매개변수로 받아 최대공약수를 구합니다.

5. gcp() 메서드는 12를 3로 나누어 나머지가 0이 된다면 3을 반환하고 아니라면, 첫 번째 인자를 3로 바꾸고 두 번째 인자를 12%3로 바꾸어 재귀호출합니다.

6. 12를 3으로 나눈 나머지는 0 이기 때문에 3을 반환하고 이 값은 최대공약수가 됩니다.

7. answer[1]번째에 두 수 12와 3을 곱한 값을 최대공약수로 나누어 최소공배수를 구해 대입합니다.

8. answer = [3, 12]

 

---

참고자료
https://www.youtube.com/watch?v=TxdljAFjTNw