'알고리즘-문제'에 해당되는 글 2건

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

아래의 문제를 최대공약수(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
}

유클리드 호제법

프로그래머스에서 애증의 코딩테스트...를 준비하는 도중 1단계 문제임에도 성능때문에 계속 실패하는 문제에 부딪혔다.

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

소수를 구하는 함수를 짠 후, 모든 숫자에 대해 소수인지 판별하여 카운팅을 하는 방식으로 짯더니 실패.

검색결과 에라토스테네스의 체를 사용하여 구하여야 1부터 아주 큰 수 까지의 숫자 중에서 소수의 집합을 구할 때 효율적이라고 한다.

https://ko.wikipedia.org/wiki/%EC%97%90%EB%9D%BC%ED%86%A0%EC%8A%A4%ED%85%8C%EB%84%A4%EC%8A%A4%EC%9D%98_%EC%B2%B4

먼저 숫자 몇까지의 소수집합을 구할지 배열공간을 만들어 놓은 후, 2부터 1씩 증가시키며 2배수 이상의 숫자들을 지워준다. 이미 지워진 숫자는 건너 뛴다. 아래는 자바스크립트로 짠 코드

function solution(n) { 
    let arr = [] 
    // 1은 소수가 아니고, 2부터 소수가 될 수 있으므로, 2부터 구하고자 하는 값까지의 배열을 만든다. 
    for (let i = 2; i <= n; i++) { 
        arr[i] = i 
    } 
    // 2부터 시작해서 2배수 이상의 숫자를 모두 지우되, 이미 지워진 숫자는 건너 뛴다. 
    for (let i = 2; i <= n; i++) { 
        for (let j = i + i; j <= n; j += i) { 
            if (arr[j] === 0) { 
                continue 
            } 
            arr[j] = 0 
        } 
    } 
    return arr.filter((item) => item !== 0).length 
}