[알고리즘] 기약분수를 만들기 위한 최대공약수 구하기

분수 결과값을 기약분수로 만드는 문제에서 최대공약수를 구하는 알고리즘이 필요했다. 아래는 유클리드 호제법을 이용하여 최대공약수를 구하는 메서드이다. * 유클리드 호제법(Euclidean algorithm)이란?두 수의 최대공약수(GCD)를 빠르게 구하는 고대 그리스 수학자 유클리드가 고안한 알고리즘이다.두 정수 a와 b(단, a > b)가 있을 때, a와 b의 최대공약수(GCD)는 b와 a % b의 최대공약수와 같다는 원리를 반복적으로 이용한다. // 1. 재귀함수 사용public static int gcd1(int a, int b) { if (b == 0) return a; return gcd1(b, a % b);}// 2. 반복문 사용public static int gcd2(int a, i..