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

알고리즘 스터디 튜터를하게되어 간단하게 다뤄볼만한 알고리즘을 찾던 중 유클리드 호제법이 떠오름

먼저 시간복잡도를 고려하지 않고 직관적으로 최대공약수 코드를 작성해봄

min(n,m)만큼 반복문이 돌아가며 두 수에 모두 나누어 떨어질경우 result에 대입하여 마지막에 출력함

다음은 시간복잡도를 고려한 유클리드 호제법을 사용하여 작성

1. m%n != 0 일 경우 func(m,n) -> func(m,m%n)

2. m%n==0일 경우 m과 n의 최대공약수는 n

결과적으로 시간복잡도 O(min(m,n) => O(log(min(m,n)))