'유클리드 호제법 알고리즘'에 해당되는 글 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

 

코딩테스트 연습 - 멀쩡한 사각형

가로 길이가 Wcm, 세로 길이가 Hcm인 직사각형 종이가 있습니다. 종이에는 가로, 세로 방향과 평행하게 격자 형태로 선이 그어져 있으며, 모든 격자칸은 1cm x 1cm 크기입니다. 이 종이를 격자 선을

programmers.co.kr

 

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
}

 

유클리드 호제법

블로그 이미지

망원동똑똑이

프로그래밍 지식을 자유롭게 모아두는 곳입니다.

,