23.04.18 Today I Learned

유클리드 호제법

유클리드 호제법이란?

두 양의 정수 a, b에 대하여 (a>b) r = a%b 일때, a,b의 최대공약수는 b,r의 최대공약수와 같다.

즉, gcd(a,b) = gcd(b,r)이고 r이 0이라면 a,b의 최대공약수는 b 이다. 

무려 인류 최초의 알고리즘이라 불린다.

 

이를 이용하면 알고리즘에 자주 나오는 최대공약수, 최대공배수, 서로소, 분수 덧셈등 다양하게 활용할 수 있다.

 

자바 코드로 구현해보자

 

1. 반복문 사용

public int getGcd(int a, int b){
	int r = 0;
    while(b!=0){
    	r = a%b;
        if(r == 0){
        	return b;
        }
        a = b;
        b = r;
    }
}

이렇게 반복문으로 표현할 수도 있지만 재귀 함수를 사용하면

2. 재귀 함수 사용

public int getGcd(int a, int b){
	if( b == 0 ){
    	return a;
    }
    return getGcd( b, a%b )

훨씬 더 간결하고 가독성 좋게 구현할 수 있다. (어제 정리한  if문 작성에 대한 규칙을 적용했다!!)

 

 

---

• BLOB, TEXT, VARCHAR의 차이와 사용 방법
• @Coulumn(nullable = false)
• DDL,DML, DCL
• if문 작성에 대한 규칙
• GeneratedValue AUTO vs IDENTITY
• Optional
• @Allargsconstructorlombok
• Git 플로우 전략
• if문 여러개 vs else if 의 차이
• @Transactional

---