유클리드 호제법

오늘은 백준 2609 문제를 통해 유클리도 호제법을 공부했다.

 

유클리드 호제법이란, a,b의 최대공약수를 구하기 위한 알고리즘인데 a = b * q + r이라고 할 때, gcd(a,b) = gcd(b,r)인 것을 이용한다.

 

예를 들어,

 

123 58의 최대공약수를 구한다고 해보자.

123 = 58 * 2 + 7 이므로 gcd(123, 58) = gcd(58, 7) = ... 이런식으로 계속 진행되는 것이다.

 

반복되는 구간이 보이듯이, 이 알고리즘은 재귀 또는 반복으로 구현할 수 있다. 간편하게 재귀로 구한 알고리즘은 다음과 같다:

int gcd(int a, int b)
{
	if (b == 0) return a;
	if (b > a) gcd(b, a);
	
	return gcd(b, a % b);
}

( a > b )인 점에 유의하자.

 

최소공배수는 이렇게 구한 최대공약수를 이용해서 구할 수 있다. lcm(a,b) = a * b / gcd(a,b) 이다.