백준 9613 GCD 합 - 유클리드 호제법(최대공약수 구하기)

백준 9613

여느날과 같이 백준 문제를 풀던 중 GCD라는 용어를 만나게 되었다.

GCD가 해당 문제에서 제시한 개념인줄 알고 눈을 부릅 뜨고 찾아봤지만...

그런건 없었다... ㅎㅎ

 

찾아보니 GCD는 Greatest Common Divisor의 약자로 최대 공약수를 의미하는 것이었다.

 

기존의 코드

따로 특별한 알고리즘에 대해서 알고있는게 없기 때문에 일단 생각나는데로 코드를 작성했다.

int getGCD(int a, int b)
{
	if(!a || !b)
		return 0;
	vector<int> vt;
	vt.push_back(1);
	int start = 2;
	while(1){
		if(start > a)
			break;
		if(a % start == 0){
			vt.push_back(start);
			a = a / start;
		}
		else{
			start ++;
		}
	}

	int ans = 1;
	for(auto i = vt.begin(); i != vt.end(); i++){
		if(b % *i == 0)
		{
			b = b / *i;
			ans *= *i;
		}
	}
	return ans;
}

논리는 다음과 같다.

a와 b가 있으면 a의 인수를 모두 구한다.

인수를 순회하며 만약 해당 인수가 b의 약수라면, b의 값을 인수로 나누고 해당 인수를 공약수값을 추가한다.

이를 반복해 최대공약수를 구한다.

 

유클리드 호제법

 

사실 틀린 논리는 아니다. 이걸로 정답을 받았지만 GCD라고 이름을 붙인것으로 보아 알고리즘이 있을 것같아 찾아보니 유클리드 호제법이라는 유클리드 선생님의 가르침이 있었다.

 

유클리드 호재법은 A와 B의 최대공약수가 B와 A%B의 나머지와의 최대공약수가 같다는 이론이다.

 

증명은 아래와 같다. (수악중독 유투부 참고함)

개선된 코드

 

이를 코드로 풀어내면 다음과 같다.

int GCD(int a, int b)
{
	if(b == 0)
		return a;
	else return GCD(b, a % b);
}

논리는 다음과 같다.

A, B (A > B)가 있을때 A와 B의 최대공약수는 B와 A%B의 최대공약수가 같다는 유클리드 호제법에 기반해 최대공약수를 구한다.

 

재귀적으로 실행되어 조금 이해가 안될 수 있는데, 이를 그림으로 표현해보았다.

 

 

연쇄적으로 호출되는 GCD들은 모두 같은 최대공약수를 가지고 있다.

값이 작아지고 작아져, 결국 나누어지는 값인 B가 0인 시점에 최대공약수를 발견해 리턴하고, 이를 모든 GCD함수가 반환하므로 재귀적으로 최대공약수를 찾을 수 있다.

 

 

출처:

https://www.youtube.com/watch?v=J5Yl2kHPAY4 (수악중독 유튜브)