[프로그래머스] 최대공약수와 최소공배수 | JavaScript

최대공약수와 최소공배수

문제 설명

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

제한 사항

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

입출력 예

n	m	return
3	12	[3, 12]
2	5	[1, 10]

입출력 예 설명

입출력 예 #1

위의 설명과 같습니다.

 

입출력 예 #2

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

최대공약수와 최소공배수

정말 오랜만에 최대공약수와 최소공배수를 다시 배우게 되었다. 이걸 처음 접했을 때의 어린 나는 수학책에 끼적이면서 풀었었는데 현재의 나는 컴퓨터로 편하게 최대공약수와 최소공배수를 배우고 이 공식을 코드로 옮겨 컴퓨터가 풀어준다. 새삼 시대의 변화와 내가 정말 좋은 시대에 살고 있다는 걸 느끼게 되었다.

 

1. 최대공약수(GCD, Greatest Common Division)

두 수, 혹은 그 이상의 여러 수의 공통인 약수 중 가장 큰 수 - https://swess.tistory.com/13

예를 들어

• 7 -> 1, 7
• 14 -> 1, 2, 7, 14

두 수, 7과 14에서 공통인 약수 중 가장 최대인 수는 7이므로 최대공약수는 7이다.

 

2. 최소공배수(LCM, Least Common Multiple)

두 수, 혹은 그 이상의 여러 수의 공통인 배수 중 가장 작은 수 - https://swess.tistory.com/13

예를 들어

• 7 -> 7, 14, 21, 28...
• 14 -> 14, 28, 42...

두 수, 7과 14에서 공통인 배수 중 가장 최소인 수는 14이므로 최소공배수는 14이다.

 

여기서 두 수 A, B의 최대공약수를 G, 최소공배수를 L이라고 하면

AB = LG와 같은 식이 성립이 된다.

유클리드 호제법(Euclidean algorithm)

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘이다.

1. A와 B를 나눈 나머지 R₁을 구한다. (여기서 두 수가 나누어 떨어지면 B가 최대공약수이다.)

2. B와 R₁를 나눈 나머지 R₂를 구한다.

3. R₁과 R₂를 나눈 나머지 R₃를 구한다.

4. 이 과정을 어느 한 쪽이 나누어 떨어질 때까지 반복한다. 여기서 직전에 얻은 나머지가 최대공약수이다.

 

이렇게 최대 공약수를 구하고, 최소공배수는 L = AB / G로 구한다.

코드

function solution(n, m) {
  const gcd = (a, b) => {
    if (b === 0) return a;
    return gcd(b, a % b);
  };
  const lcm = (a, b) => (a * b) / gcd(a, b);
  return [gcd(n, m), lcm(n, m)];
}

사실 코드로 옮기지는 못했다. 의사코드를 만들고도 풀지 못해서 구글링을 통해 재귀함수로 푸는 것을 보고 풀게 되었다. 재귀함수로 푸는 것은 처음이다. 프로그래밍을 배울 때 초기에 무한 루프를 재귀함수로 설명했었던 것 같다. 코드를 보면 간단하면서도 참 가독성도 좋다.

 

조건문을 통해 a와 b가 나누어 떨어질 때까지 만들고, 최소공배수까지 아주 간단하게 구했다. 정말 연습밖에 길이 없는 것 같다. 알고리즘은 참 어려운데 재미있다.

그래도 이런 풀이를 통해 조금씩 보는 눈이 넓어지는 것 같다.