2024. 10. 02.(알고리즘 - 최대공약수와 최소공배수)

★ 문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요. 배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다. 예를 들어 두 수 3, 12의 최대공약수는 3, 최소공배수는 12이므로 solution(3, 12)는 [3, 12]를 반환해야 합니다.

(두 수는 1이상 1000000이하의 자연수입니다.)

★ 문제 해결 과정

처음에는 최소공배수와 최대공약수를 구할 수 있는 수학공식을 찾아서 적용하려고 했는데 아무리 해봐도 내가 아는 지식으로 쉽게 풀어낼 . 수 없을 것 같아 찾아보니 유클리스 호제법이라는 것이 있었다.

 

유클리드 호제법(Euclidean algorithm)은 두 수의 최대공약수를 구할 수 있는데.

이 방법은 두 수를 나누는 과정을 반복하여 최대공약수를 찾는 방식으로, 아래와 같은 아이디어를 기반으로 적용된다:

1. 두 수 aaa와 bbb (a>ba > ba>b)가 있을 때, aaa를 bbb로 나눈 나머지를 구합니다.
2. 만약 나머지가 0이면, bbb가 두 수의 최대공약수입니다.
3. 나머지가 0이 아니면, aaa를 bbb로 대체하고, bbb를 나머지로 대체하여 반복합니다.

이 과정을 나머지가 0이 될 때까지 반복하면, 마지막에 남은 값이 최대공약수가 된다.

 

최소공배수는  두 수의 공통 배수 중에서 가장 작은 수를 의미한다.

최소공배수=a×b최대공약수인데,​

이 관계가 성립하는 이유는 아래와 같다.

1. 두 수 aaa와 bbb의 곱은 공약수를 중복하여 포함한 값을 가지게 됩니다.
2. 이를 최대공약수로 나누어주면 두 수의 최소공배수를 얻을 수 있습니다.

★ 제출한 문제 답안

function solution(a, b) {
  const gcd = (x, y) => (y === 0 ? x : gcd(y, x % y));
  const gcdValue = gcd(a, b);
  const lcmValue = (a * b) / gcdValue;
  
  return [gcdValue, lcmValue];
}