[알고리즘] 유클리드 호제법에 대해서 알아보자.

유클리드 호제법이란?두 정수의 최대 공약수(GCD, Greatest Common Divisor)를 구하는 효율적인 알고리즘이다. 사용 방법 public static int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } 1. b가 0이면 a가 최대 공약수이므로, 반환2. 아니라면 a % b (나머지 연산)로 문제를 줄여 재귀 호출한다.3. 나머지가 0이 될 때까지 반복해서 GCD를 구한다. 유클리드 호제법을 사용하여 최소공배수 구하기공식 : a * b / GCD(최대공약수) public static int lcm(int a, int b) { return a * b / gcd(a, b); } 마무리잊을 쯤 되면 보이는 최대공약수, ..

2025.07.27