[Programmers](Level1) 최대공약수, 최소공배수 (feat. 유클리드 호제법)

주형(Jureamer)·2022년 4월 7일
0

문제명: 최대공약수와 최소공배수

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

최대공약수 GCD(Greatest Common Divisor)
최대공약수는 두 자연수의 공통된 약수 중 가장 큰 수를 의미한다.

최소공배수 LCM(Least Common Multiple)
최소공배수는 두 자연수의 공통된 배수 중 가장 작은 수를 의미한다.

유클리드 호제법(Euclidean Algorithm)
유클리드 호제법 또는 유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나이다.
기존의 방식인 2부터 해당 정수까지 나누어서 풀면 시간복잡도는 O(N)이 되지만 유클리드 호제법으로 시간복잡도를 O(logN)으로 줄일 수 있다.

문제풀이

 function solution(n, m) {
  var answer = [];
  
  // 최대공약수 구하기 (유클리드 호제법)
  function gcd(n, m) {
      return n % m === 0 ? m : gcd(m, n%m)
  }
  
  // 최소공배수 구하기
  function lcm(n, m) {
      return n * m / gcd(n, m)
  }
  answer.push(gcd(n, m));
  answer.push(lcm(n, m));
  return answer;
}
profile
작게라도 꾸준히 성장하는게 목표입니다.

0개의 댓글