두 분수를 더하는 방법

분수를 더하는 가장 복잡한 방법은 코드를 짜서 분수를 더하는 것이다. :? 하지만, 단발성이 아닌 작업에서는 손으로 계산하는 수고가 훨씬 덜하겠지만, 반복적인 작업에서는 코드를 짜서 분수를 더하면 손으로 계산하는 수고는 줄어들게 된다. :>

 

두 분수를 더할 때의 로직을 생각해보면, 다음과 같은 로직으로 생각해야 할 것이다.

1. 두 분수의 분모들의 '최대공약수'를 구함
2. 통분
3. 분자의 덧셈
4. 기약분수를 구하기 위해 '최대공약수'를 구함
5. 답 반환

 

이때, 로직을 구현하기 위한 주요 아이디어는 최대공약수를 구하는 방법을 구현하는 것이다. 최대공약수는 유클리드 알고리즘을 활용해서 구하고, 유클리드 알고리즘은 재귀함수의 형태로 구현한다.

유클리드 알고리즘의 실행은 다음과 같다.

EUCLID(30, 21) = EUCLID(21, 9) // 30/21 = 1...9 중 나머지인 9가 EUCLID(a,b)의 b 자리에 오게됨.
		= EUCLID(9, 3)  // 21/9  = 2...3 중 나머지인 3이 b 자리에 오게됨.
        	= EUCLID(3, 0)  // 9/3 = 3...0 이므로 b=0이므로 분모에 올 수 없으므로 a값을 반환.
        	= 3

위 내용을 재귀함수로 구현하면 다음과 같다.

int gcd(int a, int b) // 단, a, b는 음이 아닌 정수
{
	if(a%b==0) return b;
    else return gcd(b, a%b);
}

따라서 위 로직을 통해 구현하면 문제에 대한 코드 구현을 쉽게 할 수 있다.

 

요즘엔 검색만 하면 원하는 정보가 다 나오기에, 코드를 구현하는 것보다는 아이디어를 잘 떠올리는 게 굉장히 중요한 것 같다. 알고리즘 책을 잘 훑어보고, 앞으로 해결할 문제들의 아이디어에 기여할 수 있게끔 연습해봐야겠다.

 

참고문헌 : Introduction to Algorithms 3rd Edition, 31.2 최대공약수, p.958