[알고리즘]유클리드 호제법을 이용한 최대공약수와 최소공배수 구하기_java

기본적인 알고리즘 문제 중에 최대공약수와 최소공배수를 구하는 코드를 준비해보았습니다!

 

이번 포스팅에서 중요한 건 최대공약수를 유클리드 호제법으로 구하는 것입니다.

유클리드 호제법을 설명하기 앞서,

숫자1은 숫자2보다 커야한다는 조건이 있다는 것을 염두하시고 봐주시면 될 것 같습니다!

 

[유클리드 호제법으로 짠 코드]

1. 숫자1 / 숫자2를 하여 나눈 나머지를 remain에 저장한다.

2. 숫자1에 숫자2를 저장하고 나머지 remaind을 숫자2에 저장한다.

3. 계속 1번과 2번을 반복하여 remain값이 0이 될 때, 숫자1이 최대 공약수이다.

---

//최대 공약수와 최소 공배수 구하기
public class Main {
    public static void main(String[] args) {
        int num1 = 18;
        int num2 = 12;

        /*최대 공약수 호출*/
        int gdc = gdc(num1,num2);

        /*최소 공배수 계산(두 수의 곱 / 최대공약수)*/
        int lcm = (num1 * num2) / gdc;

        System.out.println("최대 공약수: "+gdc);
        System.out.println("최소 공배수: "+lcm);

    }
    /* 최대 공약수 - 유클리드 호제법*/
    public static int gdc(int num1, int num2){
        if(num1 < num2){
            int tmp = num1;
            num1 = num2;
            num2 = num1;
        }
        while(num2 != 0){
            int remain = num1 % num2;
            num1 = num2;
            num2 = remain;
        }
        return num1;
    }
}

 

최대 공약수를 구했으면, 최대 공배수는 간단하게 구할 수 있습니다.

(숫자1 * 숫자2) / 최대공약수 이기 때문이죠!

 

기본적인 알고리즘을 가볍게 짤 수 있어야지 난이도 높은 테스트를 푸는데 힘을 빼지 않는 것 같습니다ㅎㅎ 

역시 기본기가 중요하다!!!