프로그래머스 (N개의 최소공배수_JAVA)
1달간 1차 알고리즘 스터디를 슬렁슬렁 한 결과,,, 아무것도 얻지 못했다..
다시 마음을 잡고 2차 스터디를 잘 하고자 했으나.. 벌써 14일.
지금부터라도 꼼꼼한 리뷰와 정확한 이해를 위해 블로그를 시작!!!
문제 설명
숫자 배열이 주어지면 그 숫자들의 공통된 최소공배수를 구하는 문제이다.
문제 풀이 방법
최대공약수와 최소공배수 구하는 방법을 알아낸다.
따로 최대공약수, 최소공배수 구하는 클래스를 생성한다.
메인 클래스에서 관계에 따라서 알고리즘을 구현한다.
최대공약수 알고리즘
최대공약수란?
먼저 공약수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 여러 수의 공통인 약수라는 뜻이다. 최대공약수는 당연히 공약수 중 가장 큰 것. 두 수 a,b의 최대공약수를 수학적 기호로 표시하면, gcd(a,b)이며,더욱 줄여서 (a,b)로 표기하기도 한다.특히, gcd(a,b)=1이면 두 수 a,b는 서로소(relatively prime, coprime)라고 한다.
유클리드 호제법
알고리즘 문제에서 최대공약수 관련 문제는 보통 유클리드 호제법이라는 것을 사용한다.
static int gcd(int a, int b) {
while(b!=0) {
int r=a%b;
a=b;
b=r;
}
return a;
}
이와 같이 두수가 있으면 처음에 그 중 한 수(여기서는 b)로 나누고 나머지를 임시 변수(r)에 저장하고 나누어진수(a)는 나눈수(b)가 되고 나눈수(b)는 임시변수(r)이 된다. 그리고 b가 0이 아닐때 까지 반복하다 0이 되면 a를 return 하게 되는데 a가 a,b의 최대공약수가 된다.
최소공배수란?
공배수란, 이름에서 알 수 있듯이 두 수, 혹은 그 이상의 수들의 공통인 배수라는 뜻이다. 최소공배수는 당연히 공배수 중에서 가장 작은 것. 두 수 a,b의 최소공배수를 기호로 lcm(a,b)로 표기하며, 더욱 줄이면 [a,b]로 표기하기도 한다.
최소공배수 구하는법
간단하다 , 이것 또한 알고리즘 문제에서 가장 많이 쓰이는 식인데
최소공배수 = 두수의 곱 / 두수의 최대공약수
class Solution {
public int solution(int[] arr) {
int answer = 0;
int lcm = arr[0];
for (int i=1; i<arr.length; i++ ) { //0번 인덱스를 기준으로 모든 요소와
lcm = getLcm(lcm, arr[i]); //최소공배수를 구한다..
}
return lcm;
}
public static int getGcd(int a, int b) {//최대공약수
while(b!=0) {
int temp = a%b;
a=b;
b=temp;
}return a;
}
public static int getLcm(int a, int b) {//최소공배수
return a * b/getGcd(a, b);
}
}
Author And Source
이 문제에 관하여(프로그래머스 (N개의 최소공배수_JAVA)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@abcd-2020/프로그래머스-N개의-최소공배수JAVA저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)