알고리즘) 유클리드 호제법
2023. 12. 29. 20:53ㆍ알고리즘/개인공부
먼 과거, ‘유클리드’ 라는 사람이 적은 책의 내용으로 2개의 자연수 또는 정식의 최대공약수를 구하는 가장 오래된 알고리즘으로도 알려저 있다. 먼저 호제법의 의미는 두 수가 서로 상대방의 수를 나누어서 결국 원하는 수를 얻는 알고리즘 방식을 뜻하며, 이 유클리드 호제법의 개념은 다음과 같다.
2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라서, b를 r로 나눈 나머지 r’를 구하고, 다시 r을 r’로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수이다.
추가로, 최소공배수를 구하는 방법은 두 수 a, b를 곱한 수에 최대공약수를 나누어 나온 몫이 바로 최소공배수이다.
// 프로그래머스 최대공약수 최소공배수 구하는 문제
using System;
public class Solution {
public int[] solution(int n, int m) {
// 유클리드 호제법을 사용해서 최대공약수를 구한 다음
// 최소 공배수는 구하는 두 수의 곱에서 최대공약수를 나누어서 구한다
int[] answer = new int[2];
int min = 0; // min은 최대공약수
int max = 0; // max는 최소공배수
min = gcd(n, m);
max = (n*m) / min;
answer[0] = min;
answer[1] = max;
return answer;
}
public int gcd(int n, int m)
{
if(m == 0) return n;
else return gcd(m, n%m);
}
}
'알고리즘 > 개인공부' 카테고리의 다른 글
다익스트라 알고리즘(Dijkstra) (0) | 2024.07.15 |
---|