알고리즘-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

좋은 이론이었다

끝!

참고

• 유클리드호제법-위키백과
• 프로그래머스- 최대공약수와 최소공배수