백준 알고리즘 #5 - 유클리드 호제법

이번 포스트에서는 유클리드 호제법(Euclidean algorithm)에 대해 알아보겠습니다.

여러분들은 지금까지 살아오면서 최대공약수에 관해 한 번 이상은 들어봤을 것입니다.

최대 공약수는 두 수의 공약수 중 최대인 수를 이야기 합니다. 아마, PS 혹은 다른 쪽을 희망한다고 하더라도, 알아 두면 좋은 알고리즘 이라고 생각을 합니다. 또한, 이산수학에서도 배우게 될 내용이니 미리 학습하시는걸 추천드립니다!

 

 

 

🏳️ 왜 유클리드 호제법을 써야하는가?

유클리드 호제법의 개념을 이용하지 않고, 7과 28의 최대 공약수를 코드를 통해 도출해보죠.

 

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int Max(int num1, int num2)
{
	return (num1 > num2) ? num1 : num2; // 둘중 비교 해서 큰 값을 리턴하는 삼항 연산자입니다.
}

int main(void)
{
	int gcd = 0;
	int a = 7;
	int b = 28;
	for (int i = 1; i <= b; i++)
	{
		if (a % i == 0 && b % i == 0)
		{
			gcd = Max(gcd, i);
		}
	}
	printf("%d", gcd);
}

 

저희가 알고 있듯이, 제일 쉽고 간단한 방법은, 큰수의 범위까지 반복문을 돌려 a와 b를 나눈값이 0이 되는 수 중에 최댓값을 도출 하면 됩니다.

하지만 이 알고리즘의 최대 단점은 매우 느리다는 것입니다.

 

 

 

 

ex) 최대공약수를 구해야하는 두 숫자가 너무나 클 때

 

위 알고리즘으로 구현 했을 때

 

 

736326777 과 956126112같은 매우 큰 숫자의 최대공약수를 구할 때, 위 알고리즘처럼 코드를 구상하게 된다면 반복문을 i를 1부터 956126112까지 돌려야 할겁니다. 실제로 시간도 1.456초로 엄청 많이 걸리게됩니다.

 

 

유클리드 호제법으로 구현 했을 때

 

 

그러나 유클리드 호제법으로 구현 했을때, 시간이 비약적으로 단축된다는 것을 알 수 있습니다. 

 

 

 

 

 

 

🏳️ 그래서 유클리드 호제법이 뭔데?

-  두 수의 최대공약수를 구할 때,  나누기 연산을 이용해서 답을 도출해내는 방법입니다.

 

숫자 a와 b가 있다고 가정해봅시다.

1 - a를 b로 나눈 나머지를 r( a = max( a , b ), b = min( a , b ))이라고 하면 a와 b의 최대공약수는 b와 r의 최대 공약수와 같습니다.

2 - b를 r로 나눈 나머지를 r'이라고 하면, b와 r의 최대공약수는 b와 r'의 최대공약수와 같습니다.

3 - 위 과정을 반복할때, x라는 수로 나눈후 나머지가 0이 되면 그 'x'가 바로 a와 b의 최대공약수 입니다.

 

 

 

ex)

91872와 12744의 최대공약수 계산

91872 % 12744 = 2664
12744 % 2664 = 2088
2664 % 2088 = 576
2088 % 576 = 360
576 % 360 = 216
360 % 216 = 144
216 % 144 = 72
144 % 72 = 0

고로 최대 공약수는 72.

 

 

 

 

 

 

 

🏳️ 알고리즘으로 구현하는법

 

 

- 234, 44의 두 숫자로 표현해 보겠습니다.

 

 

 

 

 STEP1) 두 숫자의 나머지를 구해 줍니다.

 

 

 

   

 

 

 

234 % 44은 '14'입니다.

 

 

 

 

 

STEP2) 나머지가 0이 될때까지 STEP1을 반복합니다.

 

 

 

44 % 14는 '2' 입니다

 

14 % 2는 '0' 입니다.

 

이때, 2로 나눴을때 나머지가 0이 되므로 두 수의 최대공약수는 '2'가 됩니다.

 

 

 

 

 

 

Q) 그러면 코드를 짤 때, 무조건 큰 수가 앞에 오게 인자를 전달해야 하나요?

 

 

A) 아니요, 전달 순서를 신경쓰지 않아도 괜찮습니다. 어쩌피 둘은 뒤바뀌게 될거니까요.

 

 

 

 

   

 

 

이를 코드로 나타내면 다음과 같습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>

int GCD(int num1, int num2)
{
	int temp = num1 % num2;
	while (temp > 0)
	{
		num1 = num2;
		num2 = temp;
		temp = num1 % num2;
	}
	return num2;
}

int main(void)
{
	int a = 91872;
	int b = 12744;
	printf("%d와 %d의 최대 공약수 값 : %d\n", a, b , GCD(a, b));//or GCD(b,a)
}