https://www.acmicpc.net/problem/5639
재귀를 활용한 후위순회를 하는 문제이다.

import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline

bst = []

while True:
    try:
        n = int(input())
        # sys.stdin.readline 종료 문자 방지
        if n=="":
            break
        bst.append(n)
    except:
        break

def post_order(start,end):
    # 종료 조건
    if start>end:
        return
    
    root = bst[start]
    idx = start+1

    # 루트 노드보다 큰 오른쪽 자식노드 찾기
    while idx <= end:
        if root < bst[idx]:
            break
        idx +=1
    # idx-1는 오른쪽 자식노드보다 큰 값
    post_order(start+1, idx-1)
    post_order(idx, end)
    print(root)

post_order(0, len(bst)-1)

pypy vs python

PyPy3로 실행하니 메모리 초과가 발생했다.
아무래도 pypy가 python보다 메모리를 더 많이 쓰기 때문인 것으로 보인다.

왜 pypy가 메모리를 더 사용할까?

PyPy는 JIT 컴파일을 하기 때문이다.
JIT(Just-In-Time) 컴파일은 빌드가 아니라 런타임에 반복적으로 사용하는 코드를
컴파일하여 기계어로 변환해 저장하고 이 기계어는 메모리에 적재됩니다.
이때 어떤 코드가 반복적으로 쓰이는가?를 분석하기 위해 추가적인 메모리가 소모되어
최적화 과정에서 추가적인 리소스를 사용합니다.