유클리드 호제법 - 최대 공약수

코테를 풀다보면 최대 공약수 문제를 자주 접하게 된다.

n,m 이 주어졌을때 최대 공약수를 구하기 위해 

i = 1 부터 n, m 중 작은 값에 도달할 때까지 + 1 을 하면서 두 값 모두 나누어지는 가장 큰 수를 찾을 수도 있겠으나

이 경우 n 까지 무조건 반복해야하기 때문에 O(n) 의 시간 복잡도를 갖는다. 

• 완전 탐색

function getGcd(n, m) {
    let min = Math.min(n, m);
    let gcd = 1;
    for (let i = 1; i <= min; i++) {
        if (n % i === 0 && m % i === 0) {
            gcd = i;
        }
    }
    return gcd;
}

 

 

• 유클리드 호제법

이 방법을 쓰면 재귀적으로 짧은 코드로 빠르게 최대 공약수를 찾을 수 있다.

이 경우 시간 복잡도는 O(logn)이다. 

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

---

그동안 이 코드를 몇번 봐왔지만, 문제를 마주했을때 아 그거 어떻게 작성했더라 ;; 하면서 바로 적용하기가 쉽지 않았다.

그 이유는 공식의 원리를 모르고 있기 때문이었겠지?

 

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

 

두 수의 최대 공약수는 이러한 성질을 갖는다.

다시 말하면 a를 b로 나눈 나머지 r에 대해, b를 r로 나눈 나머지가 같다는 뜻이다.

그리고 b === 0 이 되는 시점의 a 가 두 수가 나누어 떨어지는 최대 공약수가 된다.

 

무려 기원전 300년전에 유클리드에 의해 밝혀졌다고 하니 정말 신기하다.

이제 원리를 알았으니 담부턴 바로 적용할 수 있기를!

 

참고 블로그

https://heoseongh.github.io/algorithm/Euclidean/