4000년 전 이집트 분수가 알고리즘 문제로 돌아왔다: 분수를 1/n들의 합으로 쪼개기

학교에서 배운 분수와 좀 다른 분수

우리가 학교에서 배운 분수는 3/4, 5/7처럼 분자랑 분모를 자유롭게 쓰잖아요. 그런데 고대 이집트 사람들은 좀 달랐어요. 이들은 분자가 무조건 1인 분수, 그러니까 1/2, 1/3, 1/5 같은 것만 썼거든요. 이걸 "단위 분수(unit fraction)"라고 부르는데, 말 그대로 1을 뭔가로 나눈, 분자가 1인 분수예요.

그럼 3/4 같은 건 어떻게 표현했을까요? 단위 분수 여러 개를 더해서 나타냈어요. 예를 들어 3/4는 1/2 + 1/4로 쓰는 식이죠. 여기에 규칙이 하나 더 있었는데, 같은 분수를 두 번 쓰면 안 됐어요. 1/4 + 1/4 + 1/4처럼 쓰는 건 반칙이었던 거예요. 이렇게 서로 다른 단위 분수들의 합으로 어떤 수를 표현하는 방식을 "이집트 분수(Egyptian fraction)"라고 불러요. 무려 4000년 전 파피루스에 적혀 있던 표기법인데, 지금 봐도 꽤 재밌는 수학 퍼즐이에요.

왜 개발자가 이걸 알아야 하냐면

여기서 개발자들이 솔깃해지는 부분이 나와요. 임의의 분수 a/b가 주어졌을 때, 이걸 서로 다른 단위 분수들의 합으로 "어떻게" 자동으로 쪼갤까? 이게 전형적인 알고리즘 문제거든요.

가장 유명한 방법이 탐욕 알고리즘(greedy algorithm)이에요. 탐욕 알고리즘이 뭐냐면, 멀리 내다보지 않고 매 순간 "지금 당장 가장 큰 한 입"을 떼어먹는 방식이에요. 이집트 분수에서는 이렇게 동작해요. a/b보다 크지 않으면서 가장 큰 단위 분수 하나를 떼어내고, 남은 만큼을 가지고 또 똑같이 반복하는 거죠. 수식으로는 "1을 b÷a의 올림값으로 나눈 것"을 떼어내면 돼요.

예를 들어 3/7을 쪼개볼게요.

• 3/7보다 크지 않은 가장 큰 단위 분수는 1/3이에요. (7÷3=2.33...이니 올림하면 3)
• 3/7 - 1/3 = 2/21이 남아요.
• 2/21보다 크지 않은 가장 큰 단위 분수는 1/11이에요.
• 2/21 - 1/11 = 1/231이 남아요. 어? 분자가 1이네요. 끝!

그래서 3/7 = 1/3 + 1/11 + 1/231이 나와요. 신기하게도 이 탐욕 알고리즘은 어떤 분수를 넣어도 반드시 끝나요. 한 번 돌 때마다 남은 분수의 분자가 무조건 줄어들거든요. 그러니 무한 루프 걱정 없이 언젠가 분자가 1이 되면서 끝나죠.

그런데 탐욕은 완벽하지 않아요

여기서 함정이 있어요. 탐욕 알고리즘이 항상 "답"은 주지만, 항상 "좋은 답"을 주는 건 아니에요. 방금 3/7을 1/3 + 1/11 + 1/231로 쪼갰는데, 분모에 231이라는 큰 수가 튀어나왔잖아요. 그런데 같은 3/7을 1/4 + 1/7 + 1/28로도 쓸 수 있어요. (28분의 7+4+1 = 12/28 = 3/7, 맞죠?) 분모가 훨씬 작고 깔끔하죠.

그러니까 "단위 분수 개수를 최소로" 하거나 "분모를 최대한 작게" 만드는 최적의 표현을 찾는 건 탐욕만으로는 안 돼요. 이게 의외로 어려운 문제라서, 수학자들이 지금도 연구하는 영역이에요. 대표적으로 에르되시-스트라우스 추측(Erdős–Straus conjecture)이라는 게 있는데, "4/n은 항상 단위 분수 3개의 합으로 쓸 수 있다"는 가설이에요. 너무 당연해 보이는데도 아직 완전히 증명이 안 됐어요.

한국 개발자에게 주는 의미

사실 이집트 분수를 실무에서 쓸 일은 거의 없어요. 그런데도 이게 코딩 테스트나 알고리즘 공부에 좋은 소재인 이유가 있어요. 탐욕 알고리즘이 항상 정답을 주지는 않는다는 걸 손에 잡히게 보여주는 예제거든요. 면접에서 "탐욕으로 풀면 되지 않나요?"라고 했다가 반례를 못 대면 곤란해지는데, 이집트 분수가 딱 그 반례 연습용이에요.

또 분수 계산을 정수만으로 정확하게 다루는 연습도 돼요. 부동소수점(float)으로 하면 오차 때문에 답이 틀어지지만, 분자/분모를 정수 쌍으로 들고 다니면 오차 없이 정확하게 계산할 수 있거든요. 금융 계산이나 정밀한 비율 처리할 때 쓰는 사고방식과 똑같아요.

한줄 정리: 4000년 전 표기법이 "탐욕은 답은 주지만 최적은 아니다"라는 알고리즘 교훈을 가장 우아하게 보여주는 예제로 살아남았어요. 여러분은 탐욕 알고리즘이 실패하는 반례, 면접에서 바로 떠올릴 수 있으세요?

---

🔗 출처: Hacker News