최대공약수 GCD(Greatest Common Division)

#17087 https://www.acmicpc.net/problem/17087

17087번: 숨바꼭질 6

 

최소공약수가 필요한 문제인데, 난 여태 최소공약수 연산을 다음처럼 했었다.

def get_gcd(num1, num2):
  for i in range(max(num1, num2), 0, -1):
    if num1%i == 0 and num2%i == 0:
      return i

공약수를 구하는 상황인 만큼 두 수의 약수가 아닌 수까지 loop를 돌리는 위 코드는 무조건 시간초과가 날 수 밖에 없었다.

그렇게 얻은 솔루션은 다음과 같다.

 

def get_gcd_efficiently(num1, num2):
  if num1 > num2:
    m, n = num1, num2
  else:
    m, n = num2, num1
   
  while n:
    mod = n
    n = m%n
    m = mod
  return m

어떤 원리인지는 잘 모르겠지만 아주 효율적인 코드이다.