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

유클리드 호제법이란?

두 정수의 최대 공약수(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);
  }

 

 

마무리

잊을 쯤 되면 보이는 최대공약수, 최소공배수 코딩테스트를 까먹어서 정리하기 위해 블로그에 적는다.