이집트 분수란?
이집트 분수는 양의 유리수를 서로 다른 단위분수의 합으로 나타내는 방식입니다. 단위분수란 \(\frac{1}{2}\), \(\frac{1}{3}\), \(\frac{1}{7}\)처럼 분자가 1인 분수를 말합니다. 고대 이집트인들은 (\(\frac{2}{3}\)을 나타내는 특별한 기호를 제외하면) 모든 분수를 이런 방식으로 표기했습니다. 이 계산기는 여러분이 입력한 진분수를 자동으로 이런 합의 형태로 변환해 줍니다.
계산기 사용 방법
진분수(분자가 분모보다 작은 분수)의 분자와 분모를 입력하세요. 계산기는 먼저 분수를 기약분수로 약분한 다음, 탐욕 알고리즘을 적용해 전체 분해 결과와 그 안에 포함된 단위분수의 개수를 함께 보여줍니다.
공식 설명
피보나치와 실베스터가 고안한 것으로 알려진 탐욕 알고리즘은 가능한 가장 큰 단위분수를 반복해서 빼내는 방식입니다. 남은 분수 \(\frac{a}{b}\)에 대해 다음 분모는 \(d = \left\lceil \frac{b}{a} \right\rceil\)로 정해지며, 여기서 \(\frac{1}{d}\)를 빼면 새로운 분수 \(\frac{a\cdot d - b}{b\cdot d}\)가 됩니다. 이 분수를 다시 약분한 뒤 같은 과정을 반복합니다.
$$\begin{gathered} \frac{\text{Numerator } a}{\text{Denominator } b} = \frac{1}{d_1} + \frac{1}{d_2} + \cdots + \frac{1}{d_k} \\[1.5em] \text{where}\quad \left\{ \begin{aligned} d_i &= \left\lceil \frac{b}{a} \right\rceil \\ \frac{a}{b} &\to \frac{a\,d_i - b}{b\,d_i} \quad (\text{reduced, then repeat}) \end{aligned} \right. \end{gathered}$$매 단계마다 분자가 반드시 작아지기 때문에, 이 과정은 언제나 끝이 납니다.
예제로 살펴보기
\(\frac{5}{6}\)을 예로 들어보겠습니다. \(d = \left\lceil \frac{6}{5} \right\rceil = 2\)이므로 \(\frac{1}{2}\)를 먼저 떼어냅니다. 남은 값은
$$\frac{5}{6} - \frac{1}{2} = \frac{2}{6} = \frac{1}{3}$$입니다. 이미 단위분수이므로 분해 결과는 \(\frac{1}{2} + \frac{1}{3}\)이 되며, 단위분수 2개를 사용합니다. 직접 확인해 볼까요?
$$\frac{1}{2} + \frac{1}{3} = \frac{3}{6} + \frac{2}{6} = \frac{5}{6} \checkmark$$자주 묻는 질문
이집트 분수 분해는 유일한가요? 아닙니다. 하나의 분수를 단위분수로 나타내는 방법은 여러 가지가 있으며, 탐욕 알고리즘은 그중 유효한 한 가지 표현만 만들어 줍니다.
왜 분수들이 서로 달라야 하나요? 이집트 분수는 정의상 서로 다른 분모를 사용합니다. 바로 이 점 때문에 단순히 \(\frac{1}{b}\)를 여러 번 더하는 것이 아니라, 탐욕 알고리즘이 흥미로운 의미를 갖게 됩니다.
분모가 아주 커질 수도 있나요? 네. 탐욕 알고리즘은 간단해 보이는 분수에서도 놀라울 만큼 큰 분모를 만들어낼 수 있는데, 이는 이 방식의 잘 알려진 단점 중 하나입니다.
