알고리즘-2021/04/24


문제 설명

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

제한 사항

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

입출력 예

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

풀이

const findGcd = (big, small) => {
  let restNum = big%small;
  if(restNum === 0) return small;

    return findGcd(small, restNum);
};

const findLcm = (gcd, big, small) => {
  return (big*small) / gcd;
}

function solution(n, m) {
    let answer = [];
    let bigNum = n > m ? n : m;
    let smallNum = n < m ? n : m;
    let gcd = findGcd(bigNum,smallNum); //최대공약수
    let lcm = findLcm(gcd,bigNum,smallNum); //최소공배수

    answer = [gcd, lcm];
    return answer;
}

문제를 처음 보고 고등학교때 손으로 손수 써가며 하는 방식으로는 답이 없을 것 같아 최대공약수,최소공배수 알고리즘을 검색해본 결과
역시 좋은 이론이 있었다 :)..

  • 최대공약수를 찾기 위해 큰수와 작은수를 나누고 나머지가 0이 되는 경우 작은 수가 최대공약수가 된다.
    만약 나눠지지 않는다면 1. 작은 수2. 큰수와 작은수의 나머지를 다시 한번 나뉘고 이것이 나머지가 0이 될때까지 진행하면 최대공약수가 나오게 된다.
    이는 재귀함수로 해결하였다.

  • 최소공배수는 두 숫자의 곱에 최대공약수를 나뉘면 해결된다.

A = a*gcd
B = b*gcd
lcm = a*b*gcd = A*B/gcd

좋은 이론이었다

끝!


참고

좋은 웹페이지 즐겨찾기