[프로그래머스|최대공약수와 최소공배수] 유클리드 호제법

문제

---

본인 풀이

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        answer[0] = getGCD(n,m);
        answer[1] = (n * m) / (answer[0]);
        
        return answer;
    }
    
    public static int getGCD(int n, int m){
        if(n % m == 0){
            return m;
        }
        return getGCD(m,(n%m));
    }
}

---

풀이법

 

 

유클리드 호제법

2개 수의 최대 공약수를 구하는 알고리즘

자연수 a, b에 대해서 a%b의 결과를 r이라고 한다면 a, b의 최대공약수와 b, r의 최대공약수는 같다.

이 성질을 이용하여 a, b를 나눈 나머지 r을 구하고 b, r을 나눈 나머지 r1을 구한다.

나머지 결과가 0이 나올 때 나눈 수가 a, b의 최대공약수가 된다.

이를 이용한 최대 공약수(GCD)를 통해 최소 공배수(LCM)를 구할 수 있다. 

 

최소공배수 = (a*b) / gcd

 

 

Q> 만약 2개의 수가 아닌 여러 개의 수(ex. A, B, C)의 최대 공약수를 구해야 한다면?

1) A, B의 최소 공배수를 구한다.

2) 1에서 구한 최소 공배수와 C의 최소 공배수를 구한다.

 

---

참고: https://programmer-chocho.tistory.com/9

[JAVA] 최대 공약수(GCD), 최소 공배수(LCM) 구하기

https://velog.io/@deannn/Java-int%ED%98%95-ArrayList-%EB%B0%B0%EC%97%B4-%EB%B3%80%ED%99%98

[Java] Integer ArrayList을 int 배열로 변환 방법