🤔 사전 지식
유클리드 호제법? 어디서 들어본거는 같긴 한데…
최대공약수 비스무리 했던 것 같은 느낌…?
구현은 어떻게 하더라… 😫
💡 공부하기
📄 기본적인 개념
두 정수(숫자)의 최대 공약수(GCD;Greatest Common Divisor)을 계산하는 가장 효율적인 방법
최대공약수 : 나머지 없이 둘을 나눌수 있는 가장 큰 수
위처럼 소인수 분해한 결과를 비교하는 방식으로 진행됩니다.
중요한 건 이것을 코드로 짜는 것이 굉장히 까다로울 것 같다는 생각이 듭니다.
코드로 표현하는 방식을 잘 표현한 진행이 있어서 함께 보여봅니다.
이렇게 2개의 값의 나머지가 0이 될 때까지 반복하게 됩니다.
수학적인 방법의 증명도 있지만, 전체적인 흐름을 이해하는 것이 더 중요할 것 같습니다 ㅎㅎ
📑 중요 포인트
- 정수 n과 m의 최대공약수를 정할 때, 조건이 n<m으로 들어와야 한다.
- 종료 조건
- n이 0이면 종료
- m이 n으로 나누어 떨어진다면 종료
🔖 Sudo Code 작성
1. 정수 n과 정수 m이 n > m의 조건으로 입력됨
1-1. 아니라면 n과 m을 swap하기
2. m이 0이 되면, n이 결과가 됨
3. 다음과 같이, 변환하여 다시 반복함
3-1. n = m
3-2. m = n % m💻 Full Code 구현하기
재귀함수 1
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(GCD(2, 4)); // 2
System.out.println(GCD(4, 2)); // 2
System.out.println(GCD(72, 90)); // 18
System.out.println(GCD(90, 72)); // 18
}
public static int GCD(int n, int m) {
if (n <= m) {
int temp = n;
n = m;
m = temp;
}
if (m == 0) return n;
return GCD(m, n % m);
}
}재귀 함수 2 - 삼항연산자 활용
public class Main {
public static void main(String[] args) throws Exception {
System.out.println(GCD(2, 4)); // 2
System.out.println(GCD(4, 2)); // 2
System.out.println(GCD(72, 90)); // 18
System.out.println(GCD(90, 72)); // 18
}
public static int GCD(int n, int m) {
if (n <= m) {
int temp = n;
n = m;
m = temp;
}
return m ? GCD(m, n % m) : n;
}
}여기서 재미있는 건, 원론적인 조건인 n과 m의 대소비교(n>m)을 지키기 위해 swap를 진행했습니다.
하지만 학부나 초기 알고리즘을 학습할 때에 코드는 swap과정이 없었습니다.
이 때, 과제가 과연 맞는것일까 생각이 들어서 결과를 출력해보았습니다.
public class Solution {
public static int N = 100;
public static void main(String[] args) throws Exception {
for (int i =0;i < N;i++) {
for (int j = 0; j < N; j++)
System.out.print(GCD(i, j) + "\t" + GCD(j, i) + "\t||\t");
System.out.println();
}
}
public static int GCD(int n, int m) {
if (m == 0) return n;
return GCD(m, n % m);
}
}
갓뎀 ㅋㅋ 이런 방식으론 어디가 다른지 확인할 수 없어서,
다음과 같이 if (*GCD*(i, j) != *GCD*(j, i)) 조건을 추가했습니다.
하지만, 결과가 다르게 출력되는 부분이 없었습니다.
N의 조건을 100 ~ 10,000까지 늘려보았지만, 역시 동일하였습니다.
근본적인 원인이 궁금해 손으로 직접 작성해보았습니다.
진행 순서는 조금 달랐지만, m의 값이 n으로 변동되면서 같은 흐름을 진행했습니다.
이것을 직접 보고 나니 왜 이렇게 될 수 있는지도 이해했습니다.
GCD는 두 수의 최대공약수 뿐만이 아니라, 다양한 내용을 알 수 있습니다.
추가적으로 알 수 있는 내용을 더 알아보도록 하겠습니다.
- 최소공배수(LCM)는 공통된 배수를 의미해, (n * m) / GCD로 진행한다면 구할 수 있게 됩니다.
- 서로소는 수 사이의 공약수가 1밖에 없을 때기에, GCD(n, m) == 1일 경우 찾을 수 있습니다.
🧐 요약&정리
- 유클리드 호제법(Euclidean algorithm)
: 두 수의 나머지 연산을 사용해, 최대공약수(GCD;나머지 없이 나눌 수 있는 수)를 구할 수 있는 알고리즘
public static int GCD(int n, int m) {
return m == 0 ? n : GCD(m, n % m);
}- 최소공배수(LCM) : 수 사이의 공통 배수,
(n * m) / GCD(n, m); - 서로소(Coprime) : 수 사이의 최대 공약수가 1인 조건,
GCD(n, m) == 1
📚 관련 문제
baekjoon
programmers
🌐 참고 링크
