TIL_프로그래머스 - Lv1. 최대공약수와 최소공배수

📒 오늘의 공부

1. 프로그래머스

Lv1. 최대공약수와 최소공배수

나의 풀이

const solution=(n, m)=> {
    let answer = [];
    let gCD = 0;
    let lCM = 0;

// 최대공약수
for (let i = 1; i <= n && i <= m; i++) {
    if (n % i === 0 && m % i === 0) {
        gCD =i;
    }
}
    answer.push(gCD);

// 최소공배수
    lCM = (n*m)/gCD;
    answer.push(lCM);

    return answer;
}

다른 풀이

function gcdlcm(a, b) {
    var r;
    for(var ab= a*b;r = a % b;a = b, b = r){}
    return [b, ab/b];
}

• ab/b: 두 수의 곱 / 최대공약수 = 최소공배수
• r: a를 b로 나눈 나머지. 나머지가 0이 될 때까지 반복.
• 반복문 내에서 a에는 b를, b에는 r을 대입하여 값을 갱신
  (유클리드 호제법을 활용하여 최대공약수를 구하는 과정)
• 반복문이 종료되면 b에는 최대공약수가 저장

알게된 것

최대공약수

• 최대공약수(Greatest Common Divisor, GCD)
  • 두 개 이상의 정수의 공통된 약수 중 가장 큰 수를 의미
  • ex. 12의 약수는 1, 2, 3, 4, 6, 12
    18의 약수는 1, 2, 3, 6, 9, 18
    => 12와 18의 최대공약수는 6
• 최대공약수 구하기
  • 유클리드호제법
    • A와 B의 최대공약수는 A를 B로 나눈 나머지가 r 일 때 B와 r의 최대공약수와 같다.
    • b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.

최소공배수

• 최소공배수(Least Common Multiple, LCM)

  • 두 개 이상의 정수의 공통된 배수 중 가장 작은 수를 의미
  • ex. 4의 배수는 4, 8, 12, 16, 20, ...
    6의 배수는 6, 12, 18, 24, 30, ...
    => 4와 6의 최소공배수는 12

• 최소공배수 구하기

  • 두 수의 곱을 최대공약수로 나눈 것

참고자료

유클리드 호제법 개념