분수의 덧셈

첫 번째 분수의 분자와 분모를 뜻하는 numer1, denom1, 두 번째 분수의 분자와 분모를 뜻하는 numer2, denom2가 매개변수로 주어집니다.
두 분수를 더한 값을 기약 분수로 나타냈을 때 분자와 분모를 순서대로 담은 배열을 return 하도록 solution 함수를 완성해보세요.

제한 사항

• 0 <numer1, denom1, numer2, denom2 < 1,000

최대공약수를 반환하는 재귀함수를 이용하여 문제 풀이에 접근하였다.
최대공약수를 재귀함수를 이용해 알아내는 방법은 아래 코드와 같다.

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

위 재귀함수의 반복이 일어나다보면 최종적으로 두 정수의 최대공약수가 반환되고 이를 분수의 덧셈 함수로 나타내면 아래와 같다.

vector<int> solution(int numer1, int denom1, int numer2, int denom2) {
    vector<int> answer(2); // 반환할 벡터의 공간을 미리 0으로 초기화 시킨다.
    answer[1] = denom1*denom2; // 분모1 * 분모2
    answer[0] = numer1*denom2 + numer2*denom1; // 분자1 * 분모2 + 분자2 * 분모1
    
    int num = gcd(answer[0],answer[1]); // 최대공약수

    answer[0] /= num;
    answer[1] /= num;

    return answer;
}

위 과정에서, 공통 분모를 단순 두 분모의 곱으로 정하여 초기 answer 벡터의
0 인덱스에는 분자 값을, 1 인덱스에는 분모 값을 저장하였다.

이후 분자와 분모를 위에서 설명한 gcd함수(최대공약수 반환 재귀함수)를 이용하여 최대공약수를 구하였고 이를 변수 num에 저장하였다.
마지막으로 각 분자와 분모의 값을 최대공약수로 한 번 나누어 주면 기약분수 형태로 나타나게 된다.

분수를 기약분수로 만들기 위해선, 분자와 분모의 최대공약수를 이용한다는 간단한 수학적 배경을 필요로하는 풀이이다.

(+a)최대공배수

gcd함수에 대해서 알아보았는데, 이를 이용한 최대공배수를 구하는 코드는 아래와 같다.

int lcm(int a, int b){
    return (a * b) / gcd(a, b);
}

두 정수의 곱을 최대공약수로 나누어주면 최소공배수가 된다.

최대공약수, 최소공배수, 재귀함수