으아아아아악할수있다.
오늘은 프로그래머스 레벨 1단계 두 문제를 풀었다. 한 문제는 못 풀었고 한 문제는 통과했다. 못 푼 문제는 최대공약수, 최소공배수 출력하는 문제인데 아직도 모르겠다. 연구해봐야겠다.
먼저 문제를 차근차근 정의해보아야 한다. 최대공약수(줄여서 gcd)는 공통된 약수 중 가장 큰 정소, 최소공배수(줄여서 lcm)는 공통된 배수 중 가장 작은 정수를 의미한다.
최대공약수를 구하는 방법 중에는 유클리드 호제법을 이용한 방법이 가장 효율적으로 보였다.
유클리드 호제법: a와 b의 최대공약수 = b와 r의 최대공약수 (r = a % b)
이를 반복하다보면 r=0이 되는데 이 때 b가 a와 b의 최대공약수이다.
최소공배수도 이를 이용해서 구할 수 있다. a b는 (최소공배수 최소 공약수)와 같다는 점을 이용하는 것이다.
곧, 최소공배수 = (a * b) / 최소공약수 이므로 최소 공약수를 위의 방법으로 구하면 쉽게 구할 수 있다.
function gcd(a, b) {
return b>0 ? gcd(b, a%b) : a;
}
function lcm(a, b) {
return a * b / gcd(a, b)
}