24/05/14 최대공약수, 최소공배수, 유클리드 알고리즘

목적

알고리즘 풀이를 하면서, 이 내용은 정리해야겠다고 생각했다. 최대 공약수를 구하고 이를 통해 최소 공배수까지 구하는 코드를 작성했다.

유클리드 알고리즘이란?

2개의 자연수 사이 최대 공약수를 구하는 알고리즘이다.

방식은 다음과 같다.

2개의 자연수 a, b(단, a > b) a % b 의 결과인 나머지를 r 이라고 하자. 그럼 a 와 b 간의 최대 공약수는 b 와 나머지 r 의 최대 공약수와 같다.

이 성질을 이용해서, b와 나머지 r의 b % r 결과를 다시 r 로 나누어 r’ 를 구하는 과정을 반복해 나머지가 0이 되었을 때 나누는 수가 최대 공약수가 된다.

정리해보자면,

1. a % b 계산, 이때 나머지는 r.
2. if (r === 0) then r, else a = b, b = r, r = a % b
3. 2번 if 문의 조건이 참일 때 까지 반복.

쉬운 예시로, a = 24, b = 18 로 해보자.

횟수	a	b	a % b	최대 공약수
1회	24	18	6	GCD(24, 18)
2회	18	6	0	GCD(18, 6) === 6

2회만에 나머지가 0 이 되었다. 24 와 18의 최대공약수는 18 과 6의 최대 공약수와 같기에 18 % 6 의 결과에 따라 18을 나누는 수는 6이므로 6이 최대 공약수가 된다.

아래 코드를 보자.

최소 공배수

최소 공배수는 바로 최대 공약수를 구해 쉽게 구할 수 있다.

두 자연수 a, b 의 곱을 최대 공약수로 나누면 된다.

위에서 사용한 예시를 그대로 이어가보자.

a = 24, b = 18 일 때 최대 공약수는 6 이었다.

둘의 최소 공배수는 24 * 18 / 6 이 된다.

이는 72가 되며, 최대 공약수와 최소 공배수 모두 구할 수 있었다.

구현 코드

function solution(n, m) {
  var answer = [];

  let lg = n > m ? n : m;
  let sm = n < m ? n : m;
  let r = lg % sm; // 나머지 구하기, 한 번에 나누어 떨어지면 반복문 안 들어가도록 만듦.

  while (r !== 0) {
    lg = sm; // 나누는 수가 나눠지는 수가 됨.
    sm = r; //
    r = lg % sm;
  }

  answer.push(sm);

  // ㄴ> 유클리드 알고리즘 사용

  let lcm = (n * m) / sm;

  answer.push(lcm);

  return answer;
}