유클리드호제1 [알고리즘/자바] 재귀 알고리즘으로 유클리드 호제법 구현하기 유클리드 호제법 크기가 큰 두 수가 있을 때 최대 공약수를 빠르게 구하기 위해서 사용한다. 유클리드 호제법은 A를 B로 나눈 나머지가 C일 때, (A와 B의 최대 공약수) = (B와 C의 최대 공약수)라는 사실을 이용해서 처음에 구하려고 했던 숫자의 크기를 점점 줄여 간단하게 만든 다음 최대 공약수를 구하는 방법이다. 예를 들어, 48과 21의 최대 공약수를 구해본다면. 48/21 ••• 6 21/6 ••• 3 6/3 ••• 0 최대 공약수는 3이 된다. 유클리드 호제법 메서드 구현 static int ea(int x, int y) { if (y == 0){ return x; } else { return ea(y, x % y); } class EuclidGCD { static int ea(int x, i.. 2019. 12. 23. 이전 1 다음
