[코딩테스트] 최대공약수, 최소공배수 구하기 (유클리드 호제법)

코딩테스트를 풀다보면 간간히 최대공약수, 최소공배수와 관련된 문제를 찾아볼 수 있다.

 

수학에 익숙하지 않은 사람이면 '최대공약수', '최소공배수'라는 워딩에서 주는 생소함에 부담을 가질 수도 있다.

 

하지만 코테 사이트에서 이와 관련된 문제를 꽤나 낮은 난이도의 문제로 취급하고 있는 만큼, 생각보다 어렵지 않은 개념이라 볼 수 있다.

 

최대공약수(GCD) 구하기

최대공약수는 유클리드 호제법을 이용하여 구할 수 있는데, 이는 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될 때 까지 작동하여 구하는 방식이다.

 

1. 재귀 방식으로 구현

// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

 

2. 반복문 방식으로 구현

// 반복문 방식
public static int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

최소공배수(LCM) 구하기

최소공배수는 두 수(a, b)를 앞서 구한 최대공배수로 나누어 구할 수 있다.

public static int lcm(int a, int b) {
    return a * b / gcd(a, b);
}