swift / 유클리드 호제법으로 최대 공약수 구하기

알고리즘 문제에서 최대 공약수를 구하는 문제들이 나오는데요
간단하게 최대 공약수를 구할 수 있는 유클리드 호제법 이용해 쉽게 구할 수 있습니다.

 

유클리드 호제법이란?

큰 수에서 작은 수를 나누어 나머지를 구하고 나눈 몫과 나머지를 또 나누어 나머지가 0이 될 때까지 반복하는 원리입니다.

예를 들어 34와 26이라는 숫자의 최대 공약수를 구해보겠습니다.

 

34 / 26 = 1 (나머지 8)
26 / 8 = 3 (나머지 2)
8 / 2 = 4 (나머지 0)

 

나머지가 0이 됐고 마지막 나눈 값은 2입니다.

마지막 나눈 값이 최대공약수가 되기 때문에

(gcd) = 4 가 됩니다.

gcd는 최대공약수의 약자로 최대공약수(Greatest Common Divisor, GCD) 입니다.

코드로 작성하게 되면

 

func gcd(_ a: Int, _ b: Int) -> Int {
  let r = a % b
    
  if r != 0 {
    return gcd(b, r)
  } else {
    return b
  }
}

 

이런 식으로 최대 공약수를 구할 수 있게 됩니다.