기약분수, 서로소, 최대공약수(GCD), 유클리드 호제법, 추가) 최소공배수(LCM)

알고리즘 풀이중에 "기약분수로 출력하세요" 란 문제를 만났습니다.

수학용어들이 낮설게 다가옵니다.

 

기약분수(Irreducible fraction) 

분자와 분모의 공약수가 1뿐이어서 더 이상 약분되지 않는 분수.

공약수가 1뿐인 두 수를 서로소 라고 함.

기약(旣約) : 이미 약분된

 

'그럼 a/b의 기약분수를 구하려면 둘 중 작은 수부터 1씩 줄여가면서 둘다 나누어 떨어지는 수로 나누어 가면 되겠다.' 라고 생각했다가, 그게 공약수일테고, 최대공약수(Greatest Common Divisor)를 구하면 되겠구나로 이어집니다.

1식 줄여가면서 둘다 나누어 떨어지는 첫번째 수가 최대공약수 이겠네요..

그런데 이렇게 무식하게 처리하면.. 100,98의 경우는 최대공약수 2를 구하기 위해서 많은 계산을 하게 됩니다.

알고리즘을 이용합니다.

 

유클리드 호제법

호제(互除) : 서로 나눔

 

재귀처리

int gcd(int a, int b)
{
	return b ? gcd(b, a%b) : a;
}

반복처리

int gcd(int a, int b)
{
    int c;
	while(b)
	{
		c = a % b;
		a = b;
		b = c;
	}
    return a;
}

 

100,98의 경우는 

----------------------------------------------

gcd(100,98) >> gcd(98,2) >> gcd(2,0)

----------------------------------------------

로 몇번 만에 최대공약수(GCD)를 구합니다.

 

문제의 분자, 분모를 최대공약수(GCD)로 나누어 기약분수를 제출했습니다.

 

 

추가)

최소공배수(Least Common Multiple, Lowest Common Multiple)도 최대공약수(GCD)를 이용해서 계산할 수 있네요.

lcm = a*b / gcd(a,b);