알고리즘

[Algorithm] 자바/ 최대공약수, 최소공배수 - 유클리드 호제법

유클리드 호제법이란 2개의 자연수를 받아 최대공약수를 구하기 위해 2부터 두 자연수 중 가장 작은 자연수까지 나누어 최대공약수를 구하는 방법이다. 이를 이용하여 최대공약수 구하는 알고리즘을 정리하고자 한다. public static void main(String[] args){ int a = sc.nextInt(); int b = sc.nextInt(); int gcd = gcd(a,b); // 최대공약수 int d = (a*b/gcd); // 최소공배수 } public static int gcd(int a, int b){ if(b == 0) return a; // GCD(a,b) = GCD(b, r) r = a% b return gcd(b, a%b); } - 백준 2609번 https://www.acm..