자바 - 최대공약수를 가장 빠르게 찾는 방법: 유클리드 호제법 알고리즘

백준 문제에서 최대공약수를 찾는 문제가 나왔어요. 당연히 무식한 저는 그냥 두 수의 모든 배수를 찾아서 그 중에서 가장 큰 수를 검색하는 방식으로 했는데 시간초과에 걸리는 것이 아니겠어요? 그래서 그럼 어떤 방법으로 최대공약수를 찾을 수 있을까 찾아봤더니 유클리드 호제법이라는 아주 유명한 수학공식이 있더군요.

 

1. 무식한 방법

public static int maximumCommonMultiple(Integer a, Integer b) {

        Map<Integer, Integer> aCommonMultiple = new HashMap<>();
        List<Integer> bCommonMultiple = new ArrayList<>();

        int resultCommonMultiple = 0;

        for (int i = 1; i <= a; i++) {

            if ((a % i) == 0) {
                aCommonMultiple.put(i, 0);
            }
        }

        for (int i = 1; i <= b; i++) {
            if((b % i) == 0) {
                bCommonMultiple.add(i);
            }
        }

        for (int i = bCommonMultiple.size() - 1; i >= 0; i--) {

            if (aCommonMultiple.containsKey(bCommonMultiple.get(i))) {
                resultCommonMultiple = bCommonMultiple.get(i);
                return resultCommonMultiple;
            }
        }

        return resultCommonMultiple;
    }

 

입력받은 두 수를 하나는 Map, 하나는 List에 각자의 배수를 넣고, List를 순회하면서 가장 큰 같은 배수를 찾아서 리턴으로 반환하는 코드입니다. 아무래도 입력받은 두 수의 배수를 찾는 것부터 많은 1부터 그 수의 끝까지 반복을 해야하기 때문에 시간이 굉장히 많이 걸리는 단점이 있고, 실제로도 백준 문제에서 시간초과를 받았습니다 ㅠ

 

유클리드 호제법

    public static int maximumCommonMultiple(Integer a, Integer b) {

        if (b == 0) {
            return a;
        }

        return maximumCommonMultiple(b, a % b);
    }

 

코드가 굉장히 많이 줄었어요. 계속해서 b로 a를 나눈 나머지를 b 자리에 b를 a 자리에 넣어서 재귀호출을 하고, a를 b로 나눈 나머지가 0일때 a가 최대 공약수입니다. 이것의 증명은 아래의 링크 나무위키에 가서 보세요. 저는 이해가 안되요... 

 

유클리드 호제법 - 나무위키

 

 

자바로 손쉽게 최대공약수를 찾는 방법에 대해서 알아보았습니다.