[BOJ] 최대공약수와 최소공배수(2609) - Java

백준 2609번을 풀다가 최대공약수를 구하는 새로운 알고리즘에 대해 공부하게 되었다. 명시적으로 기술된 가장 오래된 최대공약수 구하기 알고리즘이라고 한다.

최대공약수 풀이

유클리드 호제법(알고리즘)

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. - 출처 위키백과

예시

1071과 1029의 최대공약수를 구하면,

1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
42는 21로 나누어떨어진다.
따라서, 최대공약수는 21이다.

적용 - java

 int getGcf(int n1, int n2) {
        if (n1 < n2) {
            int tmp = n1;
            n1 = n2;
            n2 = tmp;
        }
        int tmp;
        while((tmp = n1%n2) != 0) {
            n1 = n2;
            n2 = tmp;
        }
        return n2;
    }

tmp는 n1를 n2로 나눈 나머지를 저장하는 변수이다. tmp가 0이 될 때 까지 반복하여 나눈다.
나머지가 0이 되게 한 몫을 반환하면 그것이 최대공약수이다.

최소공배수 풀이

최소공배수는 두 수를 곱하여 최대공약수로 나누면 된다.

 int getLcm(int n1, int n2) {
        int gcf = getGcf(n1, n2);
        return n1*n2/gcf;
    }

두 수 사이의 합을 구하는 등 수학적으로 접근하는 공부를 많이 해봐야겠다.