[알고리즘] (swift) 유클리드 호제법 (feat. 최대공약수, 최소공배수 구하기)

최소공배수, 최대공약수를 구하는 알고리즘을 정말 간단하게 구현할 수 있으면서도, 계속 for문을 돌리고있고,,, 시간낭비를 할 때가 많다. 스스로 기억하기 위해서 적어두는 유클리드 호제법! 꼭 기억하고 있도록 하자

 

🔖 유클리드 호제법 이란? (feat. 최대공약수)

유클리드 호제법은 두 개의 정수(자연수) 사이에서의 최대공약수를 구하는 알고리즘이다.
호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

-wiki

 2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면 (단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

예시로 살펴보자.

💬 예시로 살펴보는 유클리드 호제법

1071과 1029의 최대공약수를 구해보자.

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. 여기서 나머지 r 은 42가 된다.
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. 여기서 r' 는 21이 된다.
• 42는 21로 나누어 떨어진다. 👉 따라서, 최대공약수는 21이다.

 

🔖 코드로 구현해보자. (swift)

위에있는 알고리즘은, 재귀를 사용해서 구현할 수 있을 것이다.

private func gcd(_ n: Int, _ m: Int) -> Int {
    return m == 0 ? n : gcd(m, n%m)
}

• n이 m보다 크다는 전제가 있어야한다.
• (1071, 1029)가 들어가게 되면, 1071에서 1029를 나눈 나머지 42가 다시 gcd에 들어가게 되고, 다시 1029가 n자리에 들어가게 된다. 즉, (1029, 42)가 되고, 다시 (42, 21)이 된다. 이 다음과정은 (21, 0)인데, 여기서 m 이 0이므로 n인 21이 출력되는 과정이다.

 

🔖 최소공배수는 어떻게 구할까

최대공약수를 구했다면, 최소공배수는 매우 쉽게 구할 수 있다. 8과 24 두 개의 수로 최소공배수를 구해보자.  A와 B의 최대공약수가 a, 최소공배수가 b라고 하면, A*B = a*b라는 공식이 성립한다. 이 공식을 활용해서 최소공배수를 구할 수 있다.