[Algorithm] Euclidean Algorithm

유클리드 알고리즘에 대해 알아보고, 관련 문제를 해당 알고리즘으로 풀어보도록 하겠습니다.

 

이미지 출처: https://youtu.be/34eplUrmGfY

 

유클리드 알고리즘, 유클리드 호제법(互除法)이란?

유클리드 호제법(-互除法, Euclidean algorithm) 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘의 하나이다.

 

호제법에 대한 설명은 다음과 같습니다.

두 수가 서로 상대방을 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
호제법이라는 말은 서로(互) 나누기(除) 때문에 붙여진 이름이다.
이 뜻의 '호제' 라는 단어가 따로 있지는 않다.

 

다시, 유클리드 호제법

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b),
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고,
다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가
a와 b의 최대공약수이다.

두 양의 정수 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가 된다.

 

예시

110과 35의 최대공약수를 유클리드 알고리즘을 이용하여 구해보겠습니다.

a > b의 조건은 성립합니다.

a / b = 110 / 35의 나머지는 5, r = 5

b / r = 35 / 5의 나머지는 0.

나누는 수 r = 5가 a, b의 최대공약수 입니다.

 

문제: 프로그래머스 최대공약수와 최소공배수

코딩테스트 연습 - 최대공약수와 최소공배수

위 설명에서 '다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여...' 라는 부분이 있습니다.

여기서 재귀용법을 사용해서 구현할 수 있다고 떠올릴 수 있습니다.

public class Solution {
    public int[] solution(int n, int m) {
        int[] answer = new int[2];
		
        // a > b의 조건을 맞춰주기 위해 swap해줍니다.
        if(n < m) {
            int temp = n;
            n = m;
            m = temp;
        }

        int gcd = gcd(n, m); // 최대공약수
        int lcm = n * m / gcd; // 최소공배수

        answer[0] = gcd;
        answer[1] = lcm;

        return answer;
    }

    static int gcd(int a, int b) {
    	// 나눈수의 나머지가 0이면 나눈수가 최대공약수
        if(a % b == 0) {
            return b;
        }
        // 그렇지 않으면 반복해서 b와 a/b의 나머지를 반환합니다.
        return gcd(b, a % b);
    }

    @Test
    public void test() {
        int[] a = solution(110, 35);
        int[] b = {5, 770};
        Assert.assertArrayEquals(a,b);
    }
}