최대공약수, 최소공배수 구하기

이 코드는 재귀적인 방법으로 최대공약수^{Greatest Common Divisor}를 구하는 함수입니다. 이 함수는 유클리드 호제법^{Euclidean algorithm}에 기반하여 작동합니다. 유클리드 호제법은 최대공약수를 구하는 방법 중 하나로, 재귀적인 나머지 연산을 통해 두 수의 최대공약수를 효율적으로 구하는 방법입니다.

function gcd(a, b) {
  if (b === 0) {
    return a;  // 만약 b가 0이면, a를 반환
  }

  return gcd(b, a % b);  // 재귀 호출을 통해 최대공약수를 구함
}

알고리즘은 다음과 같이 동작합니다:

1. 두 수 a와 b를 입력받습니다.
2. 만약 b가 0이면, a가 최대공약수이므로 a를 반환합니다.
3. 그렇지 않은 경우, a를 b로 나눈 나머지를 구합니다.
4. a를 b로 나눈 나머지를 새로운 a로 설정하고, b를 원래의 a로 설정합니다.
5. 1~4번 과정을 반복합니다. 
6. b가 0이 될 때, a는 최대공약수입니다.

이런 식으로 재귀 호출을 반복하다 보면, 최종적으로 두 수의 최대공약수가 반환됩니다.

 

이 코드를 사용해 a가 3이고 b가 12일 때, 최대공약수 num을 구하는 과정은 다음과 같습니다:

function gcd(a, b) {
  if (b === 0) {
    return a;
  }

  return gcd(b, a % b);
}

const a = 3;
const b = 12;
const num = gcd(a, b);

console.log(num);

1. a는 3, b는 12입니다.
2. gcd(3, 12)를 호출합니다. 
3. b가 0이 아니므로 조건문을 건너뜁니다.
4. gcd(b, a % b)를 재귀적으로 호출합니다. gcd(12, 3 % 12)를 호출합니다. => gcd(12, 3)
5. b가 0이 아니므로 조건문을 건너뜁니다.
6. gcd(b, a % b)를 재귀적으로 호출합니다. gcd(3, 12 % 3)를 호출한다. => gcd(3, 0)
7. b가 0이므로 조건문이 참입니다.
8. 최대공약수 3을 반환합니다.

따라서 a가 3이고 b가 12일 때, 주어진 코드를 실행하면 최대공약수인 3을 구할 수 있습니다.

 

function lcm(a, b) {
  return (a * b) / gcd(a, b);  // 최소공배수를 구하기 위해 최대공약수를 활용한다
}

위 코드는 a와 b의 최소공배수를 반환한다. 이를 위해 입력받은 a와 b를 곱하고, 그 값을 최대공약수(gcd(a, b))로 나눈 결과를 반환합니다. 이렇게 두 수의 최소공배수를 구할 수 있습니다.