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) 시간 복잡도로 최소공배수를 계산할 수 있다.


    반응형

    댓글