JavaScript에서 유리수를 단위분수의 합으로 분해하기

문제

정확히 두 개의 숫자로 이루어진 배열을 인수로 받는 JavaScript 함수를 작성해야 합니다.

첫 번째 요소는 어떤 유리수의 분자를, 두 번째 요소는 동일한 유리수의 분모를 나타냅니다.

이 함수는 각각 두 개의 요소를 가진 하위 배열들로 구성된 배열을 반환해야 합니다. 이때 하위 배열들이 나타내는 유리수들을 모두 더하면 입력된 유리수와 같아져야 하며, 모든 하위 배열의 분자는 반드시 1이어야 합니다.

또한 하위 배열의 개수는 가능한 한 최소가 되도록 만들어야 합니다.

이처럼 분자가 1인 분수(단위분수)의 합으로 유리수를 표현하는 것을 이집트 분수(Egyptian Fraction)라고 부르며, 본 문제는 대표적인 그리디(Greedy) 알고리즘 적용 사례로 널리 알려져 있습니다.

예시

다음은 해당 코드입니다 −

const num = '2/3';
const decompose = (num = '') => {
   let fractions = [];
   let res = eval(num);
   // 값이 1 이상이면 정수 부분을 먼저 분리
   if (res >= 1) {
      fractions = ['' + Math.floor(res)];
      res = res - Math.floor(res);
   }
   let sum = 0;
   let denom = 2;
   // 남은 값보다 작거나 같은 가장 큰 단위분수를 차례로 선택
   while (sum <= res - 0.000000001) {
      if (1 / denom + sum <= res) {
         fractions.push("1/" + denom);
         sum += 1 / denom;
      }
      denom++;
   }
   return fractions;
}
console.log(decompose(num));

코드 설명

이 코드는 다음과 같은 순서로 동작합니다.

먼저 eval()을 사용해 문자열 형태의 분수를 실수 값으로 변환합니다. 값이 1 이상인 경우에는 정수 부분을 결과 배열에 먼저 넣고, 소수 부분만 남겨 처리합니다.

이후 분모를 2부터 하나씩 늘려가며, 현재까지의 합에 해당 단위분수(1/denom)를 더해도 목표 값을 초과하지 않는 경우에만 배열에 추가합니다. 이 과정을 부동소수점 오차를 고려한 허용 범위(0.000000001) 내에서 합이 목표 값에 도달할 때까지 반복합니다.

이러한 탐욕적 선택 전략 덕분에 매 단계에서 가능한 가장 큰 단위분수를 우선적으로 사용하게 되며, 결과적으로 비교적 적은 수의 단위분수로 유리수를 분해할 수 있습니다.

출력

다음은 콘솔 출력 결과입니다 −

[ '1/2', '1/6' ]

즉, 2/3은 1/2 + 1/6의 합으로 분해되며, 이것이 주어진 조건을 만족하는 답이 됩니다.