유클리드 호제법 (Euclidean algorithm)

유클리드 알고리즘 이란?

• 2개의 정수 또는 두 다항식의 최대공약수를 구하는 방법이다.
• 알고리즘은 "A > B 일때 A와 B의 최대공약수는 B와 나머지 R의 최대공약수와 같다."
  • 큰 수(A)를 작은 수(B)로 나눈다. ( A > B )
  • 나눈 수(B)를 A로 대입 나머지(R)을 B로 대입하여 계속 나눠준다. ( A(B) %  B(R) = (R)) 
  • 나머지가 0이 된다면 이전에 B에 대입한 R이 최대공약수이다.

 

예시

• 1071은 1029로 나누어 떨어지지 않기 때문에, 1071을 1029로 나눈 나머지를 구한다. ≫ 42
• 1029는 42로 나누어 떨어지지 않기 때문에, 1029를 42로 나눈 나머지를 구한다. ≫ 21
• 42는 21로 나누어 떨어진다.

 

반목문

const gcd =(a,b){
  let tmp;
  while(b !== 0){      //b가 0이 될 때까지
    tmp = a % b;
    a = b;
    b = tmp;
  }
  return a;
}

 

재귀함수

const gcd(a,b) {
  const remainder = a % b;
  return b === 0 ? a : gcd(b, remainder);
}

• 재귀함수란 함수 자신을 내부에서 다시 호출하는 구조로 만들어진 함수이다.
• 종료조건이 없다면 무한반복을 하게되므로 주의하자.

 

 

최소공배수 (LCM)

• 최소공배수(LCM)는 최대공약수(GCD)를 응용하면 구할 수 있다.
• 최소공배수는 LCM = (a * b) / GCD 이다.
• 두 수의 곱에 최대공약수를 나누어주면 최소공배수가 나온다.

function solution(n, m) {
  const gcd = (a, b) => (a % b === 0 ? b : gcd(b, a % b));
  const lcm = (a, b) => (a * b) / gcd(a, b);

  return lcm(n, m) // 최소공배수
}

//코테 스터디 팀원분의 프로그래머스 풀이