[Java] 최대 공약수(GCD) , 최소 공배수(LCM) 알고리즘
프로그래머스의 N개의 최소공배수라는 문제를 풀면서 알게된 내용들이 있다.
분명 어렸을때 학교를 다니면서 배웠던 내용인 최대 공약수와 최소 공배수였지만 이부분을 알고리즘으로 풀어내고자 하니 규칙을 찾아내기 보다는 나만의 풀이과정을 통해 풀게 되었다. 소인수분해를 통해 주어진 각 숫자의 최대 제곱을 구하여 풀어내는 방법이였다. 나의 풀이 방법과 동시에 최대 공약수 , 최소 공배수는 어떻게 구현해가는지 정리해보자
최대 공약수(GCD) 알고리즘
최대 공약수(Greatest Common Divisor)란? 두 수 이상의 여러 수의 공약수 중 최대인 수를 가리킨다.
12의 소인수분해 해보면 2 * 2 * 3이 된다.
18을 소인수분해 해보면 2 * 3 * 3이 된다.
두 수에서 소인수분해 후 주어진 숫자가 일치하는 것에서 최소값을 가져와서 계산해보면 최대 공약수가 된다.
12에는 2^2이 있지만 18에는 2 뿐이므로 2
18에는 3^2가 있지만 12에는 3 뿐이므로 3
2 * 3 = 6이라는 최대 공약수를 알 수 있다.
다르게 풀이 한다면 두 수의 약수를 다 나열해서 둘다 가지고 있는 최대의 약수를 구하는 것으로 보면 된다.
12의 약수는 1, 2, 3, 4, 6, 12
18의 약수는 1, 2, 3, 6, 9, 18
여기에서 둘다 가지고 있으며 가장 높은 숫자는 6이다.
위의 풀이 과정을 Java 코드로 담으려고 한다.
기존의 최대공약수 구하는 방법(무차별 대입)
public int gcd(int a, int b) {
int result = 0;
int min = Math.min(a , b);
for (int i = 0; i <= min; i++) {
if (a % i == 0 && b % i == 0) result = i;
}
return result;
}빅오표기법 시간복잡도 : O(N)
유클리드 호제법
유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘이다.
호제법이란? 두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 뜻한다.
자바 코드
public int gcd(int a , int b) {
while (b != 0) {
int tmp = b;
b = a % b;
a = tmp;
}
return a;
}
예제) 270과 192의 최대 공약수 구하기 - GCD(270 , 192)
※괄호 안에는 담긴 숫자를 뜻합니다.
첫번째 흐름
- tmp(192) = b(192)
- b(78) = a(270) % b(192)
- a(192) = tmp(192)
두번째 흐름
- tmp(78) = b(78)
- b(36) = a(192) % b(78)
- a(78) = tmp(78)
세번째 흐름
- tmp(36) = b(36)
- b(6) = a(78) % b(36)
- a(36) = tmp(36)
네번째 흐름
- tmp(6) = b(6)
- b(0) = a(36) % b(6)
- a(6) = tmp(6)
b 값이 0에 도달했을때 return 하는 값은 6이라는 숫자를 return 한다.
이로써 270과 192의 최대 공약수는 6이라는 사실을 알 수 있다.
최소 공배수(LCM) 알고리즘
최소 공배수(Least Common Muliple)란 두 수에서 서로 공통으로 존재하는 배수 중 가장 작은 수를 가리킨다.
최대 공약수와 똑같이 소인수분해를 해보면
12를 소인수분해 해보면 2 * 2 * 3
18을 소인수분해 해보면 2 * 3 * 3
로 나오며 각 숫자의 제곱수치를 적용해서 계산해보면 최소 공배수를 알수있다.
2^2 * 3^2 = 4 * 9 = 36 이 나온다.
자바 코드
public int lcm(int a, int b) {
int c = a와 b의 최대 공약수
return a * b / c;
}12 * 18을 계산해보면 216이 나오는데 여기에 최대 공약수인 6를 나누면 36 이라는 최소 공배수를 알수 있게 된다.
프로그래머스 문제
최대 공약수와 최소 공배수의 알고리즘을 공부하며 블로그 글을 작성해두자라고 생각하게 된 문제는 아래와 같다.
N개의 최소공배수 문제이다.
여러개의 숫자가 주어지며 전부 만족하는 최대 공배수를 찾아 return 하면 되는 문제 였다.
여기서 내가 풀이한 방법은 아래와 같다.
- 주어진 숫자가 중복이 있을 수 있다 판단하여 중복 제거 로직을 작성하였다.
- Map<Integer , Integer> cnt = new HashMap<>(); 를 선언하여 각 숫자를 소인수분해하여 제곱수치가 어느 숫자가 가장 높은지 저장하고자 했다.
- 2번 작업을 위해 반복문을 돌려가며 소인수분해를 하였고 ArrayList에 담았고 그 ArrayList를 HashSet에 넣었고 Collections.frequency 기능을 통해 제곱수치를 추려내며 담는 작업을 진행했다.
- 3번의 작업이 완료되면 계산해서 return 했다.
실제로 문제를 풀어서 노션에 정리해두었다.
N개의 최소공배수 | Notion
문제사이트
stirring-astronomy-a9b.notion.site
마무리
어떻게 풀어나갈지 방법만 알았더라면 완전 쉬운 문제 였는데 그걸 몰라서 이렇게 풀었던 것 같다.
비유하자면 1 + 1 = 2 인데... + 라는 기호를 모르는 채 1하고 1을 더해서 왜 2가 되는지? 스스로 고민하며 수식을 써내려가면서 푼 느낌이다...
덕분에 생각지도 못한 여러 기능들을 공부한 덕도 있다.