[Algorithm] 백준 알고리즘 기초 1/2 - 최대공약수와 최소공배수

최대공약수

최대공약수(Greatest Common Divisor)는 줄여서 GCD라고 쓴다.

두 수 $A$와 $B$의 최대공약수 $G$는 $A$와 $B$의 공통된 약수 중에서 가장 큰 정수이다.

최대공약수가 1인 두 수를 서로소(Coprime)라고 한다.

최대공약수를 구하는 가장 쉬운 방법은 2부터 min(A, B)까지 모든 정수로 나누어 보는 것이다.

• 기본 구현

int g = 1;
for(int i = 2; i <= min(a, b); i++) {
    if(a % i == 0 && b % i == 0) {
        g = i;
    }
}

앞의 방법보다 빠른 방법은 유클리드 호제법(Euclidean algorithm)이다.

유클리드 호제법은 $a$를 $b$로 나눈 나머지를 $r$이라고 했을 때 $GCD(a, b) = GCD(b, r)$이고, $r$이 0이면 그 때 $b$가 최대공약수임을 이용하는 것이다.

예를 들어, $GCD(24, 16) = GCD(16, 8) = GCD(8, 0) = 8$이다.

• 재귀함수를 사용해서 구현한 유클리드 호제법

int gcd(int a, int b) {
    if(b == 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

• 재귀함수를 사용하지 않고 구현한 유클리드 호제법

int gcd(int a, int b) {
    while(b != 0) {
        int r = a % b;
        a = b;
        b = r;
    }
    return a;
}

$N$개의 최대공약수

세 수의 최대공약수는 $GDC(a, b, c) = GCD(GCD(a, b), c)$와 같이 두 개의 수의 최대공약수로 바꾸어 구할 수 있다.

네 수, $N$개의 숫자도 이와 같은 식으로 계속해서 구할 수 있다.

최소공배수

최소공배수(Least Common Multiple)는 줄여서 LCM이라고 한다.

두 수의 최소공배수는 두 수의 공통된 배수 중에서 가장 작은 정수이다.

최소공배수는 GCD를 응용해서 구할 수 있다. 두 수 $A$와 $B$의 최대공약수를 $G$라고 했을 때, 최소공배수 $L = G\times{(A\div{G})}\times{(B\div{G})}$이다.