문제
문제 설명
두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.
제한 사항
- 두 수는 1이상 1000000이하의 자연수입니다.
입출력 예
| n | m | return |
|---|---|---|
| 3 | 12 | [3, 12] |
| 2 | 5 | [1, 10] |
풀이
나의 풀이
유클리드 호제법으로 최대공약수와 최소공배수를 구하였다.
(유클리드 호제법에 대한 설명은 아래에서)
function solution(n, m) {
let N = n, M = m;
while (M > 0) {
let temp = M;
M = N % M;
N = temp;
}
return [N, (n * m) / N];
}다른 사람들의 풀이
나는 for문을 이해한 적이 없었구나 생각하게 만든 풀이.
true/false 조건을 r = a % b로 판별. 0이 나오면 for문이 종료된다.
function gcdlcm(a, b) {
let r;
for (let ab = a * b; r = a % b; a = b, b = r) {}
return [b, ab / b];
}WIL
유클리드 호제법
(유클리드 호제법은 기원전 300년경 [유클리드 원론]에 기록된 인류 최초의 알고리즘으로 알려져있다)
두 수의 최대공약수는 유클리드 호제법으로 구한다.
호제법이란 '두 개의 수가 서로 나누는 것'이기에 붙여진 이름으로, 주어진 두 개의 수를 번갈아 가며 나누어서 최대공약수를 구하는 방법이다.
"정수 X와 Y(X ≥ Y)가 주어졌을 때 X를 Y로 나눈 나머지를 R이라고 하면, X와 Y의 최대공약수는 Y와 R의 최대공약수와 같다. 그러나 X와 0이 남았을 경우 최대공약수는 X로 한다.
유클리드 호제법에 따라 정수 X와 Y(X ≥ Y)의 최대공약수를 변수 GCD에 구하는 알고리즘을 작성해보자.
- 변수 R에 X/Y의 나머지 값을 대입한다.
- 변수 R이 0이 아니라면 다음 3~5단계를 반복한다.
- 변수 X에 변수 Y의 값을 대입한다.
- 변수 Y에 변수 R의 값을 대입한다.
- 변수 R에 X/Y의 나머지 값을 대입한다.
- 변수 GCD에 변수 Y의 값을 대입한다.
정리
- 유클리드 호제법에 따라 재귀함수로 최대공약수를 구할 수 있다.
- 두 수를 곱한 값에서 최대공약수를 나누면 최소공배수가 된다.
