[Algorithm] 효율적으로 조합 계산하기 : 팩토리얼 없이 나누기

 

조합 계산은 일상적인 프로그래밍 문제에서 자주 등장한다. 예를 들어. 여러 개의 아이템 중에서 일부를 고를 수 있는 경우나, 팀 구성, 경기 조합 등의 문제에서 자주 활용된다.

이때 조합을 계산하는 가장 일반적인 방법은 팩토리얼을 이용하는 방법이다. 조합 계산의 기본 공식은 다음과 같다.

하지만 팩토리얼을 이용해서 조합을 계산한 결과 특정 테스트 케이스에서는 작동이 되지 않는 문제가 발생하였다.

이에 대한 원인은 큰 수를 다룰 때 부동소수점 오차와 오버플로우 문제로 인해 발생하는 것이었다.

 

 

🔥 문제 1 : 부동 소수점 오차 (Floating-point Precision Error)

컴퓨터에서는 실수를 부동소수점 방식으로 저장한다. 부동 소수점 방식이란 실수를 일정한 자릿수로 근사하여 저장하는 방식이다.

이는 숫자를 일정한 자릿수로 정확하게 표현할 수 없다는 한계가 있다.

예를 들어, 0.1을 컴퓨터에서 정확히 표현할 수 없기 때문에, 계산 중에서 미세한 오차가 발생할 수 있다.

이 오차는 조합 계산과 같은 여러 숫자를 곱하거나 나누는 과정에서 점차 커질 수 있다.

 

console.log(0.1 + 0.2 === 0.3); // false

위 코드는 false를 출력한다. 이유는 0.1 + 0.2가 정확히 0.3으로 계산되지 않기 때문이다.

이처럼 부동소수점 계산에서 발생하는 미세한 오차가 조합 계산에 영향을 미칠 수 있다.

 

 

🔥 문제 2 : 오버플로우 (Overflow)

오버플로우는 계산 중에 숫자가 표현할 수 있는 범위를 초과하는 경우 발생한다.

특히 팩토리얼 계산에서는 숫자가 급격히 커지기 때문에 오버플로우가 발생할 위험이 있다.

 

예를 들어, 30!과 같은 큰 숫자는 쉽게 컴퓨터에서 표현할 수 있는 범위를 넘어설 수 있어 오버플로우가 발생할 수 있다.

 

 

 

 

# 팩토리얼을 이용해 조합을 계산할 경우

앞선 문제들이 발생할 수 있기 때문에 팩토리얼을 직접 사용하여 조합을 계산하는 방식에는 몇 가지 한계가 있다.

function factorial(n) {
    let result = 1;
    for (let i = 1; i <= n; i++) {
        result *= i;
    }
    return result;
}

function combination(balls, share) {
    return factorial(balls) / (factorial(share) * factorial(balls - share));
}

위 코드 구동 결과 balls나 share 값이 커질 경우 앞서 말한 오버플로우 문제가 발생할 수 있다.

 

 

 

# 팩토리얼을 이용하지 않은 방법

부동소수점 오차, 오버플로우 문제를 해결하기 위해 팩토리얼을 사용하지 않는 방법을 사용하여 효율적으로 조합을 계산할 수 있다.

function solution(balls, share) {
    let result = 1;
    for (let i = 0; i < share; i++) {
        result *= (balls - i) / (i + 1);
    }
    return Math.round(result);
}

이 방법은 조합 계산을 직접적으로 나누고 곱하는 방식으로 구현한다.

result *= (balls - i) / (i + 1)는 n! / (r! * (n - r)!)의 계산을 대신한다.

여기서 balls - i는 n!에서 곱할 값을 나타내고, i + 1은 r!에서 나눠야 할 값을 나타낸다.

 

Math.round(result)는 계산 결과를 반올림하여 반환한다.

 

즉, 중간에 큰 수를 다루지 않고 필요한 부분만 계산하므로 부동소수점 오차와 오버플로우 문제를 예방할 수 있다.

• 부동소수점 오차 : 나누기 연산을 중간에 진행함으로써 매우 큰 수를 한 번에 다루지 않아 팩토리얼 계산에 비해 부동소수점 오차가 적은편
• 오버플로우 방지 : 큰 수가 곱해지지 않기 때문에 오버플로우 방지 가능
• 효율적인 계산 : 팩토리얼을 직접 구하지 않고 나누고 곱하는 방식으로 계산을 진행하므로 중복 계산을 줄일 수 있다. 

 

 

 

따라서, 조합 계산에서 팩토리얼을 이용하는 방법은 간단하지만, 부동소수점 오차와 오버플로우 문제를 일으킬 수 있다.

이를 해결하기 위해 팩토리얼을 직접 계산하지 않고 필요한 값만 곱하고 나누는 방법을 사용하면 성능을 최적화하고 문제를 해결할 수 있다.

특히 대규모 숫자를 다루는 조합 계산에서 매우 유용하다.

 

 

---

References

https://school.programmers.co.kr/questions/10368

프로그래머스