자바스크립트 코딩테스트 강좌, 최대 공약수 구하기

주제: 최대 공약수 구하기

문제 설명

두 개의 정수 a와 b가 주어질 때, 두 수의 최대 공약수(GCD)를 구하는 함수를 작성하세요.
최대 공약수는 두 수의 공통된 약수 중 가장 큰 수를 의미합니다.

입력 및 출력 형식

  • 입력: 두 개의 양의 정수 a, b (1 ≤ a, b ≤ 109)
  • 출력: 두 수의 최대 공약수

예시

        입력: 48, 18
        출력: 6

문제 접근 방법

최대 공약수를 구하는 방법은 여러 가지가 있지만, 유명한 유클리드 알고리즘을 활용하면 효율적으로 해결할 수 있습니다.
이 알고리즘은 다음과 같은 기본 원리를 가지고 있습니다:

  • 두 정수 a와 b의 최대 공약수는 b가 0이 될 때까지 반복적으로 a % b를 구하여 구할 수 있습니다.
  • 즉, GCD(a, b) = GCD(b, a % b)이며, b가 0이 될 때 a가 최대 공약수입니다.

유클리드 알고리즘 설명

유클리드 알고리즘은 다음의 단계로 작동합니다:

  1. a와 b를 준비합니다. 만약 b가 0이 아니면, 다음 단계를 진행합니다.
  2. r = a % b를 계산하여 새로운 나머지를 구합니다.
  3. a의 값은 b로, b의 값은 r로 업데이트합니다.
  4. 이 과정을 b가 0일 때까지 반복합니다.
  5. 결과적으로, a가 최대 공약수가 됩니다.

자바스크립트 구현

유클리드 알고리즘을 자바스크립트로 구현한 코드는 다음과 같습니다:

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

        // 테스트
        const result = gcd(48, 18);
        console.log(result); // 6

시간 복잡도 분석

유클리드 알고리즘의 시간 복잡도는 O(log(min(a, b)))입니다.
이는 두 수의 비율에 따라 성능이 좋은 편이며, 특히 큰 수를 다룰 때 효율적인 방법입니다.

추가 문제 및 연습

최대 공약수를 구하는 방법에 익숙해졌다면, 아래의 문제를 풀어보세요:

  • 두 개의 정수가 주어졌을 때, 이들의 최소 공배수를 구하는 함수를 작성하세요. (최소 공배수 LCM(a, b) = a * b / GCD(a, b)임을 사용하세요.)
  • 주어진 배열에서 모든 원소의 최대 공약수를 구하는 함수를 작성하세요.

결론

이번 글에서는 자바스크립트를 이용하여 최대 공약수를 구하는 문제를 해결해 보았습니다.
유클리드 알고리즘을 통해 효율적인 문제 해결 방안을 익힐 수 있었습니다.
이러한 기본적인 알고리즘들은 코딩 테스트와 실무에서 자주 사용되므로, 충분한 연습이 필요합니다.

참고 자료