TIL(20240612) [유클리드호제법]

---

📌 코딩테스트1️⃣ : 최대공약수와 최소공배수

🔒 문제 : 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

🚫 조건 : 두 수는 1이상 1000000이하의 자연수입니다.

🔓 문제풀이

class Solution {
    public int[] solution(int n, int m) {
        int[] answer = {};

        // a > b라는 가정
        int a = Math.max(n,m);
        int b = Math.min(n,m);
        
        while(b!=0){ // 최대 공약수 
            int r=a%b;
            a=b;
            b=r;
        }
        
        answer = new int[2];
        answer[0] = a;
        answer[1] = n * m / a; // 최대 공배수
        
        return answer;
    }
}

💡 유클리드 호제법

최대 공약수 gcd(a,b) 구하기

• 임의의 두 자연수 a, b(a > b)가 주어지고 a를 b로 나눈 나머지를 r(r = a % b)로 이라고 하자.
• a = b가되고 b = r이 되는데, 이때 b가 0이 될 때의 a가 최대공약수이다.

최대 공배수 구하기

• 최소 공배수 * 최대 공약수 = a * b 임을 이용
• 따라서 최소 공배수 = a * b / 최대 공약수

유클리드호제법