프로그래머스 (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);
}

}