최대공약수와 최소공배수, 유클리드 호제법, 기약분수

최대공약수(GCD, Greatest Common Divisor)

두 수의 공통된 약수 중 가장 큰 수를 의미한다. 예를 들어, 12와 18의 최대공약수는 6다.

• 12의 약수: 1, 2, 3, 4, 6, 12
• 18의 약수: 1, 2, 3, 6, 9, 18
• 공통된 약수: 1, 2, 3, 6 → 최대공약수는 6

최소공배수(LCM, Least Common Multiple)

두 수의 공통된 배수 중 가장 작은 수를 의미한다. 예를 들어, 12와 18의 최소공배수는 36이다.

• 12의 배수: 12, 24, 36, 48, ...
• 18의 배수: 18, 36, 54, ...
• 공통된 배수: 36, 72, ... → 최소공배수는 36

 

최소공배수와 최대공약수의 관계

두 수 a, b에 대하여 다음과 같은 관계가 성립한다:

 

LCM × GCD = a × b

 

 

유클리드 호제법

최대공약수를 구하는 가장 효율적인 알고리즘이다.

'호(互)'는 '서로'라는 뜻이고, '제(除)'는 '나누다'라는 뜻이다. 즉 '서로 나누는 방법'이라는 의미다. 두 수가 서로를 번갈아가며 나누어가는 과정이라서 이런 이름이 붙었다.

 

다음과 같은 원리로 동작한다:

1. 두 수 a, b가 있을 때 (a > b), a를 b로 나눈 나머지를 r이라 다.
2. b와 r의 최대공약수는 a와 b의 최대공약수와 같다.
3. r이 0이 될 때까지 이 과정을 반복하며, 이때 나누는 수가 최대공약수가 된다.

// 최대공약수 (GCD) 구하기 - 유클리드 호제법
function getGCD(a, b) {
    while (b !== 0) {
        const temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

// 최소공배수 (LCM) 구하기
function getLCM(a, b) {
    return (a * b) / getGCD(a, b);
}

// 사용 예시
const num1 = 12;
const num2 = 18;

const gcd = getGCD(num1, num2);
const lcm = getLCM(num1, num2);

console.log(`${num1}과 ${num2}의 최대공약수: ${gcd}`); // 6
console.log(`${num1}과 ${num2}의 최소공배수: ${lcm}`); // 36


/*
최대공약수를 구할 때, 반드시 제수(나누는 수)가 피제수(나눠지는 수)보다 작을 필요는 없다.
다만 제수가 피제수보다 큰 경우, 몫이 0이 되는 경우가 반드시 있으므로, 한 단계가 추가되어 비효율적이 된다.

[제수가 작은 경우]
36 = 24 × 1 + 12    // 1단계
24 = 12 × 2 + 0     // 2단계
-> 2단계 필요

[제수가 큰 경우]
24 = 36 × 0 + 24    // 1단계 (불필요)
36 = 24 × 1 + 12    // 2단계
24 = 12 × 2 + 0     // 3단계
-> 3단계 필요

그렇다면 최대공약수를 구하는 로직 이전에 크기를 비교하여 제수와 피제수를 상호교체하는 로직이 필요할까?
그렇지는 않을 것 같다.

/ 방법 1: swap 사용
function gcdWithSwap(a, b) {
    if (a < b) {
        [a, b] = [b, a];    // 메모리 공간 3개 필요 (임시 저장 공간 포함)
    }
    while (b !== 0) {
        let r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 방법 2: 그냥 나누기
function gcdWithoutSwap(a, b) {
    while (b !== 0) {
        let r = a % b;      // 메모리 공간 1개
        a = b;
        b = r;
    }
    return a;
}

swap 방식

장점: 불필요한 나눗셈 연산 1회 방지
단점: 추가 메모리 공간 필요, 조건문 검사 필요


그냥 나누기

장점: 코드 단순, 추가 메모리 불필요
단점: 불필요한 나눗셈 1회 발생 가능



위처럼 메모리 공간에 접근하여 값을 변경하는 비용보다 정수를 정수로 나누는 비용이 저렴하기 때문이다.

차라리 두 수가 반드시 정수임을 확인하는 로직을 추가하는 것이 나아보인다.

 

 

유클리드 호제법을 사용하지 않고 최대공약수를 구하는 방식을 생각해 보자

// 시간복잡도: O(N), N은 작은 수의 크기
function getGCD1(a, b) {
    let gcd = 1;
    for (let i = 1; i <= Math.min(a,b); i++) {
        if (a%i===0 && b%i===0) gcd = i;
    }
    return gcd;
}

// 혹은 위처럼 함수를 분리하지 않고 사용한다면
    for (let i = 1; i <= Math.min(a,b); i++) {
        if (a%i===0 && b%i===0) n = i;
    }

 

직관적이지만 수가 커졌을 때 순회 횟수가 증가하는 문제가 있다. 그에 비해 유클리드 호제법을 사용하면 순회 횟수를 극적으로 감소시킬 수 있다.

// 1071과 1029의 최대공약수 구하기

// 첫 번째 방법
- 1부터 1029까지 모든 수 확인 필요
- 1029번의 반복문 실행

// 유클리드 호제법
1071 = 1029 × 1 + 42
1029 = 42 × 24 + 21
42 = 21 × 2 + 0
- 단 3번의 연산으로 완료

 

 

 

유클리드는 어떻게 이 방법을 깨닫게 됐을까?

 

고대 그리스에서는 수를 선분의 길이로 표현하였다.

선분 A (길이 21)
|----------------------|

선분 B (길이 15)
|-----------------|

 

두 선분의 공통 측정 단위(공약수)를 찾기 위해, 긴 선분에서 짧은 선분을 반복적으로 빼보는 과정을 시도했을 것으로 추측

21에서 15를 한 번 뺌 → 6 남음

A(21): |----------------------|
B(15): |-----------------|
남은 길이(6): |------|

이제 15에서 6을 반복해서 뺌 → 3 남음

B(15): |-----------------|
6: |------|
6: |------|
남은 길이(3): |---|

6에서 3을 반복해서 뺌 → 0 남음

6: |------|
3: |---|
3: |---|

 

이 과정에서 마지막에 남은 길이 3이 두 선분을 정확히 측정할 수 있는 가장 큰 단위(최대공약수)가 된다는 것을 발견하였다.

 

21 = 3 × 7

15 = 3 × 5

 

이렇게 기하학적인 뺄셈 과정을 대수적인 나눗셈으로 바꾸어 표현한 것이 지금의 유클리드 호제법이 되었다. 선분의 길이를 비교하고 빼는 과정에서, 두 수의 최대공약수를 찾는 규칙성을 발견한 것으로 추측할 수 있다.

 

 

 

기약분수 구하기

분자와 분모의 최대공약수(GCD)를 구한다. 최대공약수는 두 수를 나눌 수 있는 최대의 값이다. 따라서 분자와 분모를 최대공약수로 나누면 분자와 분모는 서로소가 된다.

 

즉, 분자와 분모를 두 수의 최대공약수(GCD)로 나누면 기약분수를 만들 수 있다.

24/36을 기약분수로 만들기

1. 먼저 24와 36의 최대공약수를 구함
   36 = 24 × 1 + 12
   24 = 12 × 2 + 0
   -> 최대공약수는 12

2. 분자와 분모를 12로 한 번 나눔
   24 ÷ 12 = 2 (분자)
   36 ÷ 12 = 3 (분모)
   -> 2/3이 기약분수

 

 

 

3개 이상의 수의 최대공약수와 최소공배수를 구하는 경우

 

당황할 필요 없다. 먼저 임의의 두 수의 최대공약수를 구한다. 그렇게 계산된 최대공약수와 다른 수의 최대공약수를 구하면 된다.

예를 들어 [12, 18, 24]의 최대공약수를 구하는 경우, 12와 18의 최대공약수를 구하면 6이다. 그리고 다시 6과 24의 최대공약수를 구하면 된다. (이 역시 6이 된다)

GCD(12, 18, 24)의 경우:
1. GCD(12, 18) = 6
2. GCD(6, 24) = 6

LCM(12, 18, 24)의 경우:
1. LCM(12, 18) = 36
2. LCM(36, 24) = 72


// GCD:최대공약수, LCM:최소공배수

 

가독성을 위해 함수에 관한 코드를 아래 배치하였다. 

// 두 수의 GCD
function getGCD(a, b) {
    while (b !== 0) {
        let r = a % b;
        a = b;
        b = r;
    }
    return a;
}

// 두 수의 LCM
function getLCM(a, b) {
    return (a * b) / getGCD(a, b);
}

// 여러 수의 GCD
function getMultipleGCD(numbers) { // 배열이 매개변수로 입력됨
    return numbers.reduce((acc, cur) => getGCD(acc, cur));
    // 초깃값이 설정돼 있지 않으므로, 최초에는 입력 배열의 첫 번째 원소가 초깃값으로 설정됨
    // 만약 [12, 18, 24]라면 최초에는 12가 초깃값으로 설정되며, cur는 18이 된다.
    // 왜 cur가 12가 아니고 18이냐고?
    // 자바스크립트의 reduce 함수는 초기값이 없을 때:
	// acc는 자동으로 배열의 첫 번째 요소(0번 인덱스)로 설정된다.
	// cur는 자동으로 배열의 두 번째 요소(1번 인덱스)부터 설정된다.
    // 즉, 초깃값을 명시적을 설정했다면 cur가 0번 인덱스부터 시작했겠지만,
    // 여기서는 초깃값을 설정하지 않았으므로 cur가 1번 인덱스부터 시작하는 것이다.
    // 따라서 acc는 1번 원소(18)와의 연산을 통해 6으로 교체되고, 2번 원소(24)와의 연산을 통해 다시 6으로 교체된다. 
    // 리듀스 함수는 '누적' 또는 '교체'의 연산을 통해 '하나의 값(단일값)'을 구하는 데 사용되는데,
    // 주로 누적값을 찾는데 사용되지만 여기서는 최종 교체된 값을 찾는 데 사용된 것이다.
}

// 여러 수의 LCM
function getMultipleLCM(numbers) {
    return numbers.reduce((acc, cur) => getLCM(acc, cur));

}

// 사용 예시
const numbers = [12, 18, 24];
console.log(getMultipleGCD(numbers));  // 6
console.log(getMultipleLCM(numbers));  // 72