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

출처:프로그래머스(https://school.programmers.co.kr/learn/courses/30/lessons/12940)

class Solution {
    public int[] solution(int n, int m) {
        int gcd = gcd(n, m);
        int lcs = lcs(n, m);
        int[] answer = {gcd, lcs};
        return answer;
    }
    public int gcd(int val1, int val2) {
        int i = val1;
        while(i > 1) {
            if(val2 % i == 0 && val1 % i == 0) {
                break;
            }
            i--;
        }
        return i;
    }
    public int lcs(int val1, int val2) {
        int i = val2;
        while(i < val1 * val2) {
            if(i % val1 == 0 && i % val2 == 0) {
                break;
            }
            i++;
        }
        return i;
    }
}

두 숫자의 최대공약수를 구할 때 가장 큰 값이 나와도 두 수중 작은수인 n보다는 작을거라고 판단하고 n부터 시작해서 1씩 내리면서 두 수가 i로 나누어 떨어지는지 확인하는 로직이다.

 

두 숫자의 최소공배수를 구할 때 두 숫자중 큰 수인 m보다는 크고 두 수의 곱보다는 작을 거라고 판단하고 m부터 시작해서 n*m이 될 때까지 1씩 증가하면서 i가 n과 m이 나누어 떨어지는지 확인하는 로직이다.

 

위의 해답은 일종의 꼼수를 활용한 알고리즘으로 정석으로 짜면 유클리드 호제법을 활용해서 구현해야 한다.

class Solution {
    public int[] solution(int n, int m) {
        int gcd = gcd(n, m);
        int lcs = lcs(n, m);
        int[] answer = {gcd, lcs};
        return answer;
    }
    public int gcd(int val1, int val2) {
        if (val2 == 0) {
            return val1;
        }
        return gcd(val2, val1 % val2);
    }
    public int lcs(int val1, int val2) {
        int gcd = gcd(val1, val2);
        return Math.abs(val1*val2) / gcd;
    }
}

 

유클리드 호제법:
두 양의 정수 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가 된다.

lcs(n,m)= |ab| / gcd(a,b)이다.