알고리즘1 유클리드 호제법(Euclidean Algorithm) 유클리드 호제법(Euclidean Algorithm)은 두 정수 a, b 의 최대 공약수를 구하는 알고리즘이다. 두 정수 a, b의 최대 공약수는 a를 b로 나눈 나머지 r을 구한 후, b를 r로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되는 경우의 나머지를 최대 공약수로 간주한다. 과정을 수식으로 표현하면 a % b = r 이면 b % r = s를 계산하여 나머지가 0이 될 때 까지 반복한다. 예를 들어 a = 30, b 12일 경우 30 % 12 = 6, 12 % 6 = 0 이 되므로 6이 최대 공약수다. JAVA로 표현하면 이렇게 표현할 수 있다. int gcd(int a, int b){ if(b==0) { return a; } else{ return gcd(b,a%b); } } 이를 이.. 2023. 2. 8. 이전 1 다음