최대공약수 GCD(Greatest Common Divisor)
최대공약수는 두 자연수가 공통으로 갖는 약수들 중에서 가장 큰 값을 의미한다.
예를들어 24와 18 있다고 해보자. 최대공약수는 6이 된다.
최소공배수 LCM(Least Common Multiple)
최소공배수는 두 자연수들의 배수들 중에서 공통된 가장 작은수를 말한다.
참고로 최소공배수는 최대공약수를 통하여 바로구할 수 있다.
최소공배수 = 두 자연수의 곱 / 최대공약수 가 적용된다.
예를 들어 24와 18의 최소공배수는 72 이다.
유클리드 호제법 (Euclidean Algorithm)
유클리드 알고리즘은 2개의 자연수 의 최대공약수를 구하는 알고리즘의 하나이다.
호제법이란 말은 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타낸다.
2개의 자연수 a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다.
이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
이를 위에서 들었던 예를 활용하여 이해해 보자.
a가 24, b가 18 이라고 해보자.
|
|
GCD
|
a
|
b
|
a%b
|
|
1회
|
GCD(24, 18)
|
24
|
18
|
6
|
|
2회
|
GCD(18, 6)
|
18
|
6
|
0
|
2번째 시도만에 나머지가 0으로 떨어졌으며, 이때 나누는 수(6) 이 최대공약수가 된다.
이제 최대공약수를 알게되었으니 최소 공배수를 구해보자!
위에서 말한대로 최대공약수를 알면 최소공배수는 바로 구할 수 있다.
최소공배수 = 두 자연수의 곱 / 최대공약수
따라서 24 * 18 / 6 을 진행하면 72가 나오면 이값은 최소공배수가 된다.
관련된 문제로 백준의 2609번 문제를 추천한다.
댓글