정수론

최대공약수와 최소공배수

개요

 이 전 토픽에서 나머지가 가지는 특징와 약수/배수와의 관계에 대해서 설명했습니다. 이번 토픽에서는 조금 특수한 수들인 최대공약수와 최소공배수를 빠르게 계산할 수 있는 알고리즘을 설명할까 합니다. 먼저 최대공약수의 정의는 아래와 같습니다.

 최대공약수(最大公約數)란, 0이 아닌 두 정수나 다항식의 공통되는 약수 중에서 가장 큰 수를 말한다. 두 정수 ab의 최대공약수를 기호로 gcd(a,b)로 표기한다. (위키피디아 발췌)

 

 최소공배수최대공약수와는 반대로, 두 정수가 공통적으로 가지는 배수 중 가장 작은 값을 의미합니다. 최소공배수최대공약수와 밀접한 관계가 있는데, 정수 a, b의 최대공약수 G = gcd(a, b)에 대하여 아래의 식을 만족하는 정수 xy가 존재합니다.

 a = Gx, b = Gy (단, x, y는 정수)

 이 때 a * b = G*G*x*y 임을 알 수 있고, G는 두 수의 최대 공약수이며 xy서로소인 관계를 가집니다. 집합적으로 생각하면, ab의 합집합은 G, x, y이고 이 세 수를 곱한 G*x*y최소공배수가 됨을 알 수 있습니다. 그러므로 두 수의 최소공배수 L = lcm(a, b)L= lcm(a, b)= a * b / gcd(a, b)이 성립합니다.

 

 이번 토픽에서는 최대공약수를 구하는 알고리즘을 소개합니다. 

 

Brute Force

 가장 단순하고 직관적인 방법을 생각해봅시다. 

두 정수 a와 b가 있다고 할 때에, a의 약수 이면서 b의 약수인 수 중 최대값이 바로 최대공약수가 됩니다. 그렇다면 우리는 [1, min(a, b) ] 범위에서 두 수 모두의 약수가 되는 값들을 찾아 그 중 최대값을 구하는 방법을 생각해 볼 수 있습니다. 이를 코드로 구현하면 아래와 같습니다.

int get_gcd(int a,int b)
{
    int max_div = 1;      //가장 큰 공약수를 저장할 변수
    int range = min(a, b);//두 수 중 작은 값 까지만 조사
    for(int i=1; i<=range; i++)
    { //i부터 공약수를 찾는다.
        if( a % i == 0 && b % i == 0)
        { // 두 수 모두의 약수일 경우
            max_div = i; //갱신 (i는 점점 증가하므로)
        }
    }
    return max_div;
}

   위의 알고리즘은 두 정수 a, b에 대하여 O( min(a,b) )의 시간복잡도를 가지게 됩니다. 어떻게 하면 조금 더 빠른 방법을 찾을 수 있을까요?  조금 잔머리를 굴려봅시다. 위의 알고리즘은 1부터 range까지 공약수를 찾아 그 중 마지막에 발견한 공약수를 반환합니다. 그렇다면 range부터 1까지 역순으로 탐색하여 가장 처음 발견된 공약수가 결국 최대 공약수가 됨을 알 수 있습니다.

int get_gcd(int a,int b)
{
    int max_div = 1;      //가장 큰 공약수를 저장할 변수
    int range = min(a, b);//두 수 중 작은 값 까지만 조사
    for(int i=range; i>=1; i--)
    { //i부터 공약수를 찾는다.
        if( a % i == 0 && b % i == 0)
        { // 두 수 모두의 약수일 경우
            max_div = i;  //저장 후 탈출
            break; //i는 점점 감소하므로, 더이상 볼 필요가 없다.
        }
    }
    return max_div;
}

 이 방법을 사용하면 조금 더 빠를 것 같습니다. 하지만 이 알고리즘의 경우도 결국엔 a와 b가 서로소인 경우에는 모든 수를 검사하게 되므로, 위의 알고리즘과 똑같은 시간복잡도를 가집니다.

  빠르게 최대공약수를 계산하는 알고리즘인 유클리드 호제법에 대해서 알아봅시다.

 

 

유클리드 호제법

 유클리드 호제법 알고리즘을 사용하면 최대 공약수를 빠르게 계산할 수 있습니다. 유클리드 호제법에 대한 자세한 정보는 링크를 참고해주세요. 

 유클리드 호제법을 간략히 요약하면 아래와 같습니다. 

 f(a, b) = gcd(a, b)라 합시다. 이 때 a mod b = 0 이라면, f(a, b) = b임이 자명함을 알 수 있습니다. 이 때 a mod b0이 아닌 경우, f(a, b) = f(b, a mod b)가 성립하고, 이를 유클리드 호제법이라고 합니다.

 두 정수 a와 b에 대하여 예를 들어봅시다. f(18, 12)의 경우 18 mod 12 = 6이므로,  f(18, 12) = f(12, 6)이 성립합니다. 이 때 12 mod 6 = 0이 성립하므로 f(18, 12) = f(12, 6) = gcd(12, 6) = 6 이 성립합니다.

 유클리드 호제법은 다양한 방식으로 구현할 수 있습니다. 아래의 방식 중 편한 방식을 사용하시면 될 것 같습니다.

int gcd(int a,int b)
{ //반복문을 이용한 방법
    int mod = a % b;
    while(mod > 0)
    {
        a = b;
        b = mod;
        mod = a % b;
    }
    return b;
}

int gcd2(int a,int b)
{ //재귀 함수형
    if( a % b == 0 )
        return b;
    else
        return gcd2(b, a % b);
}

int gcd3(int a, int b)
{ //삼항 연산자 축약형 
    return (a % b == 0 ? b : gcd3(b,a%b));
}

 이러한 유클리드 호제법은 두 정수 ab에 대하여 근사적으로 O( log2(min(a, b)) ) 시간복잡도를 가지는 알고리즘입니다. 어떻게 이러한 시간 복잡도에 근사하는 지는 나머지 연산의 성질을 생각해보시면 이해하기 쉽습니다.

 a mod b0이 아닌 경우, f(a, b) = f(b, a mod b)이 성립한다고 했습니다. 이 때 a mod b라는 값은 [0, b-1]이라는 범위를 가지게 되며, 평균적으로는 해당 범위의 중간값을 가지게 됨을 알 수 있습니다. 이 처럼 매 번 f의 재귀식으로 이어질 때 마다 나머지 연산을 통해 수의 범위가 줄어들며, 그 범위는 평균적으로 전 범위의 절반에 해당하게 됩니다. 위 과정을 통해 통계적으로 탐색하는 수 범위가 대략 절반씩으로 감소하여 위의 시간 복잡도를 근사하게 가질 수 있게 됩니다.

 단 위의 설명은 이해를 돕기위해서 한 대략적인 설명입니다.

 또한 유클리드 호제법 알고리즘은 a와 b중 큰 수를 표현하기 위한 비트 수 n에 대해 Θ(n)회의 나눗셈으로 최대공약수를 구할 수 있다. 라고 알려져 있으며, 증명 방법은 찾아보시면 공부가 될 것 같습니다.

 

댓글

댓글 본문
작성자
비밀번호
  1. 임승현
    뭐지?
  2. 망원경
    우왕 잘보고 갑니다. 여러번 방문했는데 댓글을 못남겼네요
  3. 잘보고 갑니다. 설명이 정말 쉽게 되어있어 이해하기 쉽네요^^
  4. algoism
    감사합니다 :) 뿌듯하네요
    대화보기
    • Seryang Choe
      감사합니다. 덕분에 이해가 잘 되었습니다!
    버전 관리
    코딩몬스터
    현재 버전
    선택 버전
    graphittie 자세히 보기