프로그래머스 문제중에 최대공약수, 최대공배수를 구하는 문제에 직면했다.
수학을 놓은지 오래라 이게대체 뭐지 했는데, 이 문제, 베이스캠프때 페어분들과 봤던 문제였다.
그때 유클리드 호재법을 이용하라고 했는데 아무리봐도 무슨말인지, 어떻게 응용하라는 말인지 몰라서 사용하지 못했는데 오늘 설명을 들으니 어느정도 이해가된다.
우선 유클리드 호재법은 최대공약수를 구하는 알고리즘이다.
큰수를 작은수로 나누었을때, 나머지 값이 0이면 작은수가 최대공약수가 된다.
만약 0이 되지 않는다면 기존의 작은수가 큰수가 되고 나머지가 작은수가되어 계속 계산이 반복된다.
그러다가 나머지가 0이되면 작은수가 최대공약수가되는 방식이다.
유클리드 호재법을 위해서는 기준점이 3개가 필요하다.
먼저 큰 수, 작은 수, 나머지.
n을 작은수로, m을 큰수로 놓고
let a = m // 큰수
let b = n // 작은 수
let r = 0 // 나머지
반복문을 도는데 나머지가 0이될때까지 돌려야하니(나머지가 0이되면 반복문 종료됨) 기준을 찾을 수 없다. 이럴때는 while문을 사용한다.
while((a%b)>0){// 반복문이 무한히돌지 않게 하기위해 나머지가 0보다 클경우만 돌게함
r=a%b // a를 b로 나눈 나머지가 r
a=b // 작은 수는 큰수가 됨
b=r // 나머지는 작은수가됨이렇게되면 b가 최대공약수가 되고, 최소공배수는 n*m을 최대공약수로 나누면된다.
return [b , (n * m) / b]출처-프로그래머스 최대공약수 최소공배수
