https://school.programmers.co.kr/learn/courses/30/lessons/12940
최대공약수, 최소공배수란
최대공약수(GCD) = 2부터 min(숫자1, 숫자2)까지 전부 나눠 떨어지는 최대 숫자
최소공배수(LCM) = 최대공약수 * (숫자1 / 최대공약수) * (숫자2 / 최대공약수)
두 자연수 a, b의 최대공약수 구하기 (a > b일때)
유클리드 호제법
큰 수가 작은 수를 나눈 나머지를 이용하여 최대공약수를 구하는 알고리즘이다.
1. 큰 수로 작은 수를 나눈다 (나머지 = remainder)
2. 나머지가 0이면 작은수가 최대공약수이다
2. 나머지가 0이 아니면 작은수와 나머지의 최대공약수를 구한다.gcd(작은수b, 나머지remainder)
function getGCD(a, b) {
const remainder = a % b; // 1번
if (remainder === 0) return b; // 2번
return gcd(b, remainder); // 3번
}
또한 이렇게도 표현 가능하다.
작은 수는 다음 gcd의 큰수가 되고, 큰 수를 작은 수로 나눈 나머지가 작은수가 된다.
function getGCD(a, b) {
while (b > 0) {
let smallerNum = b;
b = a % b;
a = smallerNum;
}
return a;
};
두 수 a, b의 최소공배수 구하기
최소공배수는 최대공약수를 이용하여 구할 수 있다.
최소공배수 = 최대공약수 * (a / 최대공약수) * (b / 최대공약수)
= a * b / 최대공약수
function getLCM(a, b) {
return (a * b) / getGCD(a, b);
}
관련문제 풀어보기
https://school.programmers.co.kr/learn/courses/30/lessons/12953#
- 1번째 수와 2번째 수의 최소공배수를 구하고, 구한 최소공배수와 3번째 수의 최소공배수를 구한다. 이런식으로 N개까지 최소공배수를 구하면 그 수가 N개의 공통 최소공배수가 된다.
- 최소공배수 = a * b / 최대공약수
- 최대공약수는 유클리드 호제법으로 구한다.
function solution(arr) {
arr.sort((a, b) => a-b);
let lcm = 1;
for (let i = 0; i < arr.length; ++i) {
lcm = getLCM(lcm, arr[i]); // 이전 최소공배수와 현재값의 최소공배수
}
return lcm;
}
// 최대공약수 구하기
function getGCD(a, b) {
if (b === 0) return a;
return getGCD(b, a%b);
}
// 최소공배수 구하기
function getLCM(a, b) {
return (a*b)/getGCD(a, b);
}
'알고리즘' 카테고리의 다른 글
[프로그래머스]둘만의 암호 (0) | 2023.05.27 |
---|---|
[프로그래머스] 공원산책 (0) | 2023.05.27 |
[프로그래머스]달리기 경주 (0) | 2023.05.27 |
[프로그래머스] 완주하지 못한 선수 (0) | 2023.05.18 |
[프로그래머스] 폰켓몬 JS (0) | 2023.05.18 |