유클리드 호제법으로 최대공약수 구하기

date

Dec 27, 2023

slug

get-gcd-by-euclidean

author

status

Public

기존의 최대 공약수를 구하는 방법


public int getGreatestCommonDivisor(int num1, int num2) {
	int little = num1 < num2 ? num1 : num2;
	int gcd = 0;
	for(int i = 1; i <= little; i++) {
		if(num1 % i == 0 && num2 % i == 0) gcd = i;
	}
	return gcd;
}

이렇게 반복문을 활용해서 일일히 공약수의 자격이 있는 수를 판별하고, 그 중 가장 큰 수를 반환해서 푸는 것이 일반적인 접근 방법입니다.

물론 이 코드로도 대부분의 코드는 통과하지만, 새로운 알고리즘을 발견해 소개해보고자 글을 작성하게 되었습니다.

유클리드 호제법

유클리드 호제법(Euclidean algorithm) 은 두 양의 정수 혹은 다항식에 대한 최대 공약수를 구하는 방법입니다. 인류 최초의 알고리즘으로도 유명한데요, 그 내용은 다음과 같습니다.

두 양의 정수 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) 에 대하여, a를 b로 나눈 나머지를 r이라고 하겠습니다.

a = bq + r 로 나타낼 수 있습니다. (여기서 q 는 몫을 나타냅니다)

a 와 b 의 공약수 d 가 있다고 가정했을 때, d 는 a = bq + r 의 오른쪽 항인 bq 와 r 의 약수이어야 합니다. (나머지가 없도록)

반대로, d 가 b 와 r 의 공약수라면, d 는 a = bq + r 을 나눌 수 있어야 합니다.

따라서 a 와 b 의 모든 공약수는 b 와 r 의 공약수이며, 그 반대도 성립하게 됩니다.

위 성질을 이용해서 계속해서 반복하면 최대공약수 를 구할 수 있습니다.

이 과정을 반복해서 b 를 r 로 나누고 그 다음 나머지로 나누는 과정이 연속됩니다.

나머지가 0이 될 때 까지 계속 진행된다면, 마지막으로 나누는 수가 최대공약수 입니다.

java 코드로 한 번 구현해보겠습니다.


public int euclidean(int num1, int num2) {
	while (num2 != 0) {
		int r = num1 % num2; // a를 b로 나눈 나머지
		num1 = num2;         // 다음 계산을 위해 b를 a에 할당
		num2 = r;            // 다음 계산을 위해 나머지를 b에 할당
	}
	return a; // 나머지가 0이 되었을 때 a가 최대공약수!
}

위 성질을 이용해서 최대 공약수를 구하는 코드입니다.

재귀를 이용해서 더 간단하게 표현할 수도 있습니다.


public int euclidean(int num1, int num2) {
	if (num2 == 0) return num1;
	return euclidean(num2, num1 % num2);
}

다만 주의해야할 것은 유클리드 호제법이 항상 최적인 알고리즘은 아니라는 점입니다.

엄청나게 큰 수에 대해서는 오히려 시간복잡도가 증가하게 되고 다른 준선형적 알고리즘을 채택해야한다고 합니다.

하지만 기존의 방법에 비해서는 훨씬 효율적으로 느껴지기는 합니다.

분수를 다루는 코드를 작성하다가 이런 방법을 발견했는데요~! 다음에도 재미있는 알고리즘을 발견하면 소개하도록 하겠습니다.