대표적인 알고리즘 사이트로 백준, 프로그래머스, leetcode 등이 있으며, 초반부터 알고리즘 문제를 풀다보면 항상 마주치는 문제들이 있는데, 그 중 하나로 최소공배수, 최대공약수를 구하는 문제이다. 나의 경우는 항상 시간이 지난 후 해당 문제를 접하게 되면 기억이 나지를 않고 수학적인 부분을 고려해야 하다보니 거부감이 반복적으로 들어서 이번에 한번 차근차근 정리하고 넘어가보려고 한다.
최대공약수?
두 개 이상의 수가 공통으로 갖고 있는 수 중에서 가장 큰 수
위와같이 수를 더 이상 나누어지지 않을 때까지 나눌 시 나누는데 사용했던 모든 수를 곱하면 최대공약수가 된다.
24 : 2^3 x 3 -> 1 2 3 4 6 8 12 24
18 : 2 x 3^2 -> 1 2 3 6 9 18
최대 공약수 : 6
최소공배수?
두 개 이상의 수가 갖는 배수 중 공통된 가장 작은 수
위와같이 수를 더 이상 나누어지지 않을 때까지 나눌 시 나누는데 사용했던 모든 수를 곱하면 최대공약수가 된다.
최소공배수 = 두 자연수의 곱 / 최대공약수로 나눈 수 임을 확인할 수 있다.
24 -> 24 48 72 96 . . . . .
18 -> 18 36 54 72 90 .....
최소 공배수 : 72
서로소?
주어진 수를 반복적으로 나눌 시 더 이상 나눌 수 없는 수
위의 경우 공통되는 수로 나눌 시 최종적으로 더 이상 나눌 수 없는 수(=4 3)를 볼 수 있다.
유클리드 호제법 ?
2개의 자연수의 최대공약수를 구하는 알고리즘이다.
호제법 : 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘이다.
두 수 a , b에 대하여 ( a > b) 관계가 형성될 시 a를 b로 나눈 나머지를 r이라 한다면, 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 |
다음과 같이 나머지 값 r을 다음에 나눌 b에 두고 기존에 b의 값을 a 값으로 하여 나눈 나머지가 0이 될 때 b에 해당하는 값이 곧 최대공약수가 된다.
이렇게 최대공약수를 구한다면, 최소공배수는 주어진 두 수를 곱하여 최대공약수로 나누어주면 된다.
public class Main {
public static void main(String[] args) {
int a = 24 , b = 18;
int r = Main.gcd(a,b); //최대공약수
int rr = (a * b) / r; //최소공배수
}
static int gcd(int a , int b){
while (b > 0){
int tmp = a;
a = b;
b= tmp%b;
}
return a;
}
}