유클리드 호제법

▶ BufferedReader, StringTokenizer, 유클리드 호제법을 활용한 간단한 문제가 있어 정리해보고자 합니다. 문제설명입력 & 출력나의 풀이 이번 문제는 간단하게 최대공약수와 최소공배수를 구현할 수 있는지 알아보는 문제입니다. 최소 공배수를 구하기 위해선 최대 공약수를 먼저 구해야 합니다. 최대 공약수를 구하기 위하여 gcd() 함수를 선언해주고, 유클리드 호제법으로 구현했습니다. 먼저 유클리드 호제법을 사용하기 위해선 큰 값과 작은 값을 구해줘야 합니다. Math클래스의 min()과 max() 메소드를 사용하여 구해줍니다. 유클리드 호제법은 나머지가 0이기 전 값을 반환해야 하기 때문에 일 때 큰 값을 반환해 주도록 if문으로 분기처리 해줬습니다. 만약에 0을 구하지 못했으면 다시 제..

1. 유클리드 호제법이란? 유클리드 호제법(- 互除法, Euclidean Algorithm) 유클리드(Euclid)에 의해 기원전 300년경에 발견된 가장 오래된 알고리즘 중 하나이며, 두 개의 정수 or 다수의 자연수에서 최대공약수(gcd)를 구하는 방법입니다. 이때 호제법이라는 말은 두 수가 서로 상대방 수를 나누어서 원하는 수를 얻는 알고리즘을 의미합니다. 2. 유클리드 호제법으로 최대공약수 구하기 나머지가 0이 될때까지 계속 재귀적으로 구해줘야합니다. 1. a, b (a> b) 두 수를 큰 수를 작은 수로 나눠 나머지(R1)를 구합니다. R1 = (a % b), R1!= 0 2. b % R1을 나눠서 나머지(R2)를 구합니다. R2!= 0 3. R1 % R2을 나눠 나머지(R3)를 구합니다. R3..