• 최대공배수 gcd
• 서로소 disjoint
• 기약분수 reduced fraction

유클리드 호제법 #

• 최대공약수: 두 수가 공통으로 가지는 가장 큰 약수
  • 약수: 어떤 수를 나머지 없이 나눌 수 있는 자연수
• 호제법: 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 알고리즘을 나타냅니다. (互除法)

유클리드 호제법은 기록상 가장 오래된 알고리즘입니다. 두 개의 자연수 a, b에 대해 a를 b로 나눈 나머지를 r이라고 할 때, (단, a > b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이 성질을 이용해 b를 r로 나눈 나머지 r'를 구하고 r을 r'로 나누는 과정을 반복한다. 나머지가 0이 되었을 때 나누는 수가 a, b의 최대 공약수이다.

예시 #

48, 18의 최대공약수를 위 과정을 통해 구해보겠습니다.

$48 > 18$이므로

48 % 18 = 12

여기서 r = 12가 됩니다. 48과 18의 최대공약수는 18과 12의 최대공약수와 같습니다.

18을 12로 나눈 나머지를 구합니다.

나머지는 6이 됩니다. 따라서 r' = 6이 됩니다.

12와 6이 남았으므로 12를 6으로 나눈 나머지를 구합니다. 12 / 6은 나누어 떨어지므로 나머지가 0입니다.

이 때, 6으로 나누었으므로 48과 18의 최대 공약수는 6입니다.

이해 #

두 수에 대해 나머지를 구하는 것의 의미 #

• 구하고자 하는 것은 두 수의 최대공약수입니다.

약수는 어떤 수를 나머지 없이 나눌 수 있는 수이므로 두 수의 공통된 약수 중 가장 큰 값을 찾는 것입니다.

6과 4의 최대공약수를 구해보겠습니다.

• 6과 4의 나머지를 구하기

여기 아래에 6칸, 4칸짜리 나무토막이 있습니다. 이는 위의 수를 대신 할 것입니다.

|-|-|-|-|-|-| (6)
|-|-|-|-| (4)

6칸짜리 나무토막을 4칸짜리 나무토막으로 나눈 나머지를 구하겠습니다.

2칸이 나왔습니다.
|-|-| (2)

이제 6칸짜리 나무토막은 냅두고,

4칸과 2칸짜리만 생각하겠습니다.

|-|-|-|-| (4)
|-|-| (2)

2칸짜리로 4칸짜리 나무토막을 나누면, 나누어 떨어집니다.

|-|-| (2) |-|-| (2)
|-|-| (2)

여기서 나누어 떨어지게끔 하는 약수인 2가 6과 4의 최대공약수입니다. 최대공약수인 2는 두 나무토막 (6), (4)를 나누어 떨어지게 하는 최대공약수입니다.

따라서, 두 수를 서로 나누어 나머지를 구하는 것은 나누어 떨어질때까지 나눌 수 있는 약수를 찾기 위해 나눈 것입니다.

/** 
 * a에는 b를, b에는 a % b를 b가 나누어 떨어질때까지..
*/
function gcd(a, b) {
    if(b === 0) {
        return a;
    } else {
        return gcd(b, a % b);
    }
}

function gcd(a, b) {
    while (b !== 0) {
        let temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

이 알고리즘의 시간복잡도는

$O(log(min(a,b)))$입니다.

유클리드 호제법을 통해 서로소 구하기 #

서로소는 두 수의 약수가 1인 두 수를 의미합니다.

위에서 구한 최대공약수를 통해, 두 수의 최대공약수가 1인 경우 두 수는 서로소입니다.

function isDisjoint(a, b){
    if(gcd(a, b) === 1) return true;
    return false;
}

유클리드 호제법을 통해 기약분수 구하기 #

기약분수는 분모 분자의 최대공약수가 1인 분수입니다. 예를 들어 $4 / 2$ 라는 분모는 둘의 최대공약수가 2이므로 기약분수가 아닙니다.

약분을 통해 $2 / 1$로 나타낸다면 이제 기약분수라고 할 수 있습니다.

기약분수를 구하는 과정에도 유클리드 호제법으로 구한 최대공약수가 사용되었습니다. 이를 코드로 나타내면 아래와 같습니다.

function reducedFraction(a, b){
    const divisor = gcd(a, b);

    return {
        numerator: a / divisor,
        denominator: b / divisor
    };
}

유클리드 호제법을 통해 유한소수 판별하기 #

• 소인수분해의 소인수란 자연수의 약수중 소수인 수를 가리킵니다.

• 소인수분해는 1보다 큰 자연수를 소인수들의 곱으로 나타내는 것입니다. 예를 들어 합성수인 6을 소인수분해하면 2 * 3으로 나타낼 수 있습니다.

• 유한소수와 무한소수

  • 유한소수는 분모의 소인수가 2, 5인 경우입니다.

  • 무한소수는 분모의 소인수가 2, 5가 아닌 경우입니다.

  • 예를 들어 1 / 3을 소수로 표현하면 0.3333...입니다.

    • 분수를 소수로 치환할 때, 1을 10의 자리로 맞추고 3으로 나누면 나누어 떨어지지 않습니다.
      • 이는 10진수의 특성으로 이로인해 1 / 3은 무한소수입니다.

  • 1 / 2의 경우 0.5입니다.

function isFiniteDecimal(a, b){
   const reduced = reducedFraction(a, b);
   let denom = reduced.denominator;

    while (denom % 2 === 0) {
        denom /= 2;
    }

    while (denom % 5 === 0) {
        denom /= 5;
    }

     return denom === 1;
}

2나 5로 계속 나누어 분모가 1이 되었다면 소인수가 2나 5만 있다는 것입니다.