[알고리즘 - 기초] 유클리드 호제법, GCD(최대공약수) 구하기

유클리드 호제법이란 무엇인가?

---

유클리드 호제법(Euclidean Algorithm)은 두 자연수의 GCD(최대공약수 - Greatest Common Devisor)를 구하는 알고리즘이다.

 

서로 호(互) 덜 제(除) 법 법(法)

 

 

유클리드 호제법의 원리

---

1. 두 개의 자연수 A, B가 있다. (A > B) 그리고 A를 B로 나눈 나머지 R이 있다.
2. R이 0이라면,         A와 B의 최대공약수는 B이다.
3. R이 0이 아니라면, A와 B의 최대공약수는 B와 R의 최대공약수와 같기 때문에 A에는 B, B에는 R을 대입한 후 1번으로 돌아간다. 

 

 

재귀로 구현하기

---

C / C++

int get_gcd(int A, int B)
{
    int R = A % B;

    if(R == 0) return B;
    else return get_gcd(B, R);
}

 

 

반복문으로 구현하기

---

C / C++

int A, B, R;

while(B != 0)
{
    R = A % B;
    A = B;
    B = R;
}

printf("%d", A);

 

 

시간 복잡도

---

재귀, 반복문 모두 O(log(n))의 시간 복잡도를 가진다.

 

 

 

LCM(최소공배수) 구하기

---

두 개의 자연수 A와 B를 곱한 후 이를 최대공약수로 나눠주면 두 수의 최소공배수를 구할 수 있다.

 

이를 수식으로 나타내면 아래와 같다.

 

 

C / C++

int LCM(int A, int B)
{
    return A * B / GCD(A, B);
}

 

 

예제로 알아보는 유클리드 호제법

---

아래 문제를 통해 유클리드 호제법을 적용시켜보자

2609번: 최대공약수와 최소공배수

 

[Solution]

[BOJ] 2609번: 최대공약수와 최소공배수 (C, C++, Java, Python3)