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

정수 A와 B의 최대 공약수를 구하는 가장 간단한 방법은 A가 B보다 크거나 같을 때,
1부터 B까지 모든 정수로 A와 B가 동시에 나누어 떨어지는지 확인하면 됩니다.

그러나 이 방식은 O(log(B)) 라는 시간 복잡도이기 때문에 B의 크기가 매우 크면 불리합니다.
이 성능을 개선하기 위해 사용되는 것이 유클리드 호제법 입니다.

두 정수 A와 B에서 A >= B가 성립할 때, B와 A를 B로 나눈 나머지 값을 재귀적으로 구하면서
B의 값이 0이 되는 순간의 A값이 최대 공약수입니다.

예를 들어 200과 180의 최대 공약수를 구하는 연산을 의사 코드로 표현하면 다음과 같습니다.

func(200, 180)
     func(180, 20)     // 200 % 180 == 20
          func(20, 0)  // 180 % 20 == 0
          {
            return 20;
          }

따라서 200과 180의 최대 공약수는 20임을 확인할 수 있습니다.
위의 의사 코드를 C++ 코드로 변환하면 아래와 같습니다.

int UC_GCD(int A, B)
{
  if(B == 0)
  {
    return A;
  }
  else
  {
    return UC_GCD(B, A % B);
  }
}