알고리즘 기법

유클리드 호제법 설명 & 자바, 파이썬 구현

유클리드 호제법이란? 유클리드 호제법은 2개의 자연수의 최대 공약수를 구하는 알고리즘 중 하나이다. 방법 2개의 자연수 a, b에 대하여 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대 공약수는 b와 r의 최대 공약수와 같다. 이 성질을 반복적으로 이용하여 r이 0이 되었을 때 나누는 수(b) 가 a와 b의 최대 공약수이다. 예시 24와 9의 최대 공약수를 구해보자. a = 24, b = 9 이라고 할 때, r은 a%b(a를 b로 나눈 나머지) 이므로 r = 6이 된다. 그러면 24와 9의 최대 공약수는 9와 6의 최대 공약수 와 같다는 것을 알 수 있다. 다시 9와 6의 최대 공약수를 구하기 위해 a = 9, b = 6이라 하면 r = 3이 되므로 9와 6의 최대 공약수는 6과 3의 최대 공약수..