유클리드호제법

첫 번째 문제 : 1934번 package baekjoon; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStreamReader; import java.util.StringTokenizer; /** * 두 자연수 a,b에 대하여, a의 배수이면서 b의 배수인 자연수를 * a와 b의 공배수라고 한다. * * 이 공배수 중에서 가장 작은 공배수를 최소 공배수라고 한다. * 두 자연수가 주어졌을 때, a와b의 최소공배수를 구하시오. * @author Back * */ public class _1934 { public static void main(String[] args) throws NumberFormatExce..

유클리드 호제법 (GCD) 💡 유클리드 호제법은 2개의 자연수 또는 정식의 최대공약수를 구하는 알고리즘 중 하나이다. 호제법 = 두 수가 서로 상대방 수를 나누어 결국 원하는 수를 얻는 알고리즘을 말한다. 명시적으로 기술된 알고리즘 중 가장 오래되었다고 알려져 있다. 원리 1️⃣ 2개의 자연수 a,b 에 대하여 a를 b로 나눈 나머지가 r이면 (단, a>b) , a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 2️⃣ 이 성질을 이용해 이번에는 b를 r로 나눈 나머지 r2 를 구하고, 다시 r을 r2 로 나눈 나머지를 구하는 과정을 반복해서 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수인 것이다. 접근방법 1️⃣ 반복문을 이용한 방법 2️⃣ 재귀를 이용한 방법 int GCD(int a, ..