최대 공약수란?
두 수의 약수들 중 공통된 약수중에서 가장 큰 약수를 의미한다
일반적인 최대공약수 구하기
- 일반적인 반복문을 활용하여 두 수 x와 y의 최대공약수를 구하는 방법이다
-
num변수는 최대공약수를 담을 것
-
int i = 1부터 시작한다
-> int i = 0 일 경우
-> x와 y를 0으로 나누는 연산은 불가능하기 때문에 오류가 발생한다 -
x와 y는 둘 중 더 작은 값을 기준으로 i부터 기준까지 반복한다
-
반복문을 계속 실행하다보면 결국 마지막에 num에 들어오는 i 값이 최대공약수가 된다
일반 코드
// 시간복잡도 O(N)
int x = 36;
int y = 18;
int num = 0;
for (int i = 1; i <= x && i <= y; i++)
{
if (x % i == 0 && y % i == 0)
{
num = i;
}
}
cout << "최대공약수의 값 : " << num << endl;결과값 :
해당 코드의 시간복잡도는 O(N)이다
-> x와 y중 더 작은값만큼의 반복을 진행하며 안의 조건문을 연산하기 때문이다
유클리드 호제법
유클리드 호제법을 사용해서 최대공약수를 쉽게 구해보자!
유클리드 호제법이란?
2개의 자연수 또는 정식(다항식)의 최대 공약수를 구하는 방식
-
큰 수를 작은 수로 나누는 모듈러(%)연산을 수행한다
-
앞 단계에서의 작은 수와, 모듈러 연산의 결과값(나머지값)으로 다시 모듈러 연산을 수행한다
-
2번 단계를 반복하다가 나머지가 0이 되는 순간의 작은 수가 최대 공약수이다
쉽게 말해, GCD(a, b) = GCD(b, a % b)이다
- 재귀함수를 사용한다
- 재귀함수를 탈출하는 조건은 y == 0 이다.
-> 나머지값이 0이 되었을때 재귀함수를 호출하면 y부분이 0이 되기 때문에 재귀탈출
유클리드 호제법 전체 코드
#include <iostream>
using namespace std;
int Euclid(int x, int y)
{
if (y == 0)
{
return x;
}
else
{
return Euclid(y, x % y);
}
}
int main()
{
cout << "최대공약수의 값 : " << Euclid(36, 18);
}- 재귀 탈출문을 y == 0 말고 나머지값이 0일때 y값을 반환하는 코드로 작성해도 된다
그냥 재귀함수를 한번 더 호출하느냐 마느냐의 차이일 뿐임
결과값 :
시간복잡도
두 수 x와 y중 더 작은값을 따라 로그에 비례한다 = (O(min(a,b))
즉, N = min(x, y)에서 x값이 더 작다면 시간복잡도는 O(logN)이다
-> 왜냐하면, 유클리드 호제법은 x와 y를 계속 모듈러 연산을 사용하면서 더 작은 값이 0이 될때까지 반복되기 때문이다
유클리드 호제법으로 최대공약수를 구하는건 딱히 어려운건 아닌 거 같았다
금방 이해할 수 있었다
유클리드 호제법 다시보기
코드를 다시 작성하다가 갑자기 떠올랐다
x와 y중 큰 값에서 작은 값을 나누는 모듈러 연산인데
둘 중 더 큰 값을 어떻게 판별한걸까??
- 아래의 코드를 예시로 12와 20을 넣었다
-> 처음 조건문에서12 % 20 != 0이기 때문에 else문으로 이동한다 - else문에서 재귀를 호출할때
Euclidean(20, 12 % 20)이 호출된다
-> 12 % 20의 몫은 1이고 나머지는 12이기 때문에
-> 결론적으로,Euclidean(20,12)가 호출되는 것이다! 큰값이 앞에왔죠!
#include <iostream>
using namespace std;
// 유클리드 호제법
// 큰 수를 작은 수로 나눈 나머지 값(r)을 계속 나누면서
// 두 수의 최대공약수를 알아내는 방식
// GCD(a, b) : a % b = r
int Euclidean(int x, int y)
{
if (x % y == 0)
{
return y;
}
else
{
return Euclidean(y, x % y);
}
}
int main()
{
cout << Euclidean(12, 20);
return 0;
}