[나중에 찾아보기 위한 공부내용 ]
GCD (최대 공약수 )
유클리드 알고리즘
1) v가 u보다 크다면 u와 v의 값을 바꾼다
2) u= u-v
3) u가 0이면 v가 최대 공약수
0이 아니면 (1)돌아갑니다.
GCD (250, 30)
GCD (230, 30)
GCD (200, 30)
GCD (170, 30)
.........
GCD (10, 30)
GCD (30, 10)
GCD (20, 10)
GCD (0, 10)
GCD = 10 ;
[풀이 방법 ]
package algoridem;
public class Gcd {
public int get_gcd(int su, int su2) {
int t = 0 ; // 임시저장 변수
//su가 0보다 크면 while문은 실행된다.
while (su>0) {
// 만약 su2가 su보다 더 크다면
// 두수의 자리를 체인지 해준다.
if (su<su2) {
t = su; su = su2; su2=t;
}
//su -su2를 통해 최대 공약수를 찾기
su = su-su2;
}
return su2;
}
public static void main(String[] args) {
Gcd g = new Gcd();
System.out.println(g.get_gcd(280, 30));
}
}
[그러나]
[유클리드 알고리즘 개선 방법]
뺄셈 기반 알고리즘의 문제는 너무 많은 뺄셈을 요구 하기 때문에
나눗셈의 나머지를 구해 풀이를 해보자
GCD (su, su2) = GCD(su%su2,v) =GCD(v,u%v)
- su%su2 < su2
v가 0이 아니면
su = su% su2
su와 su2를 교환
처음으로 돌아감
su2가 0이면 su가 GCD(최대공약수)
[개선된 풀이 방법 ]
package algoridem;
public class Gcd {
public int get_gcd(int su, int su2) {
int t = 0; // 임시저장 변수
// su가 0보다 크면 while문은 실행된다.
while (su2 > 0) {
t = su % su2;
su = su2;
su2 = t;
}
return su;
}
public static void main(String[] args) {
Gcd g = new Gcd();
System.out.println(g.get_gcd(280, 30));
}
}
[재귀함수]
return=0;
[생각하며 코딩을 정리 해보기 ]]
1.su가 0이면 su2 가 최대공약수 이기에
2.0 이되면 최대공약수의 값이 나온것으로보고
3.반복문을 멈추기 위해서
4.while의 조건은 su>0을 만들어서 반복문을 돌리고
5.su 가 작아지면 false를 만들어서
6.앞의 조건의 su가 0임을 만들어낸다.
7. if 만약 v가 u보다 크면 두 수의 자리를 바꾸고
계산한다
그러나 이러한 방식은 뺄셈을 통해 계속적으로 계산해서
마지막의 값을 얻어내기 때문에 효과적이지 못하다
[개선된 알고리즘]
이 연산에서 su-su2로 su가 0이 될때까지 계산하는 것이므로
su2값이 공통되게 뺄셈이 되기 때문에 su%su2 계산을 하면
더 빠르게 연산을 진행할 수 있다.
1. su% su2의 나머지 값을 t에 저장하고
su 에 su2의 값을 저장한다.
su2에 t의 값을 저장하고
while su2가 false가 될때까지 계속 연산한다.
false가 되면 while문을 빠져나가게 되고 결국에는
su값을 리턴하면된다.
[재귀함수]
v==0 이되면 리턴 값은 su로한다 .
재귀 함수를 통해
v가 0이 아닐 때까지 리턴하는 방법으로
매개변수의 값을 su2 값과 su%su2값을 매개변수로 넣어서
먄약 su의 값이 280이고 su2값이 30이면
public int gcd(int su, int su2){
// 생략
else gcd ( su2, su%su2);
}
값을 교차해서 넣어서 su2의 매개변수값을 나머지로 만든다
public int gcd(int su, int su2){
if 문을 이용해 su2 가 나머지를 구하는 방식이므로
su2가 0이 되면,
su의 값을 리턴하면된다.
else gcd ( su2, su%su2);
}
