유클리드 호제법

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

일반적으로 두 수 사이의 공약수를 구할때 소인수 분해를 하고 소인수들의 곱으로 최대 공약수를 구할 수 있었다.

하지만, 이것을 코드로 구현한다면 효율적이지 않을 것이다.

만약 주어진 수의 크기가 크다면 시간 복잡도는 계속 증가할 것이다.

유클리드 호제법 알고리즘을 사용한다면 이 문제를 쉽게 해결할 수 있다.

유클리드 호제법의 기본개념은 두 개의 수 A,B에 대해 (A>B)라면 A를 B로 나눈 나머지 C라고 가정한다.

이때, A와 B의 최대 공약수는 B와 C의 최대 공약수와 같다. 이러한 알고리즘 특징을 이용해 C가 0이 될 때의 나누는 수가 최대 공약수가 된다.

public class programmers_level1_27 {
    static int educ(int a, int b){
        int r = a % b;         //큰 숫자를 작은 수로 나눈 나머지 계산
        if(r == 0) return b;   //나머지가 0이면 작은숫자가 최대공약수 이므로 리턴
        else return educ(b, r);//나머지가 0이 아니면 재귀로 리턴
    }

    public static int[] solution(int n, int m) {
        int[] answer = new int[2];
        int r = educ(Math.max(n,m), Math.min(n,m));

        answer[0] = r;
        n = n/r;
        m = m/r;
        answer[1] = n * m * r;   // 두 수의 최소공배수 = 두 수의 최대 공약수 * 위에서 구한 몫
        return answer;
    }
}