[알고리즘] 최대공약수, 최소공배수 기본 & 유클리드 호제법

알고리즘 출처 : 프로그래머스
https://school.programmers.co.kr/learn/courses/30/lessons/120808

분수의 합을 구하는 문제였다.

유클리드 호제법을 모르면 for문을 사용하여 문제를 해결한다.

최대 공약수

1. max 에서 min을 나눈 나머지 값이 0이면 min값을 리턴한다.
2. min부터 2까지 for문을 돌아 max와 min을 각각 나눈 i의 나머지가 모두 0일 경우 i를 리턴한다.
3. 값이 없을 경우 1을 리턴한다.

const getGCD = (num1, num2) => {
    const max = Math.max(num1, num2);
    const min = Math.min(num1, num2);
    
    if (max % min === 0) {
        return min;
    }
    
    for (let i = min; 1 < i; i--) {
        if (max % i === 0 && min % i === 0) {
            return i;
        }
    }
    
    return 1;
}

최소 공배수

1. max에서 min을 나눈 나머지 값이 0이면 min값을 리턴한다.
2. min부터 2까지 for문을 돌아 max와 min을 각각 나눈 i의 나머지가 모두 0일 경우 max * min / i의 값을 리턴한다.
3. 값이 없을 경우 max * min의 값을 리턴한다.

const getLCM = (num1, num2) => {
    const max = Math.max(num1, num2);
    const min = Math.min(num1, num2);
    
    if (max % min === 0) {
        return max;
    }
    
    for (let i = min; i > 1; i--) {
        if (max % i === 0 && min % i === 0) {
            return max * min / i;
        }
        
        return max * min;
    }
}

유클리드 호제법의 정의를 이해하면 최대공약수, 최소공배수를 구하는 방식이 간결해진다.

유클리드 호제법의 최대공약수를 구하는 법

아래의 공식을 문자 그대로 이해하고 구현하는 것이 중요하다.

1. num1 을 num2로 나눈 나머지 값을 remainder이라고 했을때 GCD(num1, num2) 는 GCD(num2, remainder)과 같다.
2. remainder이 0이라면 그 때의 num2가 최대 공약수이다.

const getGCD = (num1, num2) => {
    const remainder = num1 % num2;
    
    if (remainder === 0) {
        return num2;
    }
    
    return getGCD(num2, remainder);
}

위 공식은 순서가 바뀌어도 동일하게 적용되며, 시간복잡도는 Olog(n)으로 줄게된다.

getGCD(16,24) === getGCD(24,16)
true

유클리드 호제법의 최대공배수를 구하는 법

아래의 공식을 문자 그대로 이해하고 구현하는 것이 중요하다.

num1과 num2를 곱한 값은 항상 최대공약수와 최소공배수를 곱한 값과 일치한다.

const getLCM = (num1, num2) => {
    return num1 * num2 / getGCD(num1, num2);
}

문제를 푸는 것도 중요하지만
문제의 핵심 알고리즘을 알고 이해하는 것이 매우 중요하다는 사실을 깨달았다.