'최대공약수 구하기 알고리즘'에 해당되는 글 1건

두 자연수의 최대공약수를 구해서 푸는 문제가 많으므로 메모...

아래의 문제를 최대공약수(gcd)를 이용해서 풀었다.

가로 1, 세로 1 크기의 작은 정사각형으로 이루어진 큰 사각형의 대각선 두 꼭짓점을 선분으로 이었을 때, 선분이 통과하는 작은 정사각형 교차점의 갯수를 구해야 했다. 이때, 바로 큰 사각형의 가로(w), 세로(h) 길이의 최대공약수(gcd(w, h))가 교차점의 갯수이다.

선분이 통과하는 작은 사각형의 갯수는

- 교차점이 있는 경우: w + h - gcd(w, h)

- 교차점이 없는 경우: w + h - 1

https://programmers.co.kr/learn/courses/30/lessons/62048

function getGcd (n, m) {
    let gcd = 0
    let max = Math.max(n ,m)
    let min = Math.min(n, m)
    while (true) {
        // 최대공약수
        const quot = Math.floor(max/min)
        const remains = max%min
        if (remains === 0) {
            gcd = min
            break
        } else {
            max = min
            min = remains
        }
    }
    return gcd
}

유클리드 호제법