Python으로 PS를 할 때 최대 재귀 한도 깊이의 제한으로 인해 Recursion Error가 발생하는 것을 막기 위해 setrecursionlimit() 함수를 사용하곤 한다.
BOJ 11437번 LCA 문제 (https://www.acmicpc.net/problem/11437) 를 Python으로 풀던 중 제출한 코드가 Recursion Error가 났고, 평소와 같이 아래 코드를 추가하여 오류를 해결하고자 하였다.
sys.setrecursionlimit(10**6)위의 코드를 추가했음에도 Python3로 제출했을 때 시간 초과가 발생하였고,
일반적으로 재귀를 사용하는 경우 JIT 컴파일을 도입하여 자주 쓰이는 코드를 캐싱하는 기능을 가진 PyPy가 빠르기 때문에 PyPy3로도 제출해보았다.
Python3 vs PyPy3: https://ralp0217.tistory.com/entry/Python3-%EC%99%80-PyPy3-%EC%B0%A8%EC%9D%B4
하지만 이번에는 메모리 초과가 발생하였는데, 다양한 기술 블로그들에서 PyPy3에서는 setrecursionlimit() 함수가 작동하지 않는다는 정보를 말하고 있었다.
그래서 setrecursionlimit() 함수를 삭제하고 다시 코드를 제출해보았는데, 이번에는 또 Recursion Error가 발생하였다.
혹시 최대 깊이를 10**5로만 설정하면 어떨지 하여 바꿔보았는데, Recursion Error도 발생하지 않고, 메모리 초과도 발생하지 않으며 정답 처리가 되었다.
이를 통해 깨달은 점은 아래와 같다.
- PyPy3에서도 setrecursionlimit() 함수가 대략적으로 동작한다.
http://doc.pypy.org/en/latest/cpython_differences.html 을 읽어보면
"sys.setrecursionlimit(n) sets the limit only approximately, by setting the usable stack space to n * 768 bytes. On Linux, depending on the compiler settings, the default of 768KB is enough for about 1400 calls."
라는 문구가 있다.
- 다만 최대 깊이를 필요한 만큼만 설정해주어야 메모리 초과가 발생하지 않는다.
- 기술 블로그에 나와 있는 정보들을 너무 믿지 말고, 관련 공식 문서를 열람하는 것이 정확하다.
BOJ 커뮤니티에서도 똑같은 주제로 토론하는 사람들이 있는 것을 발견하였다. https://www.acmicpc.net/board/view/35748
Python으로 PS를 준비한다면, 이런 에매한 부분들을 정확히 파고들 필요가 있어 보인다..
