팩토리얼의 끝 0의 개수 구하기

본 컨텐츠는 데스크탑 환경에 최적화되어 있습니다.

1. 들어가며

오늘 다룰 알고리즘은 팩토리얼 0의 개수에 대한 해답이다. 이런 류의 문제들이 개발자 면접 시 등장한다는 첩보가 입수되었고 나도 풀어보게 되었다.

백준에 등장하는 문제다보니 관련된 포스트가 많았는데 어떻게 차별화를 할까 하다가, 단순무식하게 푼 뒤에 원 문제의 부분문제를 정의하고 이를 활용해 문제를 보다 유려하고 효율적으로 풀 수 있는 방법으로 옮겨갈까 한다.

2. 문제 소개

이 문제는 어떤 자연수 N에서 \(N!\)의 뒤에서 0이 아닌 다른 수가 나올 때까지의 0의 개수를 세는 문제이다. 위의 \(100!\)의 뒤에는 24개의 0이 있다. 이렇게 100을 입력으로 받으면 24를 반환하면 된다.

2.1. 문제에 대한 직관

‘124000’이라는 수를 보자. 이 수는 ‘124’ * 1000’으로 나눌 수 있다. 이때 1000은 \(10^3\)이기 때문에 답이 3이 된다.

그러면 이 문제는 어떤 수가 10을 몇 개를 가지고 있냐로 다시 정의할 수 있고, 우리는 10이 2와 5 하나씩으로 구성되는 것을 안다.

결국 우리가 할 것은 어떤 수를 소인수 분해했을 때 2와 5의 계승의 수를 파악하고 이 둘의 최소값을 반환하면 된다. 위의 저 숫자를 수인수 분해하면 2의 계승은 5, 5의 계승은 3인데 남은 여분의 2의 계승은 0을 만들어내지 못하기 때문이다. 매우 기초적인 직관으로 이 문제에 대한 다양한 풀이가 있지만 결국 모두 여기서 출발한다.

우리도 이 직관을 시작으로 문제를 풀도록 하자.

3. 문제 풀이

나는 문제를 풀 때 원 문제를 부분문제로 분해해 이들을 조합해 문제를 푸는 것을 좋아한다. 직관 하나로 코드에 옮기면 어지간히 쉬운 문제가 아니면 풀 수가 없고, 풀어도 효율적이지 못할 확률이 높다.

먼저 직관으로 시작해 답을 도출해낸다. 다음은 바로 문제에 뛰어들지 않고 부분문제로 나눈 뒤 이를 통해 통찰을 이끌어내서 문제를 푼다. 그러면서 동적 계획법을 사용할 생각이다. 코드 자체보다는 알고리즘을 이끌어내기까지의 과정을 눈여겨보길 바란다.

3.1. 무식하게 풀기

이 방법은 우리의 직관에서 바로 시작한다. \(N!\)을 소인수 분해해 2와 5의 계승을 세서 이의 최소값을 반환하자.

이때 N이 100만 되어도 \(100!\)은 364자리의 미친 숫자이기 때문에 오버플로우의 위험이 있다. 그러니 팩토리얼을 직접 계산하지 말고 1부터 N까지 순회하면서 각 숫자가 가지고 있는 2와 5의 개수를 더해나가자.

def count_zero(N):
    two = 0
    five = 0

    for n in range(1, N+1):
        while n % 2 == 0:
            two += 1
            n //= 2

        while n % 5 == 0:
            five += 1
            n //= 5

    return min(two, five)

상당히 단순하고 직관적인 코드다. 1부터 N까지 순회하면서 각 수가 가지고 있는 2와 5의 개수를 전부 더해나간다. 마지막에는 이 둘의 최소값을 반환하면 된다.

이 코드의 시간복잡도는 어떻게 될까? 1부터 N까지 순회하기에 \(n\)이 나오고, 각 반복문 안에서 숫자를 2와 5로 나눠나가기 때문에 \(logn\)이 된다. 따라서 최종 시간복잡도는 \(O(nlogn)\).

이 문제를 푸는 가장 단순한 방법이지 않나 싶다. 문제 자체가 쉽기 때문에 이 문제는 이렇게 직관으로 바로 코드에 옮기는 것도 나쁘지는 않다. 하지만 내가 푼 방식은 조금 다르며 보다 효율적이기도 하다.

3.2. 효율적으로 풀기

문제가 쉽다고 그냥 직관으로 때려박지 말고, 문제를 우리의 언어로 다시 정의하자.

\[ \text{count_trailing_zeros(N): } N!\text{의 끝 0의 개수를 반환} \]

원 문제이자 인터페이스인 count_trailing_zeros 함수를 정의했다. 이 함수는 정수 N을 받아 N!의 뒤의 0의 개수를 셀 것이다. 이때 이름을 잘 지어줘야 한다. 뒤에 붙는 0이라는 의미에서 ‘trailing’이라는 이름을 추가해줬는데 이게 꼭 필요하다. 이 의미가 없으면 ‘10100’의 숫자의 답이 3이 나와야하기 때문이다. 그래서 난 백준에 소개된 문제의 이름이 ‘0의 개수’라는 것이 문제가 있다고 생각한다. 아무리 문제 소개에는 뒷부분의 0이라는 것을 알려주지만 언제나 ‘이름’이 중요한데.

이 원 문제는 해결할 단위가 크다. 이 문제를 해결하기 위해 부분문제를 하나 정의했다.

\[ \text{count_factors(N, f): } N\text{이 소수 } f\text{를 몇 개 가지고 있는지를 반환} \]

count_factors는 정수 N과 f를 받아서 정수 N를 소인수 분해했을 때 f를 몇 계승 가지고 있는지를 반환한다. 좋다. 이 부분문제를 활용해 원 문제를 해결할 수 있을 것 같은데 아까 생각한 직관을 통해 원 문제와 부분문제의 관계를 다음과 같이 정리할 수 있다.

\[ \text{count_trailing_zeros(N)} = MIN( \displaystyle\sum_{i=1}^{N} \text{count_factors(i, 2)}, \displaystyle\sum_{i=1}^{N} \text{count_factors(i, 5)} ) \]

좋아. 여기까지 왔다. 큰 원 문제를 작은 부분문제의 조합으로 만들어놓으니 문제가 더 손에 잡히는 것 같다. 이제 count_factor를 구현해야 하는데 이를 어떻게 만들까?

많은 방법이 있겠지만 재귀적인 방법이 있다는 것을 알게 됐다.

\[ \text{count_factors(N, f)} = \begin{cases} \text{count_factors(N / f, f)} + 1 & \text{if N % f == 0} \\ 0 & \text{otherwise} \end{cases} \]

테스트해보라. 숫자 몇 개만 넣어도 정확히 동작한다는 것을 알게 될 것이다. 단순히 재귀함수로 짜도 되지만 이를 동적 계획법을 사용해서 1부터 N까지의 수에서 f가 2와 5일 때의 값을 더해 비교하면 되겠다.

그리고 한 번 더 통찰이 있다.

우리는 \(N!\)에서 2와 5의 개수를 셀 것이다. 소인수가 2일 때와 5일 때를 계산해서 더 작은 값을 선택할텐데 사실 두 값을 모두 계산할 필요가 없다. 어떤 팩토리얼 수에서도 5의 개수가 2의 개수보다 더 적거나 같기 때문이다.

\[ \text{a와 b는 소수, a < b 일 때}
\displaystyle\sum_{i=1}^{N} \text{count_factors(i, a)} >= \displaystyle\sum_{i=1}^{N} \text{count_factors(i, b)} \]

이는 조금만 생각해보면 당연함을 알 수 있는데 a, b가 자연수일 때는 성립하지 않는다.(예: 7, 8) 이제 우리는 N!에서 5의 개수만 세서 반환하면 되겠다.

이제 지금까지의 내용을 코드로 옮기자.

def count_trailing_zeros(N):
    # 1.
    cache = [-1] * (N+1)

    def count_factors(n, f):
        # 2.
        if cache[n] != -1:
            return cache[n]

        # 3.
        cache[n] = count_factors(n // f, f) + 1 if not n % f else 0
        return cache[n]

    # 4.
    ans = 0
    for i in range(1, N+1):
        ans += count_factors(i, 5)
    return ans

1. 1부터 N까지의 5의 개수를 저장할 cache 를 선언했다.
2. count_factors 함수를 정의했다.
   • 이 함수는 앞서 정리한 식을 충실히 재현한다. 단순 재귀대신 동적 계획법을 사용하는 이유는 반복 계산을 하지 않기 위해서이기 때문에 cache 에 미리 저장한 값이 있으면 다시 계산하지 않고 가져다 쓴다.
3. 미리 계산되지 않은 경우 직접 계산한다.
   • n 이 f 로 나눠떨어지지 않으면 0을 반환하고 아닐 경우 그보다 작은 값에 1을 더한다.
4. 1부터 N까지의 5의 개수를 모두 더해 반환한다.

이 함수의 시간 복잡도는 길이 N의 캐시를 채워나가기 때문에 \(O(n)\)이 되며 좀 전의 방식보다 효율적이다.

솔직히 말해서, 이 문제의 경우에는 동적 계획법보다 맨 처음에 직관만 사용해서 푼 방법이 더 쉬워보인다. 하지만 이것은 이 문제가 너무 쉬워서 그렇게 보이는 것이고 이보다 문제가 조금만 더 어려워지면, 직관만으로 무식하게 덤벼들다가 반드시 막히고 여러 예상 못한 난관에 빠지게 된다.

내가 여기서 말하고 싶은 것은 ‘동적 계획법 방법이 성능이 더 좋았다’가 아니라 문제를 부분문제로 분해하고 이를 정복해 원 문제를 푸는 습관을 들여야한다는 것이다. 언제나 문제를 푸는 것보다 문제를 이해하는 것이 더 어렵고 중요하다.

4. 마치며

팩토리얼 수에서 뒤의 0의 개수를 세는 문제를 풀었다. 문제의 특성상 쉽게 터득할 수 있는 직관만으로 무식하게 문제를 풀고, 다음은 문제 자체를 이해하고 부분문제를 활용해 이 문제를 해결했다. 어느 것이 더 좋은가? 난 하늘이 두쪽나도 아래 방법으로 풀고 싶다. 그럴 능력이 생기면 좋겠다.

아 그리고, 내가 소개한 방법 말고도 이 문제를 푸는 다른 방법도 있다. 이 포스트를 참고하면 되는데 이 분도 문제를 자신만의 방식으로 이해했고 보다 쉽게 푸셨다. 시간 복잡도가 \(O(logn)\)으로 더 효율적이다. 이 포스트도 참고하기를 바란다.

이상 포스트를 마칩니다.