Algorithm

[Algorithm] 유클리드 호제법 : 최대 공약수와 최소 공배수(C++)

박땅콩 2022. 7. 20.

728x90

코딩 테스트 문제 중에 최대 공약수, 최소 공배수를 요구하는 문제가 있습니다.

그래서 최대 공약수와 최소 공배수를 구할 때 자주 사용되는 알고리즘인 유클리드 호제법에 대해서 정리해보려고 합니다.

유클리드 호제법이란

두 수의 최대 공약수를 구하는 알고리즘입니다.

유클리드 호제법을 사용하기 위해서는 MOD 연산에 대해서 알아야합니다.

MOD 연산이란 ?

두 값을 나눈 나머지를 구하는 연산으로,

큰 수를 작은 수로 나눈 나머지를 구합니다.

그렇다면 유클리드 호제법 예시를 들어보도록 하겠습니다.

예를 들어 1112, 695 두 수의 최대 공약수를 구하고자합니다.

그렇다면

첫번째 : 1112 MOD 연산 695 = 417

나눴던 수와 나머지를 또 MOD 연산을 수행합니다.

두번째 : 695 MOD 연산 417 = 278

세번째 : 417 MOD 연산 278 = 139

네번째: 278 MOD 연산 139 = 0

마지막 계산에서 나머지가 0이 되었을 때 나눴던 수가 1112와 695의 최대 공약수가 됩니다.

최대 공약수 139

그리고 최소 공배수를 구하는 방법은 최대 공약수를 알고 있으면 쉽게 구할 수 있습니다.

수학적으로 두 수의 곱 = 두 수의 최대 공약수 * 두 수의 최소 공배수 입니다.

정리하자면 두 수의 최소 공배수 = 두 수의 곱 / 두 수의 최대 공약수 입니다.

3개 이상의 수에 대한 최대 공약수 구하는법

2개의 수가 아닌 3개의 수에 대한 최대 공약수를 구하려면

두 수를 묶어서 최대 공약수를 계산하고, 결과로 나온 최대 공약수와 남은 수를 묶어서 최대 공약수를 구하면 됩니다.

예를 들어서 18, 42, 64의 최대 공약수를 구하려면

42와 18의 최대 공약수를 구합니다.

: 최대 공약수 6

6과 64의 최대 공약수를 구합니다.

: 최대 공약수 2

따라서 18, 42, 64의 최대 공약수는 2입니다.

3개 이상의 수에 대한 최소 공배수 구하는법

2개의 수가 아닌 3개의 수에 대한 최소 공배수를 구하려면

두 수를 묶어서 최소 공배수를 계산하고, 결과로 나온 최소 공배수와 남은 수를 묶어서 최소 공배수를 구하면 됩니다.

예를 들어서 18, 42, 64의 최소 공배수를 구하려면

42와 18의 최대 공약수를 구합니다.

: 최대 공약수 6

42와 18의 최대 공약수가 6 이므로 최소 공배수를 구하면

최소 공배수 = 42 * 18 / 6

최소 공배수 126

결과로 나온 126과 64의 최소 공배수를 구하면

126과 64의 최대 공약수를 구합니다.

: 최대 공약수 2

126과 64의 최대 공약수가 4이므로 최소 공배수를 구하면

최소 공배수 = 126 * 64 / 2

최소 공배수 4032

따라서 18, 42, 64의 최소 공배수는 4032 입니다.

최대 공약수/최소 공배수 구현(C++)

위 내용을 기반으로 최대 공약수를 구하는 함수를 구현하였습니다.

각 파라미터에 값을 전달함으로서 (단, a > b) 최대 공약수를 구할 수 있습니다.

int gcd(int a, int b) {
    int c = 0;
    while(true) {
        c = a % b;
        if(c == 0) {
            break;
        }
        a = b;
        b = c;
    }
    return b;
}

최대 공약수 구하는 방법 (2) - 삼항 연산자, 재귀 이용

int gcd(int a, int b) {
	return a % b == 0 ? b : gcd(b, a % b);
}

최소 공배수는 최대 공약수만 알면 되기 때문에

아래와 같이 함수를 작성할 수 있습니다.

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