GCD의 고찰 (최대공약수)
1.최대공약수 개념
2.코드 표현법
유클리드 호제법: Euclidean algorithm
알고리즘의 피타고라스의 정리 아닐까 싶을정도로
이건 알고 넘어가자
일단 코드 부터 보면서 해보자
function gcd(m, n) {
if (m % n === 0) return n;
return gcd(n, m % n);
}
두수가 입력이 되면
나머지가 0이 된다면 n 을 출력하고
0이 안된다면
재귀함수에 자리를 바꾸고, 나머지를 넣어줘라
그리고 나눠떨어지면 그것이 최대공약수 임;
삼항연산자로 표현도 가능함
const gcd = (m, n) => m % n === 0 ? n: gcd(n, m % n);
function divideChocolateStick(M, N) {
// TODO: 여기에 코드를 작성합니다.
//최대공약수 찾는 함수
const GCD = (m, n) => {
if(m % n === 0) return n;
else return GCD(n, m % n);
}
let result = [];
//인원수를 차례대로 늘려가면서 구한다.
// 최대공약수 까지만.
// 나아가 제곱근까지만 구하는 반복도 가능하다.
const gcd = GCD(M,N)
for(let i = 1; i <= Math.floor(Math.sqrt(gcd)); i++){
if(gcd % i === 0){
result.push([i, M / i, N / i])
if(i * i < gcd)
let j = gcd / i
result.push([j, M / j, N / j])
}
}
return result;
}
function divideChocolateStick(M, N) {
// TODO: 여기에 코드를 작성합니다.
const GCD = (M,N) => {
if(M % N === 0){
return N;
} else {
return GCD(N , M % N)
}
}
const gcdNum = GCD(M,N)
let result = [];
let sqrt = Math.floor(Math.sqrt(gcdNum));
//여기서 i는 사람임
for(let i = 1; i <= sqrt; i++){
if(gcdNum % i === 0){
result.push([i , M / i, N / i]);
if((i * i) < gcdNum){
const j = GCD(M,N) / i
result.push([j , M / j, N / j])
}
}
}
result.sort((a,b) => a[0] - b[0])
return result;
}
Author And Source
이 문제에 관하여(GCD의 고찰 (최대공약수)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@sud665/GCD의-고찰-최대공약수저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)