🔎 N개의 최소공배수

❓ 문제링크

https://programmers.co.kr/learn/courses/30/lessons/12953

📄 제출 코드

// 유클리드 호제법
// 최대공약수 : 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
// 최소공배수 : a*b / 최대공약수


function solution(arr) {
  var answer = arr[0];
  for (let i = 0; i < arr.length; i++) {
    answer = lcm(answer, arr[i]);
  }
  return answer;
}

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

function lcm(a, b) {
  return (a * b) / gcd(a, b);
}
  
let arr = [2, 6, 8, 14];
console.log(solution(arr));

처음 풀 때 어? 쉽게풀리겠는데 하다가 못풀었다.
막힌 이유가 내가 생각한건 두 수를 가지고 생각하는 거였는데 문제는 배열에 2개 수만 오는게 아니다.
오,,, 그럼 어떻게 하지 하다가 결국 다른 풀이를 찾으러 떠났다.

풀이는 유클리드 호제법을 사용하는 간단한 문제였다.

유클리드 호제법이란 2개의 자연수의 최대공약수를 구하는 알고리즘이다.

호제법이란 말은 두 수가 서로(互) 상대방 수를 나누어(除)서 결국 원하는 수를 얻는 알고리즘을 나타낸다.

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다

아래 코드는 C언어로 작성된 예시이며 이 코드를 참고하여 작성하였다.

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

📘 참고

https://kyun2da.github.io/2020/06/27/gcdlcm/
https://ko.wikipedia.org/wiki/유클리드_호제법