유클리드 호제법 Euclidean algorithm2개의 자연수의 최대공약수를 구하는 알고리즘 호제법 - 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘 유클리드 호제법 진행 순서1. 두 수 중 큰 수 를 작은 수로 나눈다2. 나머지가 0이면 작은 수가 최대 공약수가 된다3. 나머지가 0이 아니면 작은 수가 큰 수가 되고, 나머지가 작은 수가 되어 다시 큰 수를 작은 수로 나눈다 유클리드 호제법 특징1. 시간 복잡도 O(log(min(a, b))) - 두 수의 크기에 비례하여 알고리즘의 수행 시간이 결정된다 2. 재귀적으로 구현도 가능하다 ( gcd(a, b) -> gcd(b, a % b) )+ 최대공약수 성질 중에 gcd(a, 0) = a 라는 성질도 있다, 즉, 어떤 수와..