[유클리드 호제법]최대공약수와 최소공배수

문제

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

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

입출력 예

nmreturn

3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1
위의 설명과 같습니다.

입출력 예 #2
자연수 2와 5의 최대공약수는 1, 최소공배수는 10이므로 [1, 10]을 리턴해야 합니다.

 

문제풀이

유클리드 호제법(Euclidean-Algorithm)

• 두 수의 최대공약수(GCD)를 구하는 알고리즘
• 호제법: 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘

MOD 연산

• 유클리드 호제법을 이해하기 위해서 선제되는 연산
• 두 값을 나눈 나머지를 구하는 연산

0이상인 두 개의 정수 중 큰 수를 작은 수로 나눈 나머지를 구한다(MOD 연산)

12 mod 5 = 2

 

이후, 나눴던 수와 나머지를 통해 다시 mod 연산을 한다(과정 반복)

5 mod 2 = 1
2 mod 1 = 0

 

나머지 값이 0이 되었을 때, 마지막 연산에서 나누는 수로 사용된 1이 12와 5의 최대공약수가 된다.

 

결과적으로 반복되는 mod연산을 수행하기 위해서는 다음과 반복문 및 재귀함수를 사용할 수 있다.

 

반복문

function GCD(a, b){
  let tmp;
  while(b){      
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}
//a > b

 

재귀함수

function GCD(a, b) {
  if(b === 0) return a;
  else return GCD(b, a % b);
}
// a > b

 

이렇게 구한 최대공약수(GCD)의 값이 선제되면, 최소공배수(LCM)는 다음과 같은 연산을 통해 쉽게 구할 수 있다.

(최소공배수) = (두 자연수의 곱) / (최대공약수)

 

표를 통해 확인해보기 

 

SQ	GCD(a, b)	a	b	tmp(a % b)
1	GCD(12, 5)	12	5	2
2	GCD(5, 2)	5	2	1
3	GCD(2, 1)	2	1	0

 

코드

function GCD(a, b) {
  if(a === 0) return b;
  else return GCD(b % a, a);
}

function solution(n, m) {
  let answer = [];
  answer[0] = GCD(n, m);
  answer[1] = n * m / GCD(n, m);
  return answer;
}