[알고리즘] 최대공약수와 최소공배수

최대 공약수와 최소 공배수를 구하는 방법은 간단합니다. 요즘은 초등학생들도 할 수 있는 소인수 분해를 통해 구하면 됩니다. 다만, 컴퓨터 프로그래밍상에서 계산하는 방식은 조금 어렵습니다. 구현상의 문제가 아닌 시간 복잡도 상으로 굉장히 오래걸리기 때문입니다. 이 때문에 나온 방법이 바로 "유클리드 호제법" 입니다. 이에 대한 자세한 설명은 여기에서 확인 가능합니다. 먼저 방법부터 설명 해 보겠습니다.

먼저 두 수 A, B가 있다고 할 때, A와 B의 최대공약수를 구하는 방식은 다음과 같습니다. ( A >= B 라고 가정하고 시작합니다. )

A 가 B로 나눴을 때 나머지가 0인가?

-> Yes : End. 최대 공약수는 B

-> No : A = A % B; Swap(A, B) // A >= B의 조건을 만족하기 위해서

다시 반복.

의외로 간단한데, 이를 코드로 나타내면 다음과 같게 표현 가능합니다.

int getLCD(int a, int b)    {
    int A = a;
    int B = b;
    
    while(A % B != 0) {
        A = A % B;
        swap(&A, &B);
    }

    return B;
}

최소공배수는 더 간단합니다. a * b / getLCD(a, b) 로 진행 해 주면 끝이기 때문입니다.

사실 최소공배수, 최대공약수를 구하는 방법은 간단하나, 이에 대한 응용 문제가 어렵습니다.

백준 2981번 문제는 최대공약수를 이용하는 문제인데, 한 번 풀어보는 것을 권유드립니다. 해답은 질문란에 가면 모두 존재하기 때문에 진행하지 않도록 하겠습니다.