[알고리즘] 최대공약수, 최소공배수 (유클리드 호제법)

1. 최대 공약수 최대공약수, 최대공배수를 사용하려면 소인수분해를 사용해야 합니다. 하지만 숫자가 크면 클수록 소인수분해의 횟수는 점점 증가하기 때문에 유클리드 호제법을 사용하면 시간복잡도는 단축이 됩니다. 유클리드 호제법은 명시적으로 기술된 가장 오래된 알고리즘으로, 무려 기원전 300년에 쓰여졌다고 합니다. 여기서 호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타냅니다. 일반적으로 최대공약수를 구하는 가장 쉬운 방법은 2부터 모든 정수로 나누어 보는 방법이 있을 것 같은데 이의 경우 모든 정수를 나눠야 하므로 시간 복잡도는 O(N)이 됩니다. 유클리드 호제법을 사용한다면 때 a % b이 0이 될 때까지 반복을 해주기 때문에 시간 복잡도를 O(Log N)으로 줄..