학선생 블로그 학선생 블로그

저번에 유클리드 호제법으로 최대공약수를 구했지! 이번에는 최대공약수를 가지고 두 수의 최소공배수부터 여러 수의 최소공배수를 구해볼거야! 아, '최소공배수 最小公倍數'는 LCM이라고도 하는데 Lowest Common Multiple의 약자로 쓰여. 최소공배수를 구하는 방법 또한 여러가지가 있겠지만 우리는 두 수의 최대공약수를 구하는 방법을 알아냈으니까 최대공약수를 이용해서 구해볼거야. 먼저 두 수의 최소공배수를 알아볼까? 최대공약수만 알고 있으면 넘나리 쉽게 구할 수 있어! 두 수를 곱해서 최대공약수로 나누면 그게 최소공배수지! 엄청 간단하지? A와 B의 최소공배수 = A X B ÷ A와 B의 최대공약수 그럼 여러 수의 최소공배수는 어떻게 구할 수 있을까? 여러 수의 최대공약수를 구할 때 처럼, 일단 아무..

여러 수의 최대 공약수를 구하기 위한 여러 가지 방법이 있겠지만! 그중에서도 가장 효율적이라고 생각되는 유클리드 호제법에 대해 알아볼게! '유클리드 호제법 互除法' 또는 '유클리드 알고리즘 Euclidean algorithm'이란 두 자연수의 최대공약수를 구하는 알고리즘이야. 유클리드는 그 유명한 그리스의 수학자! 그분 맞아. 기원전 300년 전에 태어나신 그분 말이야! 아, 호제법이란, 말 그대로 '서로 호(互)'자와 '덜 제(除)'자를 써서 '서로 나누어 없애는 방법'이라고 생각하면 돼. 아직 무슨 말인지 모르겠지? 말로 백 번 설명하는 것보다 아래의 동영상을 보는 것이 훨씬 더 이해가 잘 될 텐데.. 동영상을 보기 전에 '%'라는 기호에 대해 알고 보아야 돼. '%'는 보통 '퍼센트'라고 해서 '백..