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

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

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

가로등 설치

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

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

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)

from http://forgottenknowledge.tistory.com/119 by ccl(A) rewrite - 2021-09-19 10:27:52