최대공약수(GCD)와 최소공배수(LCM) 를 위한 유클리드 알고리즘

 

유클리드 알고리즘은 어렸을적부터 접하는 익숙한 알고리즘이지만, 수학적인 부분이 포함되어 있어 막상 구현하고자 한다면 기억해내기가 쉽지 않다.

 

그 중에서도 알고리즘 문제 해결 시 심심치않게 등장하면서도 중요한 최대공약수(GCD) 와 최소공배수(LCM) 를 구하기 위한 유클리드 알고리즘을 정리해보았다.

 

가장 원시적인(Naive) 방법으로 GCD와 LCM을 구하는 방법으로는, 브루트포스(Bruteforce) 알고리즘이 있다.

 

이는 숫자 목록을 전부 순회하면서 해당 숫자가 주어진 숫자 세트의 최대공약수 / 최소공배수 인지를 판별하는 알고리즘이다.

 

이 방법 자체가 복잡하다거나 한 것은 아니지만, 불필요한 값들의 조회가 많이 일어나는 비효율적인 알고리즘이다.

 

유클리드 알고리즘은 "유클리드 호제법" 이라는 방식을 통해 최대공약수를 구해내고, 이를 바탕으로 최소공배수를 구해낸다.

 

이 원론은 숫자 A와 B에 대하여 A를 B로 나눈 나머지 R에 대해 A와 B의 최대공약수가 B와 R의 최대공약수와 같음을 이용하며, 이 나머지 연산을 나머지가 0이 될때까지 반복함으로써 최대공약수를 구해낸다.

 

최소공배수를 구하는 데 있어서는 다음 성질을 이용한다.

 

A와 B의 최대공약수 G에 대해서 최소공배수 L = A * B / G 를 만족한다.

 

이를 통해 알고리즘적으로 구현하면 다음과 같이 구해낼 수 있다.

 

 

좀 더 자세한 수학적 원리는 다음을 참고하자.

(http://staff.www.ltu.se/~larserik/applmath/chap10en/part3.html)