글 읽기 - [Python3][스포주의] 파이참에서 MemoryError

kano2812 3년 전 0

"MemoryError: stack overflow" 에 대해 질문드립니다.

문제는 index를 활용해서 root의 왼쪽과 오른쪽을 나눈 후, 재귀적으로 풀었습니다.

그런데 궁금한 점은,

제가 ide로 파이참을 사용하는데 한쪽으로 10만개 연속적으로 이어진 트리를 인풋에 넣으면

[Previous line repeated 6425 more times]
File "", line 9, in find_root
MemoryError: stack overflow

란 설명과 함께 실행이 멈춥니다.

그런데 백준에다 코드를 넣으면 맞았다고 하는데 그 이유가 궁금합니다.

파이참에서 돌린 소스는 첨부하였습니다.

import sys
sys.setrecursionlimit(200000)


def find_root(i_start, i_end, p_start, p_end):
    if i_start > i_end or p_start > p_end:
        return
    root = postorder[p_end]
    print(root, end=" ")
    if p_end - p_start == 0:
        return
    dif = dic[root] - i_start
    find_root(i_start, dic[root]-1, p_start, p_start+dif-1)   # left
    find_root(dic[root]+1, i_end, p_start+dif, p_end-1)       # right


## 한쪽으로만 이어진 트리
n = 100000
inorder = list(i for i in range(n))  # 중위순회
postorder = list(reversed(inorder))  # 후위순회
dic = [0] * (n+1)
for i in range(0, len(inorder)):
    dic[inorder[i]] = i

# first1 p_start, p_end = 0, n-1 ; [0, n-1]: closed interval
find_root(0, n-1, 0, n-1)


## 실제 백준에 넣은 input 데이터
# n = int(input())
# inorder = list(map(int, sys.stdin.readline().split()))
# dic = [0] * (n+1)
# for i in range(0, len(inorder)):
#     dic[inorder[i]] = i
# postorder = list(map(int, sys.stdin.readline().split()))
#
# # first1 p_start, p_end = 0, n-1 ; [0, n-1]: closed interval
# find_root(0, n-1, 0, n-1)

kano2812 3년 전 1

여기저기 검색하고, 시도해보면서 알아본 결과는,

파이참 같은 ide는 기본적으로 재귀 스택의 limit을 풀어도 메모리에는 제한이 걸려있습니다.

sys.setrecursionlimit(100000)을 하더라도 대략 9800개의 제귀 스택이 생기면 메모리 초과로 memory error가 뜹니다.

그래서 우분투에서 같은 코드를 돌려보았더니 대략 50000개의 재귀 스텍까지는 error가 발생하지 않았습니다.

(50000 이상에서는 제 컴퓨터가 렘이 8gb가 단순히 렘 메모리가 부족해서라고 생각합니다.)

그래서 백준에서는 소스 코드를 돌렸을 때 문제가 없었다고 생각합니다.

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python3][스포주의] 파이참에서 MemoryError

kano2812 3년 전 0

kano2812 3년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말