[ Do it! 알고리즘 코딩 테스트 ] 정수론 - 유클리드 호제법

🔷 유클리드 호제법( euclidean - algorithm )

: 두 수의 최대 공약수를 구하는 알고리즘이다.

 

유클리드 호제법을 사용하기 위해선 MOD 연산을 알고있어야한다. 

 

MOD ?

최대 공약수를 구하는 연산으로 Modulo 나머지 연산으로도 불린다.

 

🔷 유클리드 호제법의 원리

🔻 큰 수에서 작은 수로 나누는 MOD 연산 

🔻 앞에서 진행한 작은 수와 MOD 연산 결과값과 MOD 연산 수행

🔻 반복하다가 나머지가 0이 되는 순간 작은 수를 최대 공약수로 선택