KDT 실무형 스프링 백엔드 엔지니어 양성과정 6기 | Algorithm CODEKATA
🆎 최대공약수와 최소공배수
🏷 관련 주제 : Math Greatest Common Divisor Least Common Multiple
✔️ Solution with 직접 나눠보며 최대공약수 찾기
class Solution {
public int[] solution(int n, int m) {
int[] answer = {0, n * m};
int minN = Math.min(n, m);
for (int i = Math.min(n, m); i > 0; i--) {
if (n % i == 0 && m % i == 0) {
answer[0] = i;
answer[1] /= i;
break;
}
}
return answer;
}
}채점 결과
✔️ Solution with 소인수분해
class Solution {
public int[] solution(int n, int m) {
int[] answer = {1, 0};
int minN = Math.min(n, m);
for (int i = 2; i <= minN; i++) {
while (n % i == 0 && m % i == 0) {
answer[0] *= i;
n /= i;
m /= i;
}
}
answer[1] = answer[0] * n * m;
return answer;
}
}채점 결과
✔️ Solution with 두 수 중 하나가 0이 될때까지 나누어 최대공약수 찾기
class Solution {
public int[] solution(int n, int m) {
int[] answer = {0, n * m};
while (n != 0 && m != 0) {
n %= m;
if (n == 0) {
answer[0] = m;
answer[1] /= m;
break;
}
m %= n;
if (m == 0) {
answer[0] = n;
answer[1] /= n;
break;
}
}
return answer;
}
}채점 결과
💥 오늘 만난 문제 & 나의 시도 💦 & 해결 방법 👍
📌 오늘 만난 문제 : 두 수를 입력받아 두 수의 최대공약수와 최소공배수를 반환하는 함수, solution을 완성해 보세요.
배열의 맨 앞에 최대공약수, 그다음 최소공배수를 넣어 반환하면 됩니다.
- 공약수 : 두 개 이상의 자연수의 공통된 약수
- 최대 공약수(Great Common Divisor) : 공약수 중 가장 큰 공약수
- 공배수 : 두 개 이상의 자연수의 공통된 배수
- 최소 공배수(Least Common Multiple) : 공배수 중 가장 작은 공배수
n, m의 최대공약수를 G, 최소공배수 L라고 할 때, 다음과 같이 나타낼 수 있다.
(단, a, b는 서로소)
먼저, n, m을 나눈 몫이 서로소가 될 때까지 공약수로 나누고
나눈 공약수들을 모두 곱하여
n과 m의 최대공약수 G를 구한다.
$L = G \times a \times b$
를 이용해 최대공약수 L을 구하거나
n * m에 최대공약수 G을 나누면 최소공배수 L을 구할 수 있다.
최대공약수를 구하는 방법
1. 직접 모든 수를 나눠보며 공약수, 그 중 최댓값을 찾는 방법
: 반복문을 통해 n과 m에 직접 나누기
큰 수는 작은 수를 나눌 수 없으므로
n과 m중 작은 수를 시작 값으로 점차 값을 1씩 줄여 나가며 공약수를 찾으면 처음으로 나오는 공약수가 최대 공약수이다.
2. 소인수분해를 이용한 방법
: 반복문을 통해 모든 n과 m을 나누는 소수들을 모두 찾아 곱하면 최대공약수가 된다.
3. n과 m중 한 수가 0이 될때까지 나누기
💬 무엇을 새롭게 알았는지
풀이를 작성하면서 최대공약수, 최소공배수와 관련된 개념을 정리해 볼 수 있었고
Latex 작성하는 법도 익힐 수 있었다.
