[알고리즘] GCD - 유클리드 호제법

유클리드 호제법이란

---

유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식의 최대공약수(Greatest Common Divisor, GCD)를 구하는 알고리즘입니다.

호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이라는 뜻입니다.

 

GCD 알고리즘

---

 

• 두 개의 정수 a와 b (단, a ≥ b)가 주어집니다.
• a를 b로 나눈 나머지를 구합니다. 즉, r = a mod  b.
• r이 0이라면, b가 a와 b의 최대 공약수이며, 알고리즘을 종료합니다.
• r이 0이 아니라면, a는 이전의 b가 되고, b는 이전의 r이 되어 위 과정을 반복합니다.

GCD 구현

---

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

GCD 시간복잡도

---

두 수 a와 b가 주어졌을 때, 각 단계에서 나눗셈과 나머지 연산을 수행하므로,

GCD의 시간복잡도는 log(min(a, b))입니다.