반응형
해당 글에서는 최대공약수와 최소공배수를 구하는 방법에 대해서 짧게 이해하는 방법에 대해서 공유합니다.
💡 해당 글을 이해하기 전에 상세하게 이해하고 싶다하시면 아래의 글이 큰 도움이 됩니다.
1) 두수의 최대공약수, 최소공배수 구현방법
1. 최대공약수(GCD) 구현
💡 유클리드 호제법 이용하여서 “최대공약수(GCD)”를 구하는 방식입니다.
💡 이 방식은 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될때까지 작동하여 최대공약수를 구하는 방식입니다.
1. 재귀 방식으로 구현
💡 b가 0이라면 a가 최대공약수가 되며, 그렇지 않으면 b와 a % b의 최대공약수를 구합니다.
💡 이를 재귀적으로 반복하여 최대공약수를 구할 수 있습니다.
// 재귀 방식
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
2. 반복문 방식으로 구현
💡 먼저, b가 0이 될 때까지, a를 b로 나눈 나머지를 b에 대입하고, a와 b의 값을 교환합니다.
💡 이를 반복하여 최대공약수를 구할 수 있습니다.
// 반복문 방식
public static int gcd(int a, int b) {
while (b != 0) {
int temp = b;
b = a % b;
a = temp;
}
return a;
}
2. 최소공배수(LCM) 구현
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
2) N수의 최대공약수, 최소공배수 구현방법
1. 최대공약수(GCD) 구현
💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든 수의 “최대공약수”를 구합니다.
1. result 변수를 배열의 첫 번째 값으로 초기화합니다
2. 반복문을 통해 배열의 나머지 값들과 최대공약수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최대공약수가 됩니다.
public static int gcd(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = gcd(result, arr[i]);
}
return result;
}
public static int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}
2. 최소공배수(LCM) 구현
💡 해당 부분에서는 int[] arr 파라미터로 받은 배열을 순회하면서 배열에 있는 모든수의 “최소공배수”를 구합니다.
1. result 변수를 배열의 첫 번째 값으로 초기화합니다
2. 반복문을 통해 배열의 나머지 값들과 최소공배수를 구하여 result 변수에 저장합니다.
3. 최종적으로 result 변수에 저장된 값이 배열에 있는 모든 수의 최소공배수가 됩니다.
public static int lcm(int[] arr) {
int result = arr[0];
for (int i = 1; i < arr.length; i++) {
result = lcm(result, arr[i]);
}
return result;
}
public static int lcm(int a, int b) {
return (a * b) / gcd(a, b);
}
오늘도 감사합니다. 😀
반응형
'Java > Short 개발' 카테고리의 다른 글
[Java/Short] 배열, 리스트를 문자열로 변환 방법 : Array, List to String (0) | 2023.05.27 |
---|---|
[Java/Short] 카운트 Array/Map 구현방법: Counting Array, Counting Map (0) | 2023.05.13 |
[Java/Short] 배열/리스트 내의 최소값, 최대값 찾는 방법 : min, max (0) | 2023.05.02 |
[Java/Short] 배열/리스트 중복제거 방법 : 전체, 인접한 요소 중복 제거 (0) | 2023.05.01 |
[Java/Short] 문자열 <-> Date 타입 간의 변환 방법 : + Date 연산 (0) | 2023.04.29 |