프로그래머스 - N개의 최소공배수(유클리드 호제법 알아보기)

https://programmers.co.kr/learn/courses/30/lessons/12953

코딩테스트 연습 - N개의 최소공배수

이 문제는 유클리드 호제법을 이용해 최대 공약수를 구할수 있다면 보다 쉽게 접근할 수 있는 문제입니다.

저 역시 알고리즘 문제를 풀면서 이전에도 유클리드 호제법을 접해보았는데 다시 문제에 활용하려고 하니 하나도 기억이 안나더라고요.

이 기회에 유클리드 호제법을 정리하려고 이 글을 포스팅합니다~ 추후에 문제에 활용할 수 있었으면 좋겠습니다 ㅎㅎ

유클리드 호제법

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다. 호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다. 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다. 이는 명시적으로 기술된 가장 오래된 알고리즘으로서도 알려져 있으며, 기원전 300년경에 쓰인 유클리드의 《원론》 제7권, 명제 1부터 3까지에 해당한다.

에우클레이데스의 원론 - 위키백과, 우리 모두의 백과사전

 

글만봐도 겁나서 읽기가 싫네요..

그냥 최대 공약수를 구할 때 이 방법을 쓰면 쉽게 정답을 도출 할수 있다라고만 생각하고 예시를 보고 넘어가겠습니다!

유클리드 호제법 예시

1071과 1029의 최대공약수를 구하면,

• 1071은 1029로 나누어떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어떨어진다.

따라서, 최대공약수는 21이다.

자바 소스코드

1. 재귀

public class 유클리드호제법 {

    public static void main(String[] args) {

        int answer = gcd(1071,1029);
        System.out.println(answer);
    }

    private static int gcd(int a, int b){
        if(b == 0)
            return a;

        return gcd(b, a%b);
    }
}

 2. 반복문

public class 유클리드호제법 {

    public static void main(String[] args) {

        int answer = gcd(1071,1029);
        System.out.println(answer);
    }

    private static int gcd(int a, int b){
        while(b>0){
            int tmp = a;
            a = b;
            b = tmp%b;
        }
        return a;
    }
}

 두가지 구현 방법 모두 간단한 편이므로 알고 있는게 도움이 될 것 같습니다. 둘 중 하나를 사용해야 한다면 재귀 구현을 사용하게 되면 호출 스택이 메모리에 계속 쌓이니까 반복문으로 구현하는게 더 좋을것 같습니다.

N개의 최소 공배수 풀이 방법

만약 3, 6, 30의 최소 공배수를 구한다고 생각해보겠습니다.

3과 6의 최소 공배수는 6입니다.

그리고 이 최소 공배수인 6과 30의 최소 공배수를 구합니다. 

6과 30의 최소 공배수는 30으로 3, 6, 30의 최소 공배수와 같습니다. 이런 방식으로 n개의 최소 공배수를 구할 수 있습니다.

풀이 코드

2개 원소의 최소 공배수를 구한 후에 다시 배열에 넣은 후 차례대로 최소 공배수를 계산하기 위해서 Deque 자료구조를 사용했습니다.

2개 원소의 최소 공배수를 구하기 위해서는 위에서 학습한 유클리드 호제법을 활용해 최대 공약수를 구한 후, 두 원소의 곱을 최대 공약수로 나누게 되면 최소 공배수를 구할 수 있습니다.

class Solution {
        public int solution(int[] arr) {

            Deque<Integer> deque = new LinkedList<>();

            for(int i=0; i<arr.length; i++){
                deque.add(arr[i]);
            }

            return nLcm(deque);
        }

        private int nLcm(Deque<Integer> queue){

            while(queue.size() != 1){
                int a = queue.pop();
                int b = queue.pop();
                int lcm = a*b / gcd(a,b); // 최소공배수
                queue.addFirst(lcm);
            }

            return queue.pop();
        }

        // 최대 공약수
        private int gcd(int a, int b){
            while(b>0){
                int tmp = a;
                a = b;
                b = tmp%b;
            }
            return a;
        }
    }