📖 TIL - "팩토리얼 함수에 이런 함정이?!" - 알고리즘 성능 개선기 🎯

📌 문제 상황

프로그래머스 "구슬을 나누는 경우의 수" 문제를 풀면서 발견한 흥미로운 이슈들

처음 작성한 코드

function factorial(num) {
    if(num === 0 || num === 1) return 1;
    return num * factorial(num - 1);
}

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

🤔 발견한 문제점들

1. 큰 수 입력 시 스택 오버플로우

   • 재귀 호출이 너무 깊어지면 발생
   • 예: solution(100, 50) 에서 크래시

2. JavaScript Number의 한계

   • 최대 안전 정수: 9007199254740991 (약 9천조)
   • 팩토리얼 계산 시 쉽게 초과됨

💡 해결 방법

1. BigInt 도입

function factorial(n) {
    let result = 1n;  // BigInt 사용
    for (let i = 2n; i <= BigInt(n); i++) {
        result *= i;
    }
    return result;
}

2. 재귀 → 반복문

• 재귀 대신 for문 사용으로 스택 오버플로우 방지
• 메모리 사용량 개선
• 실행 속도 향상

✨ 새롭게 배운 점

1. BigInt

• JavaScript의 새로운 숫자 타입
• 매우 큰 정수를 다룰 때 사용
• 숫자 뒤에 'n' 붙여서 표현 (예: 1234n)

2. 재귀 vs 반복문

• 재귀: 코드는 간단하지만 메모리 사용량 多
• 반복문: 코드는 길어지지만 성능 good

🚀 최종 개선 코드

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

function solution(balls, share) {
    if (balls < share) return 0;
    return Number(factorial(balls) / (factorial(balls - share) * factorial(share)));
}

⭐️ 교훈

1. 알고리즘 문제는 정확성뿐만 아니라 성능도 중요
2. JavaScript의 숫자 처리 한계를 항상 고려해야 함
3. "될 것 같은데?" 보다는 "반례는 없을까?"를 더 고민해보자!

이번 문제를 통해 단순히 수학적 로직을 구현하는 것을 넘어, 실제 프로그래밍에서 발생할 수 있는 다양한 기술적 제약과 해결 방법을 배울 수 있었다. 특히 BigInt의 존재는 놀라웠다! 😲