유클리드 호제법 Euclidian Algorithm

https://www.youtube.com/results?search_query=euclidean+algorithm

euclidean algorithm - YouTube

https://www.acmicpc.net/problem/2609

최대공약수 Greatest Common Divsor, 최소공배수 Least Common Muliple을 구하는 알고리즘이다. 일명 유클리드 호제법.

최대공약수를 가지고 최소 공배수를 구하는 법은 쉽다. 두 수 A,  B가 주어졌을 때 중복되는 부분인 최대공약수를 한번 나누어주면 된다.

문제는 최대공약수를 구하는 것인데, 이 때 유클리드 호제법을 이용한다. 방법은 위 영상과 같이 그저 따라만 가면 되는거라 크게 어려운 부분이 없지만 그 안에 담겨져 있는 논리는 쉽게 파악하기 어렵다. 그냥 두 수를 같은 방식으로 나누어 봤을 때 더 이상 나머지가 존재하지 않을 때 그 몫이 두 수의 최대공배수가 된다.