12. 최대공약수 (Greatest Common Divisor, GCD) Codility Lesson 한국어 정리본 (JavaScript ver.)

최대공약수(GCD)란?

두 개의 정수 a, b의 최대공약수(GCD)는 두 수를 동시에 나눌 수 있는 가장 큰 정수 를 의미한다.

---

1. O(n) 시간 복잡도의 유클리드 알고리즘 (뺄셈 방식)

JavaScript 코드:

function gcdSubtraction(a, b) {
    if (a === b) return a;
    return a > b ? gcdSubtraction(a - b, b) : gcdSubtraction(a, b - a);
}

---

2. O(log n) 시간 복잡도의 유클리드 알고리즘 (나머지 방식)

JavaScript 코드:

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

이 방법은 빠르고, 대부분의 프로그래밍 언어에서 기본적으로 제공된다.

---

3. 최소공배수(LCM) 계산

최소공배수(LCM)는 두 수 a, b의 최소공배수를 구하는 방법이다.

function lcm(a, b) {
    return (a * b) / gcd(a, b);
}

이 함수는 O(log n) 시간 복잡도로 최소공배수를 계산할 수 있다.

---