유클리드 알고리즘

유클리드 알고리즘이란 두 수의 최대 공약수(GCD)를 구하는 알고리즘입니다.

이 알고리즘의 핵심은 다음 성질에 기반합니다.

"두 수 $a, b$ ($a > b$)가 있을 때, $a$와 $b$의 최대공약수는 $b$와 $a$를 $b$로 나눈 나머지($r$)의 최대공약수와 같다."

$GCD(a, b) = GCD(b, a \pmod b)$

GCD(a, b) = GCD(b, a % b)

[GCD(1071, 462) 구하기]

1단계: 1071을 462로 나눕니다.

• $1071 = 462 \times 2 + 147$ (나머지: 147)

2단계: 이전의 나누는 수(462)를 나머지(147)로 나눕니다.

• $462 = 147 \times 3 + 21$ (나머지: 21)

3단계: 이전의 나누는 수(147)를 나머지(21)로 나눕니다.

• $147 = 21 \times 7 + 0$ (나머지: 0)

나머지가 0이 되었으므로, 마지막 나누는 수인 21이 최대공약수입니다.

파이썬 코드 예시

def gcd(a, b):
    while b != 0:       # b가 0이 될 때까지 (나머지가 없을 때까지) 반복합니다.
        a, b = b, a % b # (중요!) a에는 b를 넣고, b에는 'a를 b로 나눈 나머지'를 넣습니다.
    return a            # b가 0이 되면, 그때의 a가 최대공약수입니다.

자바스크립트 코드 예시

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

// 사용 예시
console.log(gcd(1071, 462)); // 출력: 21

자바스크립트 코드 예시 2 (ES6+)

const gcd = (a, b) => {
    while (b !== 0) {
        [a, b] = [b, a % b]; // 구조 분해 할당 적용
    }
    return a;
};

프로그래머스 Lv.0 분수의 덧셈

function fnGCD(a, b) {
    return a % b ? fnGCD(b, a % b) : b
}

function solution(numer1, denom1, numer2, denom2) {
    var answer = [];
    
    let denom = denom1*denom2;
    let numer = numer1*denom2 + numer2*denom1;
    let GCD = fnGCD(numer, denom);
    
    denom = denom/GCD;
    numer = numer/GCD;
    
    answer = [numer, denom];
    
    return answer;
}