기약 분수(irreducible fraction)의 알고리듬적 접근 - soo:bak

기약분수란?

기약분수는 더 이상 약분할 수 없는 분수를 말합니다.

즉, 분자와 분모가 서로소 관계일 때 해당 분수는 이미 가장 간단한 형태이며, 이를 기약 상태라고 합니다.

예를 들어,

• \(\frac{4}{6} \rightarrow \frac{2}{3}\) 은 약분 가능한 분수이고,
• \(\frac{2}{3}\) 은 기약 상태입니다.

---

알고리듬적 접근

기약분수로 만드는 핵심은 분자와 분모의 최대공약수(GCD)를 구한 뒤, 이를 기준으로 각각을 나눠주는 것입니다.

단계 정리

1. 분자와 분모가 주어졌다고 가정합니다. 예: a = 18, b = 24
2. \(\text{GCD}(a, b)\) 를 구합니다 → 6
3. 각각 GCD로 나눠줍니다 → \(\frac{18}{6} = 3, \frac{24}{6} = 4\)
4. 결과는 \(\frac{3}{4}\)

C++ 코드 구현 예시

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

pair<int, int> toReducedFraction(int a, int b) {
  int d = gcd(a, b);
  return {a / d, b / d};
}

알고리듬 구현은 매우 간단하지만, 다양한 문제에서 실용적으로 사용됩니다.

---

시간 복잡도

기약분수를 만드는 과정에서 핵심이 되는 GCD 계산은 유클리드 호제법으로 이루어지며, 그 시간 복잡도는 다음과 같습니다:

\[O(\log \min(a, b))\]

참고 : GCD(최대공약수)와 유클리드 호제법의 원리 - soo:bak

따라서 전체 알고리듬은 매우 빠르며, 수의 크기가 커져도 충분히 효율적으로 동작합니다.

---

활용 예시

• 분수 비교: 기약 상태로 바꿔놓으면 두 분수를 정수 곱셈 없이 비교할 수 있습니다.
• 기하 문제: 도형의 좌표 비율, 벡터 방향성 등을 단순화할 때 기약분수를 활용할 수 있습니다.

---

마무리

기약분수는 수학적으로는 단순한 개념이지만, 프로그래밍에서 다양한 경우를 깔끔하게 해결할 수 있는 구조를 가집니다.

최대공약수를 활용한 약분은 계산 속도와 정확성을 모두 확보할 수 있는 기본적인 방법으로,

알고리듬 문제 해결에 있어서도 매우 자주 등장합니다.

정수 간 연산으로 깔끔하게 처리할 수 있다는 점에서 부동소수점 계산보다 안정적이며, 다양한 분야에서 응용 가능한 실용적인 방법입니다.