알고리즘 :: 가로등 설치, 유클리드 호제법, 최대공약수

알고리즘 공부하며 배운내용

 

 

가로등 설치

길 시작점부터 가로등이 설치되어 있다.

가로등을 설치해서 각 가로등 사이의 길이를 같게 만들자

 

0m 3m 9m 12m

이 경우는 6m에 가로등 설치해주면 각 사이가 3m가 되서 같아지겠네

 

간단히 생각해보면 각 가로등간의 거리를 구해서 거리를 비교해볼 수 있을 것 같다.

하지만 여기서 최대공약수를 이용하면 된다고 한다.

일정한 간격을 유지하게 한다는 말은 규칙이 생긴다는 말 같다.

3 6 9 12

여기서 간격은 3m 그럼 최대공약수는? 3이다

다시

4 8 12 16

여기서 간격은 4m, 최대 최대공약수는? 4다

 

그래서 최대공약수를 구하고, 배수를 해주며 빠진곳에 가로등을 설치해주면 되는 것 같다.

더 나아가 최대공약수를 구하는 방법은 약수를 구하고 제일 큰 녀석을 구하는 방법보다,유클리드 호제법을 이용해보자

 

 

유클리드 호제법(Euclidean Algorithm)

나머지 연산을 이용해서 나머지가 안나올 때까지 하면 최대공약수를 발견할 수 있다.

 

만약 8과 30의 최대공약수를 구한다고 생각해보자,

그럼 큰 수 30에 8로 나머지 연산을 시킨다(나머지 연산 결과가 0이 나올 때까지 반복한다.)

30 % 8 = 6

이번에는 8과 6을 잡고 나머지 연산을 시작한다

8 % 6 = 2

한번 더

6 % 2 = 0

나왔다 0 그럼 여기서 최대공약수는 마지막으로 나눈 값으로 사용한 2다

 

 

재밌어서 다른 예로 한번 더 해보자

4와 8이 있다

8 % 4 = 0

한 큐에 끝났네? 그럼 4가 최대공약수

 

더 자세한 방법은 잘 정리해주신 블로그 참고 => velog.io 링크 

 

 

입력

0 3 9 12

시작점부터 가로등의 거리가 들어온다

 

 

출력

몇 개의 가로등이 필요한지 알아본다

 

 

코드

// VSCode에서 JavaScript 테스트 하기위한 코드
// 메모장에 테스트 케이스 넣고 lamppost.txt로 저장했다.
let fs = require('fs')
let input = fs.readFileSync('lamppost.txt').toString().split(' ')

// 최대공약수
let gcd = showGcd(+input[1], +input[2])

let answer = 0

// 최대공약수 구하는 함수
function showGcd(a, b) {
    if(a === 0) {
        return b
    }
    else if(b === 0) {
        return a
    }
    else if(a > b) {
        return showGcd(b, a)
    }
    return showGcd(b % a, a)
}

// 최대공약수랑 input 배열이랑 비교
for(let i = 0; i <= +input[input.length - 1]; i+=gcd) {
	
    // input에 최대공약수 배수해준게 없으면 answer 1증가
    if(!input.includes(i.toString())) {
        answer++
    }
}

console.log(answer)