[Java]유클리드 호제법(Euclidean Algorithm)

*유클리드 호제법(Euclidean Algorithm)

-> 유클리드 호제법은 두 개의 자연수 or 두 개의 다항식의 최대공약수를 구하는 방법이다.

유클리드 호제법

※ a는 b의 피제수(즉, 나누어지는 수)이므로 a > b이다.

※ 따라서 수식의 q는 몫, r은 나머지를 의미한다(따라서 r은 0보다 같거나 크고 b보다는 작아야 한다).

-> 유클리드 호제법은 최대공약수를 구하는데 사용한다고 하였다. 최대공약수는 수학적으로 두 수의 모든 약수를 나열한 뒤 공통되는 약수 중 최대를 선택하거나 소인수 분해를 이용한 방법이 있지만, 유클리드 호제법을 이용하면 더 빠른 시간 안에 최대공약수를 구할 수 있다.

 

*유클리드 호제법의 사용

-> 피제수가 제수에 의해 나누어 떨어진다면, 그 피제수와 제수의 최대공약수는 제수이다. 이 명제를 응용하면 몇 번의 반복된 연산을 이용하여 최대공약수를 구할 수 있다.

-> 126과 45의 최대공약수를 구하는 아래 예시를 확인해보자.

  126을 45로 나누면 그 몫은 대충 q라고 생각하고(최대공약수를 구한다면 굳이 생각하지 않아도 된다), 나머지는 36이 될 것이다. 126과 45의 최대공약수는 유클리드 호제법에 의하여 45와 36의 최대공약수와 같다고 하였으므로, 45에 대하여 36을 나누고 나머지를 구한다. 마찬가지 방법으로 45와 36의 최대공약수는 유클리드 호제법에 의하여 36과 9의 최대공약수와 같다. 그런데 여기서, 36은 9로 나누어 떨어지므로 36과 9의 최대 공약수는 9임을 알 수 있다. 즉, 앞선 과정을 반복하여 피제수가 제수에 의해 나누어 떨어지는 순간이 되면, 초기 두 자연수 혹은 두 다항식의 최대공약수를 구할 수 있다. 아래 예시도 확인 해보자. 본인이 쉽게 최대공약수를 알 수 있는 두 수를 선택해서 해당 로직을 적용해보면 더욱 좋다.

따라서, 510과 2의 최대공약수는 2임을 알 수 있고 이에 따라 1534와 1022의 최대 공약수도 2임을 알 수 있다.

 

*유클리드 호제법을 이용한 최대공약수를 구하는 방법 구현

-> 위의 로직을 정확히 이해하였다면 재귀 혹은 반복문을 이용하여 구현은 쉽게 할 수 있다. 아래 코드를 참고하도록 하자.

import java.util.Scanner;

public class EuclideanAlgorithm {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt(); // 제수
		int b = sc.nextInt(); // 피제수

		System.out.println(GCD(a, b));
		sc.close();
	}

	// 유클리드 호제법을 이용한 최대 공약수 구하기
	private static int GCD(int a, int b) {
		// 나머지가 0이라면 해당 수가 최종 최대 공약수이다.
		if (a % b == 0) {
			return b;
		}
		// 그렇지 않다면 제수를 다음 피제수로, 나머지를 다음 제수로 바꾸어 재귀를 진행한다.
		else {
			return GCD(b, a % b);
		}
	}
}