프로그래밍에서 분수 연산은 자주 만나게 되는 고전적인 문제 중 하나입니다. 분수 a/b와 c/d가 입력으로 주어졌을 때(a, b, c, d는 0이 아닌 임의의 정수), 이 두 분수를 더해 최종 합을 구하는 것이 이번 글의 목표입니다.
분수의 기본 개념
- 분수는 a/b 형태로 표현되며, 여기서 a는 분자(numerator), b는 분모(denominator)라고 부릅니다.
- 분자와 분모에는 어떤 수든 올 수 있지만, 분모는 절대 0이 될 수 없습니다.
- 두 분수의 합은 a/b + c/d로 나타내며, 덧셈의 기본 규칙은 분모가 반드시 같아야 한다는 것입니다. 분모가 다르면 먼저 통분을 통해 분모를 일치시킨 뒤에만 덧셈을 수행할 수 있습니다.
예제
예제 1: 분모가 다른 경우
입력 : 1/4 + 2/12 출력 : 5/12
두 분수의 분모가 서로 다르므로 GCD(최대공약수) 또는 LCM(최소공배수)을 계산해 분모를 통일해야 합니다. 이 예제에서는 분모 4에 3을 곱해 12로 맞출 수 있습니다.
(1 × 3) / (4 × 3) = 3/12 3/12 + 2/12 = 5/12
예제 2: 분모가 같은 경우
입력 : 1/4 + 2/4 출력 : 3/4
두 항의 분모가 이미 같으므로 별도의 통분 과정 없이 바로 더할 수 있습니다.
알고리즘
함수 int gcd(int a, int b) 1단계 → a == 0이면 b를 반환한다 2단계 → gcd(b%a, a)를 반환한다 함수 void smallest(int &den3, int &n3) 1단계 → common_factor를 gcd(n3, den3)로 선언 및 초기화한다 2단계 → den3 = den3 / common_factor 로 설정한다 3단계 → n3 = n3 / common_factor 로 설정한다 함수 void add_frac(int n1, int den1, int n2, int den2, int &n3, int &den3) 1단계 → den3 = gcd(den1, den2) 2단계 → den3 = (den1 * den2) / den3 // 최소공배수(LCM) 계산 3단계 → n3 = (n1) * (den3/den1) + (n2) * (den3/den2) 4단계 → smallest(den3, n3) 함수를 호출한다 함수 int main() 1단계 → n1=1, den1=4, n2=2, den2=12, den3, n3을 선언 및 초기화한다 2단계 → add_frac(n1, den1, n2, den2, n3, den3)을 호출한다 3단계 → 결과 값을 출력한다
C 코드 구현
#include <stdio.h>
int gcd(int a, int b) {
if (a == 0)
return b;
return gcd(b % a, a);
}
void smallest(int &den3, int &n3) {
// 두 항의 최대공약수(GCD)를 구함
int common_factor = gcd(n3, den3);
den3 = den3 / common_factor;
n3 = n3 / common_factor;
}
void add_frac(int n1, int den1, int n2, int den2, int &n3, int &den3) {
// den1과 den2의 최대공약수를 구함
den3 = gcd(den1, den2);
// LCM × GCD = a × b 공식을 이용해 최소공배수(LCM) 계산
den3 = (den1 * den2) / den3;
// 분모를 동일하게 맞춘 뒤 최종 분수의 분자를 계산
n3 = (n1) * (den3 / den1) + (n2) * (den3 / den2);
smallest(den3, n3);
}
// 드라이버(실행) 프로그램
int main() {
int n1 = 1, den1 = 4, n2 = 2, den2 = 12, den3, n3;
add_frac(n1, den1, n2, den2, n3, den3);
printf("%d/%d + %d/%d = %d/%d\n", n1, den1, n2, den2, n3, den3);
return 0;
}
참고: 위 코드의 참조(&) 매개변수 문법은 실제로는 C++ 스타일입니다. 순수 C 환경에서 컴파일하려면 포인터(int *)로 선언하고, 호출 시 &n3, &den3처럼 주소를 전달하면 동일하게 동작합니다.
실행 결과
1/4 + 2/12 = 5/12
마무리
이 프로그램의 핵심은 세 가지입니다. 첫째, 유클리드 호제법으로 구현한 gcd() 함수를 통해 최대공약수를 빠르게 구하고, 둘째, "LCM × GCD = 두 수의 곱" 공식을 활용해 공통 분모를 계산하며, 셋째, 마지막에 smallest() 함수로 결과 분수를 기약분수(더 이상 약분할 수 없는 형태)로 정리하는 것입니다. 이 흐름만 제대로 이해하면 어떤 분수 덧셈 문제든 손쉽게 해결할 수 있습니다.