최대공약수, 최소공배수를 JAVA로 구해보자(유클리드 호제법, BigInteger)

들어가기 전에

---

코딩테스트 문제를 풀다보면 종종 최대공약수 혹은 최대공배수를 구할 때가 있다. 가장 대표적인 문제가 아래에 있는 최소공배수문제이다.

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

 

이럴때 어떤 알고리즘을 사용해야하는지, 그리고 간단하게 해결할 수는 없는지 알아보도록 하자.

 

개념을 알아보자

---

약수란??

약수란 어느 한 숫자를 0을 제외한 다른 숫자로 나누었을 때 나머지가 0이 되는 수를 말한다. 예를들어 숫자 4의 약수는 다음과 같다.

 

4 % 1 = 0    => 약수
4 % 2 = 0    => 약수
4 % 3 = 1    => 약수아님
4 % 4 = 0    => 약수

(4의 약수) = {1, 2, 4}

 

공약수란??

공약수란 어느 2개의 숫자의 약수 중 중복되는 수를 말한다. 예를들어 숫자 4와 6의 공약수는 다음과 같다.

 

4의 약수)

4 % 1 = 0    => 약수
4 % 2 = 0    => 약수
4 % 3 = 1    => 약수아님
4 % 4 = 0    => 약수

(4의 약수) = {1, 2, 4}


6의 약수)

6 % 1 = 0    => 약수
6 % 2 = 0    => 약수
6 % 3 = 1    => 약수아님
6 % 4 = 0    => 약수
6 % 5 = 1    => 약수 아님
6 % 6 = 0    => 약수

(6의 약수) = {1, 2, 3, 6}

4와 6의 공약수)

(4의 약수) = {1, 2, 4}
(6의 약수) = {1, 2, 3, 6}
(4와 6의 약수) = {1, 2}

 

최대공약수란??

공약수란 어느 2개의 숫자의 공약수 중 가장 큰 수를 말한다. 예를들어 숫자 4와 6의 최대공약수는 다음과 같다.

 

4의 약수)

4 % 1 = 0    => 약수
4 % 2 = 0    => 약수
4 % 3 = 1    => 약수아님
4 % 4 = 0    => 약수

(4의 약수) = {1, 2, 4}


6의 약수)

6 % 1 = 0    => 약수
6 % 2 = 0    => 약수
6 % 3 = 1    => 약수아님
6 % 4 = 0    => 약수
6 % 5 = 1    => 약수 아님

6 % 6 = 0    => 약수

(6의 약수) = {1, 2, 3, 6}

4와 6의 공약수)

(4의 약수) = {1, 2, 4}
(6의 약수) = {1, 2, 3, 6}
(4와 6의 약수) = {1, 2}
(4와 6의 최대공약수) = 2

 

코드로 구현해보자

이제 최대공약수가 무엇인지 알았으니 이제 코드로 구현해보자. 두수의 최대공약수를 구하기 위해선 다음과 같은 흐름으로 진행된다.

 

1. 숫자 a의 약수를 모두 구한다.
2. 숫자 b의 약수를 모두 구한다.
3. a와 b의 공약수를 모두 구한다.
4. 공약수 중 가장 큰 값을 구한다.

 

위의 흐름을 코드로 표현하면 다음과 같다.

 

import java.util.*;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        int a = 6;
        int b = 4;

        List<Integer> aDivisorList = new ArrayList<>();
        List<Integer> bDivisorList = new ArrayList<>();

        //a의 약수 구하기
        for (int i = 1; i <= a; i++) {
            if (a % i == 0) {
                aDivisorList.add(i);
            }
        }

        //b의 약수 구하기
        for (int i = 1; i <= b; i++) {
            if (b % i == 0) {
                bDivisorList.add(i);
            }
        }

        //공약수 찾기
        List<Integer> commonDivisorList = new ArrayList<>();
        
        for(int aDivisor : aDivisorList){
            if(bDivisorList.contains(aDivisor)){
                commonDivisorList.add(aDivisor);
            }
        }
        
        //가장 큰 값을 찾기 위해 정렬
        Collections.sort(commonDivisorList);

        System.out.println(commonDivisorList.get(0));
    }
}

 

 

여기서 최적화를 진행하면 다음과 같은 부분을 최적화할 수 있다.

• 가장 작은 값 부터 차례대로 약수가 넣어지므로 가장 큰 약수부터 공약수인지 확인하면 그 수보다 큰 공약수는 없으므로 다른 값은 찾을 필요가 없다.
• 공약수 탐색 때 ArrayList대신 HashSet을 사용하면 기존 시간복잡도 O(n)에서 시간복잡도 O(1)로 더 빠르게 탐색할 수 있다.

 

최적화를 반영한 코드는 다음과 같다.

import java.util.*;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        int a = 6;
        int b = 4;

        List<Integer> aDivisorList = new ArrayList<>();
        Set<Integer> bDivisorList = new HashSet<>(); //요소를 빠르게 탐색하기 위해 HashSet으로 구현

        //a의 약수 구하기
        for (int i = 1; i <= a; i++) {
            if (a % i == 0) {
                aDivisorList.add(i);
            }
        }

        //b의 약수 구하기
        for (int i = 1; i <= b; i++) {
            if (b % i == 0) {
                bDivisorList.add(i);
            }
        }

        //최대공약수 찾기
        int gcd = 1;
        
        for(int i=aDivisorList.size()-1;i>=0;i--){
            //가장 큰 a의 약수가 b의 약수인지 확인
            if(bDivisorList.contains(aDivisorList.get(i))){
                gcd = aDivisorList.get(i);
                break;
            }
        }

        System.out.println(gcd);
    }
}

 

그럼 이제 해당 코드의 효율성을 따져보기 위해 시간복잡도를 생각해보자. 시간복잡도를 계산하면 다음과 같다.

 

O(n) = (a의 약수 탐색) + (b의 약수 탐색)  + (최대 공약수 탐색)
       = N + M + N
       ≒ N

 

위의 코드의 시간복잡도는 N으로 대부분의 숫자는 빠르게 최대공약수를 찾을 수 있다. 하지만 N이 매우 커지면 최대공약수를 찾기가 어려워질 것이다. 하지만 이보다 더 빠르게 최대공약수를 찾을 수 있는 방법이 있는데 바로 유클리드 호제법을 사용한 방법이다.

 

유클리드 호제법

---

유클리드 호제법이란??

유클리드 호제법은 두 수의 최대공약수를 구하는 법칙으로 개념은 다음과 같다.

 

두 양의 정수 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가 된다. (출처 나무위키)

 

말이 복잡하게 되어있는데 쉽게 말하면 a와 b의 최대공약수는 a%b와 b의 최대공약수와 같다는 것이다. 위의 개념을 이용하면 (두수의 최대공약수) = gcd(a, b) = gcd(b, r)이므로 최대공약수가 나올때 까지, 즉 r=0일 때 까지 함수를 호출(=재귀)하면 최대공약수를 구할 수 있다!

 

유클리드 호제법을 코드로 구현해보자

유클리드 호제법을 이용해 최대공약수를 구하는 로직을 코드로 구현하면 다음과 같다.

 

private static int getGcdWithEuclidean(int b, int r) {
        //나머지가 0이면 b는 a와 b의 최대공약수가 된다.
        if(r == 0){
            return b;
        }
        //나머지가 0이 아니라면 a와 b의 최대공약수는 b와 a % b의 최대 공약수이므로
        //한번 더 탐색한다.
        return getGcdWithEuclidean(r,b % r);
    }

 

코드도 위의 약수를 탐색하는 방법보다 짧은 것을 한눈에 봐도 알 수 있다!\

위의 방식은 계속 나누기를 하면서 탐색하는 방법이기 때문에 시간복잡도는 최대 루트 N이다. 그러므로 이전에 모든 약수를 탐색하는 방식보다 더 빠른것을 알 수 있다.

 

유클리드 호제법을 더 간단하게 구현해보자(BigInteger)

하지만 이것보다 더 간단한 방법이 있다! 바로 BigInteger의 gcd메소드이다.

 

BigInteger는 int와 long으로 처리하지 못하는 아주 큰 수를 연산할 수 있는 자료형이다. BigInteger에는 재미있으면서 유용한 메소드들이 많은데 그 중 하나가 바로 gcd이다. gcd는 이름만 봐도 알듯이 두 수의 최대공약수를 구하는 메소드이다.

 

BigInteger는 어떻게 최대공약수를 구하는지 gcd의 구현 부분을 확인해보자.

 

public BigInteger gcd(BigInteger val) {
        if (val.signum == 0)
            return this.abs();
        else if (this.signum == 0)
            return val.abs();

        MutableBigInteger a = new MutableBigInteger(this);
        MutableBigInteger b = new MutableBigInteger(val);

        MutableBigInteger result = a.hybridGCD(b);

        return result.toBigInteger(1);
    }

MutableBigInteger hybridGCD(MutableBigInteger b) {
    // Use Euclid's algorithm until the numbers are approximately the
    // same length, then use the binary GCD algorithm to find the GCD.
    MutableBigInteger a = this;
    MutableBigInteger q = new MutableBigInteger();

    while (b.intLen != 0) {
        if (Math.abs(a.intLen - b.intLen) < 2)
            return a.binaryGCD(b);

        MutableBigInteger r = a.divide(b, q);
        a = b;
        b = r;
    }
    return a;
}

 

BigInteger의 gcd과정을 요약하면 다음과 같다.

1. b가 0인지 확인
   1. 0이면 자신(a)의 값을 반환 
2. 자신(a)가 0인지 확인
   1. 0이면 b의 값을 반환
3. hybridGCD를 실행해 유클리드 호제법을 통한 최대공약수 반환

 

BigInteger도 똑같이 유클레드 호제법을 이용해서 최대공약수를 구하는 것을 알 수 있다! 우리는 우리가 굳이 유클리드 호제접을 구현한 재귀 메소드를 사용하지 않아도 BigInteger의 gcd메소드를 사용하면 유사한 시간 효율을 얻을 수 있다.

 

BigInteger를 사용한 최대 공약수를 구하는 코드는 다음과 같다.

 

BigInteger gcd = A.gcd(B);

 

직접 유클리드 호제법을 구현한 것 보다 코드가 깔끔해 진것을 알 수 있다.

 

약수 탐색 vs 유클리드 호제법 vs BigInteger

---

시간을 비교해보자

그럼 이제 얼마나 연산 시간이 차이나는지 3개의 경우를 비교해보자. 다음 코드는 연산시간을 비교하기 위해 3개의 방식으로 구현한 코드이다. a는 2억, b는 1억을 두었고 각각 실행시간을 출력하게 했다.

 

import java.math.BigInteger;
import java.util.*;
import java.util.ArrayList;

public class Main {
    public static void main(String[] args) throws Exception {
        int a = 200000000;
        int b = 100000000;

        System.out.println("약수 탐색으로 최대공약수 구하기");

        long start = System.nanoTime();
        int gcd = getGcd(a,b);
        long end = System.nanoTime();

        System.out.println("최대 공약수 : "+gcd);
        System.out.println("==== 걸린 시간 ====");
        System.out.println((double)(end - start)/1000/1000+"ms\n\n");



        System.out.println("유클리드 호제법으로 최대공약수 구하기");

        start = System.nanoTime();
        gcd = getGcdWithEuclidean(a,b);
        end = System.nanoTime();

        System.out.println("최대 공약수 : "+gcd);
        System.out.println("==== 걸린 시간 ====");
        System.out.println((double)(end - start)/1000/1000+"ms\n\n");



        System.out.println("BigInteger로 최대공약수 구하기");

        BigInteger A = new BigInteger(String.valueOf(a));
        BigInteger B = new BigInteger(String.valueOf(b));

        start = System.nanoTime();
        BigInteger BigGCD = A.gcd(B);
        end = System.nanoTime();

        System.out.println("최대 공약수 : "+BigGCD.intValue());
        System.out.println("==== 걸린 시간 ====");
        System.out.println((double)(end - start)/1000/1000+"ms\n\n");
    }

    private static int getGcdWithEuclidean(int b, int r) {
        if(r == 0){
            return b;
        }
        return getGcdWithEuclidean(r,b % r);
    }

    public static int getGcd(int a, int b){
        List<Integer> aDivisorList = new ArrayList<>();
        Set<Integer> bDivisorList = new HashSet<>(); //요소를 빠르게 탐색하기 위해 HashSet으로 구현

        //a의 약수 구하기
        for (int i = 1; i <= a; i++) {
            if (a % i == 0) {
                aDivisorList.add(i);
            }
        }

        //b의 약수 구하기
        for (int i = 1; i <= b; i++) {
            if (b % i == 0) {
                bDivisorList.add(i);
            }
        }

        //최대공약수 찾기
        int gcd = 1;

        for(int i=aDivisorList.size()-1;i>=0;i--){
            //가장 큰 a의 약수가 b의 약수인지 확인
            if(bDivisorList.contains(aDivisorList.get(i))){
                gcd = aDivisorList.get(i);
                break;
            }
        }

        return gcd;
    }
}

 

실행결과

 

실행 결과 약수 탐색으로 최대공약수를 구했을 땐 1079ms가 걸렸지만 유클리드 호제법을 구현한 방법과 BIgInteger 2가지 방법은 0ms가 걸렸다. BigInteger 방식이 실행되는 조건과 메소드가 직접 구현한 방법보다 많기 때문에 시간이 약 180배 더 걸렸지만 그래도 알고리즘 문제 대부분의 제한 시간인 1초 이내로 실행 된것을 알 수 있다. 

 

즉 유클리드 호제법을 사용한 것이 약수 탐색을 통한 방법보다 더 빠르다는 것을 알 수 있었다!

 

최소공배수는??

---

최대 공약수를 구할 줄 안다면 최소 공배수를 구하는 방법은 아주 간단하다. 왜냐하면 최대 공약수를 이용해서 최소 공배수를 구하는 방법이 있기 때문이다! 그 방법은 다음과 같다.

 

(최소 공배수) = a * b / (a와 b의 최대공약수)

 

그러므로 최소 공배수를 구할 땐 단순 곱하기와 나누기인 시간복잡도 O(1)의 사칙연산만이 소요되므로 최대공약수에서 효율을 많이 잡았다면 최소 공배수에서는 단순히 사칙연산만 하면 된다.

 

연관 문제

---

한번 위의 내용을 이용해서 최대공약수와 최소공배수 문제를 풀어보자. 대부분 난이도가 낮은 문제라서 위의 방법을 알고 있다면 쉽게 풀 수 있을 것이다.

 

1. 최소공배수 (실버 5)

https://www.acmicpc.net/problem/13241

13241번: 최소공배수

 

2. 최대공약수 (실버 1)

https://www.acmicpc.net/problem/1850

1850번: 최대공약수

 

3. 최대공약수와 최소 공배수 (브론즈 1)

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

마무리

---

지금까지 최대 공약수, 최소 공배수를 구할 때 어떤 것이 가장 좋은 방법인지 알아보았다. 재귀를 통한 직접 구현하는 것이 시간효율이 더 좋으나 코드만 봤을땐 BigInteger가 깔끔한 것을 알 수 있었다. 시간적 효율과 코드의 깔끔함 중 어떤 것이 자신이 더 중요하게 생각하는지 확인해보고 상황에 맞게 사용하는 것이 좋겠다.

 

오늘 게시물을 요약하면서 마무리 짓는다.

최대공약수, 최대공배수 를 구할때 좋은 방법은??

유클리드 호제법 직접 구현 > BigInteger >>>> 약수 탐색