-
유클리드 호제법 (최대공약수)Algorithms 2022. 2. 13. 23:21
유클리드 호제법 : 2개의 자연수 또는 정수의 최대공약수를 구하는 알고리즘이다.
서문
위 문제의 풀이 중 최대공약수를 링크와 같이 단순 무식하게 풀었는데
최대공약수를 구하는 알고리즘이 있어서 정리한다.
유클리드 호제법
private int gcd(int a, int b){ if(b == 0){ return a; }else{ return gcd(b, a % b); } }
원리
2개의 자연수 또는 정수를 직사각형의 한 변으로 가정하고 짧은 길이로 긴 길이를 나눈다.
그리고 나눈 나머지가 짧은 길이가 되고 원래의 짧은 길이가 긴 길이가 된다.
그리고 위 과정을 반복(재귀)해주다가 나누어 떨어져 0이 되는 순간의 짧은 길이가 최대공약수가 된다.
참조
반응형