[TIL] 최대공약수 최소공배수 찾기(유클리드 호제법) 23.05.31

✔️오늘 한일!

• 알고리즘 문제 해결
• 개인과제 코드리뷰

---

알고리즘 문제를 해결하던 도중 최대공약수를 사용해야하는 문제가 있었다. 막상 코드로 구현을 하려고 하니 도저히 생각이 안나 구글링을 해보니 유클리드 알고리즘이라는 공식이 있었다.
이 공식으로 쉽게 해결할 수 있었다.

유클리드 알고리즘(호제법)

두 자연수 사이의 최대공약수를 구하는 알고리즘 중 하나이다.

1) a, b 중 큰 수를 작은 수로 나눈다. ( a > b )
2) b를 나머지 r로 계속 나눈다.
3) 나머지가 0이 나오면 나누는 수가 최대 공약수.

한줄로 정리하자면 아래와 같다.
"2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면, a와 b의 최대공약수는 b와 r의 최대공약수와 같다."

ex)

• a : 1070 / b : 1020
• 1070 % 1020 = 50
• 1020 % 50 = 20
• 50 % 20 = 10
• 20 % 10 = 0
  -> 최대공약수는 10

문제. 분수의 덧셈

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다. 두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.
https://school.programmers.co.kr/learn/courses/30/lessons/120808

나의 문제풀이

function calGcd(a,b) { 
  return b ? calGcd(b, a % b) : a; 
                       // r
}
function solution(numer1, denom1, numer2, denom2) {
    let num = denom1 * numer2 + denom2 * numer1
    let denom = denom1 * denom2
    let gcd = calGcd(num, denom)
    
    return [num / gcd , denom / gcd]
}

1) 재귀함수로 최대공약수(gcd)를 구하는 함수를 생성
2) 분자, 분모를 따로 구한 뒤 최대공약수로 나누어 준다

반대로 최소공배수(lcm)를 구해야 하는 경우 최대공약수를 응용하면 된다.

let lcm = (num * denom) / gcd

---

0단계인데도 해결하는데 시간이 엄청 오래걸렸다. 문제와 직접적인 내용을 구글링하면 바로 정답이 나올 것 같아서 mdn을 찾아보기도 하고 조건문을 사용해보기도하고 여러 시행착오 끝에 구글링 해본 건데 유클리드 알고리즘으로 쉽고 간단하게 해결할 수 있었다. 최대공약수라는 단어를 초·중학생 이후로 써본적이 없는 것 같은데 잘 기억해두고 혹시 써먹을일이 있다면 잘 사용해봐야겠다!