[TIL] 최대공약수(GCD)와 최소공배수(LCM) 효율적으로 구하기 (JAVA)

오늘의 데일리 루틴 문제는 '최대공약수와 최소공배수'이다.

https://school.programmers.co.kr/learn/courses/30/lessons/12940

프로그래머스

 

내가 아는 최대공약수, 최소공배수 구하는 방식을 적용해서 풀어보았는데, 

아무리 생각해도 좀 유치한가 싶기도하고, 분명 이것보다 더 효율적인 방법이 있을텐데..하는 찝찝한 마음을 떨쳐버릴 수가 없어서 정보를 찾아보았다.

 

---

아래는 내가 초기에 작성한 코드이다.

초등학생이 최소공배수, 최대공약수 구하듯이 한땀한땀 정성스럽게 비교해가며 구한다.

최소공배수는 브루트 포스를 사용했는데, 수를 하나씩 넣어가면서 답을 찾는다.

숫자가 커질 수록 효율성이 떨어질 수밖에 없다.

import java.util.*;
class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int minNum=Math.min(n,m); //n,m 중 더 작은 수
        int maxNum=Math.max(n,m); //n,m 중 더 큰 수
        
        //최대공약수 구하기
        for(int i=1; i<=minNum; i++){
            if(n%i==0 && m%i==0){
                answer[0]=i;
            }
        }
        
        int cnt=2;
        int maxNumTimes=maxNum;
        //최소공배수 구하기
        while(true){
            if(maxNumTimes%minNum==0){
                answer[1]=maxNumTimes;
                break;
            }else{
             maxNumTimes=maxNum*cnt++;  
            }
        }
        
        return answer;
    }
}

 

 

 

🟡 최대공약수(GCD, Greatest Common Divisor)구하기 - 유클리드 호제법(Euclidean algorithm)

최대공약수를 구하는 알고리즘은 기원전 300년 전에 유클리드에 의해 개발되었다.

 

🔹유클리드 호제법의 원리

유클리의 호제법의 핵심 원리는 다음과 같다.

1. a와 b의 최대공약수는 b와 a mod  b의 최대공약수와 같다.  (a, b는 정수, a mod b는 a를 b로 나눈 후의 나머지 값)

         GCD(a, b) = GCD(b, a mod b)

2. b와 a mod  b의 최대공약수를 구하는 과정을 반복하여 a mod  b = 0이 될 때의 b값이 최대공약수이다.

 

 

🔹알고리즘 설명

1. 두 정수 중에서 큰 수를 x, 작은 수를 y라고 한다.
   (※ 두 개의 정수 중에서 큰 수가 반드시 변수 x에 저장되어야한다.)
2. 만약  y가 0이면 최대 공약수는 x이다. (예외처리 및 이후 알고리즘 종료 지점)
3. (임시 변수)tmp = x mod y;
4. tmp < y 이므로, 이제 더 큰 수인 y를 변수 x에 넣고, 더 작은 수인 tmp를 변수 y에 넣는다.
   x = y;   
   y = tmp;
5. 단계 2로 되돌아간다.

import java.util.*;
class Solution {
    public int[] solution(int n, int m) {
        
        int minNum=Math.min(n,m); //n,m 중 더 작은 수
        int maxNum=Math.max(n,m); //n,m 중 더 큰 수
        
        //최대공약수 구하기
        while(true){
            if(minNum==0){ //단계 2
                answer[0]=maxNum;
                break;
            }
            int tmp=maxNum%minNum;
            maxNum=minNum;
            minNum=tmp;
        }    
   }
}

 

 

 

🟡 최소공배수(LCM, Least Common Multiple)구하기

두 정수 a, b의 최대공배수는 a⨉b의 값을 a, b의 최소공배수로 나눈 값과 같다.

LCM(a, b) = (a⨉b) / GCD(a, b)

 

🔹최소공배수 핵심 원리

1. 정수 a⨉b의 값은 a, b의 공배수 중 하나이다.
2. 최대공약수는 a, b를 동시에 나눌 수 있는 가장 큰 수이다.
3. 따라서 a⨉b를 최대공약수로 나누면, a, b의 공통된 배수 중 가장 작은 수인 최소공배수를 구할 수 있다.

유클리드 호제법을 사용하면 최소 공배수를 더 빠르게 구할 수 있다.

import java.util.*;
class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
        int minNum=Math.min(n,m); //n,m 중 더 작은 수
        int maxNum=Math.max(n,m); //n,m 중 더 큰 수
        
        //유클리드 호제법을 활용한 최소공배수 구하기
        while(true){
            if(minNum==0){
                answer[0]=maxNum; //최대공약수(GCD)
                answer[1]=n*m/maxNum; //최소공배수(LCM)
                break;
            }
            int tmp=maxNum%minNum;
            maxNum=minNum;
            minNum=tmp;
        }
        
        return answer;
    }
}