문제

두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, 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부터 둘 중 작은수(n)까지 1씩 증가하면서, 두 수를 나눴을 때 0이 나오는 수를 GCD 변수에 업데이트하도록 해서 구했다.
최소공배수는 최대공배수 = 최대공약수 * 서로소 * 서로소 공식을 이용해서 구했다.

function solution(n, m) {
    let GCD; // 최대공약수
    for (let i = 1; i <= n; i++) {
        if (n % i === 0 && m % i === 0) {
            GCD = i;
        }
    }

    let LCM = GCD * (n / GCD) * (m / GCD); // 최소공배수
    return [GCD, LCM];
}

다른 사람의 풀이

function solution(n, m) {
	var r;
  	for (var nm = n * m; r = n % m; n = m, m = r) {}
  	return [m, nm/m];
}

이게 뭐지..
이 풀이를 이해하려면 유클리드 호제법에 대해 알아야 한다는 것을 알았다.

---

유클리드 호제법

gcd(A, B) = gcd(B, r)

A > B 일 때, A와 B의 최대공약수는 B와 r의 최대공약수와 같다.
이때, r은 A를 B로 나눈 나머지이다. A = qB + r
(q는 몫, r은 나머지)

직접 계산을 해보며 이해하는 게 빠를 것이라고 생각해서 위의 방식으로 1980과 168의 최대공약수를 구해보기로 했다.

1980, 168의 최대공약수 구하기

1980 = 168 * 11 + 132
➡️ gcd(1980, 168) = gcd(168, 132)

168 = 132 * 1 + 36
➡️ gcd(168, 132) = gcd(132, 36)

132 = 36 * 3 + 24
➡️ gcd(132, 36) = gcd(36, 24)

36 = 24 * 1 + 12
➡️ gcd(36, 24) = gcd(24, 12)

24 = 12 * 2 + 0 // 나머지가 0이 나왔을 때의 B가 최대공약수이다.
➡️ gcd(24, 12) = gcd(12, 0)

따라서 gcd(1980, 168) 은 gcd(24, 12)와 같으며, 최대공약수는 12이다.

재귀 함수로 구현하기

function gcd(a, b) {
  if (b === 0) { // base case
    return a;
  }
  
  return gcd(b, a % b); // recursive case
}

반복문으로 구현하기

function gcd(a, b) {
  while(true) {
    let r = a % b;
    if (r === 0) return b; // r이 0이 될 때까지 무한 반복
    
    a = b;
    b = r;
  }
}

---

이제 위에서 봤던 풀이를 다시 살펴보자!
보기쉽게 a, b로 바꾸어 봤다.

function solution(a, b) {
	var r;
  	for (var ab = a * b; r = a % b; a = b, b = r) {}
  	return [b, ab/b]; // [최대공약수, 최대공배수]
}

조건문 안의 조건을 살펴보면...

• 초기화 구문 : let ab = a * b;
  마지막 리턴문에서 최소공배수 = 두 수의 곱 / 최대공약수 공식에 필요한 ab를 변수로 선언했다.
• 조건문 : r = a % b;
  이 말은 r = a % b가 true일 동안 반복문을 실행한다는 뜻이므로
  즉, r = 0(false)이 되면 반복문을 종료한다는 뜻이다. (r = 0이 될 때까지 반복문을 실행)
• 증감문 : a = b, b = r
  gcd(a, b) = gcd(b, r) 공식을 이용했다.

+ 위의 코드에서 var을 let으로 바꿔서 하니까 오류가 발생했다. 이유가 뭘까..... (var와 let의 차이에 대해 다시 공부해봐야겠다ㅠ)
그래서 n*m을 미리 변수로 선언해두고 이렇게 작성하니 통과할 수 있었다.

function solution(n, m) {
    const nm = n*m;
  	for (let r; r = n % m; n = m, m = r) {
    }
  	return [m, nm/m];
}

---

유클리드 알고리즘 공부를 미루다가 드디어 정리해봤는데 생각보다 어렵지 않았다..! 하지만 이걸 나중에 실제 알고리즘 문제풀이에 적용할 수 있을까?.. 프로그래머스 댓글에서 매번 위로를 받는다🥲