백준 1676 팩토리얼 0의 개수 파이썬 풀이 - recursionError

https://www.acmicpc.net/problem/1676

1676번: 팩토리얼 0의 개수

 

코드 1

def factorial(num) :
    if num == 1:
        return 1
    else :
        return (num * factorial(num - 1))

n = int(input())
count = 0

num = factorial(n)
num = [x for x in str(num)]
for i in range(len(num) - 1, -1, -1):
    if num[i] == '0' :
        count += 1
    elif num[i] != '0' :
        break
print(count)

 

처음에는 재귀함수로 함수를 만들어서 풀었었는데 런타임에러가 떴다(코드 1). 파이썬은 low-level language들보다 연산이 느리다. 그래서 런타임에러가 뜬것이 아닐까? 찾아보니 아니나 다를까 파이썬은 다른 언어에 비해 상대적으로 재귀 깊이에 제한이 엄격하고 런타임에러가 더 잘 뜬다고 한다.

 

그렇다면 재귀 깊이가 어느 정도로 제한되어 있길래 엄격하다는 것일까?

import sys
print(sys.recurionlimit())

sys 라이브러리에서 1000이 출력되는 걸 확인할 수 있다. 파이썬에서 재귀함수를 쓸 때는 1000의 깊이를 넘어가게 되면 recursionError가 뜨기 때문에 주의해야 한다.

 

이에 대한 해결법은 없는가?

recursionError가 뜨지 않게 하는 방법이 존재하기는 한다. sys.recursionlimit("인자") 인자에 1000이상의 숫자를 주면 그만큼 늘어나게 된다. 다만 파이썬에서는 이런 방법을 추천하지 않는다. 경고를 무시하고 인자를 최대한도까지 늘리게 되면 스택 오버플루우가 발생하거나, 메모리가 소진되어 성능 저하가 오가나 완전히 정지하는 경우까지 생길 수 있다. 메모리를 늘려서 백준에 돌린 결과 메모리 초과가 떴다.

재귀함수는 점점 사용되지 않는 알고리즘으로 알고 있다. 적어도 개발에서는 사용하는 경우가 극히 드문 걸로 알고 있다. 재귀함수가 반복문으로 대체가 가능한데 굳이 재귀함수를 사용하지 않아도 될 듯하다.

 

각설하고 다시 문제로 돌아와서 수정된 코드를 보자.

코드 2

def factorial(num) :
    val = 1
    if num == 0 or num == 1 :
        return 1
    else :
        for i in range(2, num + 1) :
            val *= i
        return val

n = int(input())
count = 0

num = factorial(n)
num = [x for x in str(num)]
for i in range(len(num) - 1, -1, -1):
    if num[i] == '0' :
        count += 1
    elif num[i] != '0' :
        break
print(count)

 

같은 코드를 반복문으로 변경했을 뿐이다. 가뿐히 돌아갔다.

 

이 문제는 내 코드보다 더 확실하고 효율적인 코드가 존재했다. 문제는 그 작동원리가 이해가 안 됐었는데 겨우 이해한 걸 조금 설명해 보자면, 

 

코드 3

def number_of_zero(n) :
    count = 0
    i = 5
    while(n/i >= 1) :
        count += int(n / i)
        i *= 5
    return count

n = int(input())
print(number_of_zero(n))

 

이 방법을 이해하기 위해서는 왜 팩토리얼의 끝자리에 0이 나타나는가를 알아야 한다. 여러 자리 숫자(multi-digit)에서 0이 나타난다는 것은 10의 배수가 포함되기 때문이다. 또, 10은 2와 5를 곱해 만들 수 있다. 그렇다면 2와 5가 곱해질 때마다 끝에 0이 생겨난다고 볼 수 있는 것이다.

여기서 하나 더 짚고 넘어가야 하는 부분은 2는 항상 5보다 많다는 것이다. 왜??라는 의문이 생길 수 있다. 2의 배수는 2,4,6,8,10... 숫자 하나를 건너뛰면 바로 2의 거듭제곱, 2가 나타난다. 반면 5는 5, 10, 15, 20... 주기가 2보다 길다. 2보다 5가 더 적게 등장하니까 5의 개수를 세야 한다.

그럼 이제 왜 i에 거듭제곱을 하는지에 대해 알아보자. 5! 에는 5가 한번 나온다. 10! 에는 5를 포함한 숫자가 2번 나온다(5, 10). 이처럼 숫자를 5로 나누었을 때, 나오는 결괏값은 5의 개수이다.

 

이제 예시를 큰 숫자로 들어보자 100!이다. 여기서 5는 20번 등장한다. 100 나누기 5.

5, 10, 15, 20,..., 100. 이제 5가 등장하는걸 확인해 보자.

5는 5*1

10은 5*2

.

.

.

25는 5 * 5            # 5의 배수이지만 5가 2번 등장했다. 이런 것들을 세어주기 위해 거듭제곱을 하는 것이다. 

.

.

.

50은 5 * 5 * 2

 

다시 코드를 되짚어보자. 다시 보니 왜 count를 계속해서 거듭제곱으로 나누어 나온 몫을 더해주는지 이해가 된다.

 

사실 수학공부를 게을리 한 내 입장에서는 여기까지 오는데 시간이 걸렸다. 코드를 뚫어져라 봐도 이해가 잘 되지 않아서 검색을 정말 많이 했다. 그래서 결국 이해하고 다시 짜보기도 했지만 이런 알고리즘을 써야 하는 순간이 와도 코드 2번을 쓰게 될 거 같다는 생각이 들었다. 그렇지만 늘 하고 싶은 것보다 하기 싫은 걸 해야 실력이 는다. 이번 기회에 제대로 익히고 다음에 써볼 기회가 생겼으면 좋겠다.