두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
n | m | return |
---|---|---|
3 | 12 | [3, 12] |
2 | 5 | [1, 10] |
입출력 예 #1위의 설명과 같습니다.
입출력 예 #2자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.
💡 문제풀이 과정
약수
는 어떤 수를 나누었을 때 나누어 떨이지게 하는 자연수이다. 따라서for()
반복문을 이용하여 주어진 자연수number % i === 0
이면 약수이다. 따라서 주어진 두 수(n
과m
)의공약수
를 구하는 것은if (n % i === 0 && m % i === 0)
가 될것이다. 나는 빈 배열에 공약수들을 담아주었고,최대공약수
는 공약수가 담긴 배열의 마지막 인덱스 값이 될 것이다.const 최대공약수 = arr[arr.length -1];
- 마지막으로
최소공배수
를 구하는 방법으로 공약수를 이용하는 방법과 소인수분해하여 지수를 이용하는 방법이 있는데, 나는 공약수를 이용하는 방법을 사용하였다. 두 수를서로소
(공통된 약수가 없는 수)가 나올 때까지 계속 공약수로 나누어 공약수에 서로소까지 곱하는 방법이다. 따라서 코드는const 최소공배수 = 최대공약수 * (n / 최대공약수) * (m / 최대공약수);
이렇게 만들었다.- 답안 2번의 경우 다른 사람의 풀이인데,
for()
반복문 범위를i = n과 m의 최소값
부터 시작하여i > 0
그리고i--
으로 설정하였다. (나의 경우 주어진 자연수가 1000000이하의 수라고 해서 최대 범위를 너무 높게 잡아놨기 때문에…) 그리고 이렇게 범위를 설정하게 되면, 답안 1번과 같이 공약수를 빈 배열에 담아 최대공약수를 추출할 필요없이, 최대공약수를for()
문 속에서 바로 뽑을 수 있겠다.
❓ 약수 / 공약수 / 서로소 / 최대공약수/ 최소공배수의 기본 이론 및 예제
약수
: 어떤 수를 나누었을 때 나누어 떨어지게 하는 자연수.공약수
: 서로 다른 두 자연수의 공통된 약수.
- 3의 약수: 1, 3
- 12의 약수: 1, 2, 3, 4, 6, 12
- 3과 12의 공약수: 1, 3
최대공약수
: 공약수에서 제일 큰 수로, 위 예시에서 최대공약수는 3이 되겠다.- 참고로 공약수가 없는 경우가 있는데, 이처럼 공통된 약수가 없는 수를
'서로소'
라고 한다.공배수
: 서로 다른 두 자연수의 공통된 배수.
- 2의 배수: 2, 4, 6, 8, 10, 12, 14, 16, 18, ...
- 3의 배수: 3, 6, 9, 12, 15, 18, 21, ...
- 2와 3의 공배수: 6, 12, 18 ...
최소공배수
: 공배수에서 제일 작은 수로, 위 예시에서 최소공배수는 6이 되겠다.
✅ 답안 #1
function solution(n, m) {
let answer = [];
let arr = [];
for (let i = 1; i <= 1000000; i++) {
if (n % i === 0 && m % i === 0) arr.push(i); //공약수 배열에 담기
}
const max = arr[arr.length - 1]; //최대공약수
const min = max * (n / max) * (m / max); //최소공배수
answer.push(max, min);
return answer;
}
✅ 답안 #2
function solution(n, m) {
const min = Math.min(n, m);
let common_max = 1;
for(let i = min; i > 0; i--){
if(n % i === 0 && m % i === 0){
common_max = i;
break;
}
}
return [common_max, common_max * (n / common_max)* (m / common_max)];
}