문제 설명
두 수의 최소공배수(Least Common Multiple)란 입력된 두 수의 배수 중 공통이 되는 가장 작은 숫자를 의미합니다. 예를 들어 2와 7의 최소공배수는 14가 됩니다. 정의를 확장해서, n개의 수의 최소공배수는 n 개의 수들의 배수 중 공통이 되는 가장 작은 숫자가 됩니다. n개의 숫자를 담은 배열 arr이 입력되었을 때 이 수들의 최소공배수를 반환하는 함수, solution을 완성해 주세요.
제한 사항
- arr은 길이 1이상, 15이하인 배열입니다.
- arr의 원소는 100 이하인 자연수입니다.
입출력 예
arr result
| [2,6,8,14] | 168 |
| [1,2,3] | 6 |
package LV2;
public class H12953 {
public static void main(String[] args) {
// 테스트 케이스 정의
int[] arr1 = {2, 6, 8, 14};
int[] arr2 = {1, 2, 3};
// 테스트 케이스 실행 및 결과 출력
System.out.println(solution(arr1)); // 출력: 168
System.out.println(solution(arr2)); // 출력: 6
}
// 최소공배수를 구하는 메서드
public static int solution(int[] arr) {
// 첫 번째 값을 answer로 초기화
int answer = arr[0];
// arr 배열의 각 요소에 대해
for (int i = 1; i < arr.length; i++) {
// answer와 다음 값의 최소공배수를 계산하여 answer 업데이트
answer = lcm(answer, arr[i]);
}
// 최종 계산된 최소공배수 반환
return answer;
}
// 최대공약수를 구하는 메서드
private static int gcd(int a, int b) {
// b가 0이 아닐 동안 반복
while (b != 0) {
// a를 b로 나눈 나머지를 r에 저장
int r = a % b;
// a에 b를 대입
a = b;
// b에 r을 대입
b = r;
}
// 최대공약수인 a 반환
return a;
}
// 최소공배수를 구하는 메서드
private static int lcm(int a, int b) {
// a와 b의 곱을 a와 b의 최대공약수로 나눈 값 반환
return a * b / gcd(a, b);
}
}
두 수 a와 b의 최소공배수 LCM(a, b)는 a * b / GCD(a, b)로 계산할 수 있다. 이 때, GCD(a, b)는 a와 b의 최대공약수를 의미한다. 따라서 최대공약수를 찾는 함수가 필요하며, 유클리드 호제법을 이용해 최대공약수를 구할 수 있다.
두 수 이상의 최소공배수는 첫 번째 수와 두 번째 수의 최소공배수를 구하고, 그 결과와 세 번째 수의 최소공배수를 구하는 방식으로 순차적으로 계산할 수 있다.
유클리드 호제법
유클리드 호제법은 두 자연수의 최대공약수를 구하는 알고리즘 중 하나이다. 이름에서 알 수 있듯이, 이 방법은 고대 그리스의 수학자 유클리드가 저술한 '원론'에서 처음 소개되었다.
유클리드 호제법은 다음과 같은 원리에 기반한다: 두 수 A와 B(A > B)의 최대공약수는 B와 A를 B로 나눈 나머지 R의 최대공약수와 같다. 이 원리를 이용해 나머지가 0이 될 때까지 반복하여 나누는 과정을 거친다.
다음은 유클리드 호제법을 통해 최대공약수를 찾는 절차이다:
- 두 수 A와 B가 있을 때, A가 B보다 크다고 가정한다.
- A를 B로 나눈 나머지를 R이라 한다.
- 이제 B를 새로운 A로, R을 새로운 B로 간주하고 다시 A를 B로 나눈다.
- 이 과정을 나머지 R이 0이 될 때까지 반복한다.
- 나머지가 0이 되면, 그때의 B가 최초의 A와 B의 최대공약수가 된다.
이 방법은 반복적으로 나머지 연산을 수행하기 때문에 두 수의 차이가 클 때에도 빠른 속도로 최대공약수를 구할 수 있습니다. 또한, 이 알고리즘은 최소공배수를 구하는 데에도 활용된다. 두 수의 곱을 두 수의 최대공약수로 나누면 그 결과가 두 수의 최소공배수가 되기 때문이다.