유클리드 호제법

[Algorithm] 유클리드 호제법

[Algorithm] 유클리드 호제법 (글쓴날 : 2020.03.23) * 이 글은 글쓴이가 공부한 내용을 정리하며 올리는 글입니다. 유클리드 호제법 1) 유클리드 호제법이란? 유클리드 호제법이란 어떤 두 자연수의 최대공약수를 구하는 알고리즘의 하나로 최대공약수를 구하는 알고리즘 중 가장 대표적인 알고리즘입니다. 호제법이란 주어진 두 수로 서로 다른 수를 나누어 원하는 결과를 얻는 방법을 의미하며, 그에 따라, 유클리드 호제법은 어떤 자연수 a, b가 있을 때 (a > b), 두 수의 최대공약수는 a를 b로 나눈 나머지와 b의 최대공약수와 같다. 라는 성질을 이용한 알고리즘입니다. 위의 원리에 따라, a를 b로 나눈 나머지를 다시 a로 사용하고 b로 또 나누고 이렇게 반복하다, 나누어떨어질 때 나눈 수가..