파이썬으로 숫자 팩토리얼의 후행 0 개수 세기

이 글에서는 주어진 문제 상황에 대한 해결 방법을 자세히 알아보겠습니다.

문제 정의

문제 — 정수 n이 주어졌을 때, n! (팩토리얼) 값의 끝에 연속해서 나타나는 0의 개수를 구해야 합니다.

예를 들어 5! = 120이므로 후행 0은 1개이고, 10! = 3628800이므로 후행 0은 2개입니다.

접근 방법

팩토리얼 값의 뒤에 붙는 0은 곱셈 과정에서 2와 5가 한 쌍씩 만날 때마다 생성됩니다. 팩토리얼 계산에서 2의 개수는 항상 5의 개수보다 많기 때문에, 후행 0의 개수는 결국 약수 중 5의 개수와 같습니다.

따라서 다음과 같은 수식(르장드르 공식)으로 표현할 수 있습니다.

후행 0의 개수 = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + ...

즉, 5의 거듭제곱으로 n을 나눈 몫들을 모두 더하면 됩니다. 이 방법은 실제로 팩토리얼을 계산하지 않고도 O(log n) 시간에 답을 구할 수 있어 매우 효율적입니다.

구현 예제

# 후행 0 개수 세기
def find(n):
    # 카운트 초기화
    count = 0
    # 5의 거듭제곱으로 나누며 카운트 갱신
    i = 5
    while (n / i >= 1):
        count += int(n / i)
        i *= 5
    return int(count)

# 드라이버 프로그램
n = 79
print("Count of trailing 0s " + "in", n, "! is", find(n))

실행 결과

Count of trailing 0s in 79 ! is 18

동작 원리 설명

n = 79인 경우를 살펴보겠습니다.

• ⌊79/5⌋ = 15 → 5의 배수가 15개
• ⌊79/25⌋ = 3 → 25의 배수(5를 두 개 포함)가 3개
• ⌊79/125⌋ = 0 → 반복 종료

따라서 총 후행 0의 개수는 15 + 3 = 18개가 됩니다.

시간 복잡도

이 알고리즘은 매 반복마다 i가 5배씩 증가하므로 시간 복잡도는 O(log₅ n)입니다. 거대한 수의 팩토리얼이라도 즉시 결과를 얻을 수 있습니다.

결론

이 글에서는 파이썬을 사용하여 숫자의 팩토리얼에서 후행 0의 개수를 효율적으로 계산하는 방법을 배웠습니다. 팩토리얼 값을 직접 구하지 않고 5의 개수만 세는 수학적 접근 덕분에 매우 큰 입력값에도 빠르게 동작합니다.