글 읽기 - [파이썬] 메모리초과, 출력 초과 질문입니다.

kckc0608 3년 전 2

처음에는 리스트 슬라이싱으로 풀었다가 메모리 초과를 받았고, 질문글을 통해 인덱스를 넘겨주는 방법으로 풀라는 글을 보았습니다.

근데 인덱스를 넘겨주어도 여전히 메모리 초과가 발생하는데, 그 이유를 모르겠습니다.

정답풀이를 간단하게 보니, 인오더와 포스트오더의 시작, 끝지점을 각각 인자로 받아 푸는 풀이를 보고 참고하여 코딩해보았습니다.

그랬더니 메모리초과는 해결했지만 (왜 해결되었는지 이해가 안됩니다. 사용하는 변수의 개수는 차이가 없지 않나요..?) 출력초과가 발생합니다.

정답풀이와 제 코드의 차이점을 고민해보니

저는 커팅지점을 기준으로 -1, +1 하여 좌/우 를 나누었고

정답코드는 좌측 요소의 개수, 우측 요소의 개수를 계산하여 인자로 넘겨주는 차이가 있는데, 왜 여기에서 출력초과와 정답의 차이가 발생하는지 모르겠습니다. 도대체 어디서 이런 차이가 발생하는 건가요?
(정답코드를 제가 푼 방식대로 커팅지점 기준으로 -1,+1 하도록 조금 수정하니 출력초과가 나와서 이 부분이 차이점이라고 생각했습니다.)

''' 트리의 순회(메모리초과) '''
import sys
sys.setrecursionlimit(10**8)
def preorder(root,start,end,post_end):
    print(root, end = ' ')
    if start == end:
        return
    cut = pos[root]
    if cut-1 >= start:
        preorder(postorder[cut-1],start,cut-1,cut-1)
    if cut + 1 <= end:
        preorder(postorder[post_end-1],cut+1,end,post_end -1)

n = int(input())
inorder = list(map(int,input().split()))
pos = [x for x in range(n+1)]
for i in range(n):
    pos[inorder[i]] = i
postorder = list(map(int,input().split()))
preorder(postorder[-1],0,n-1,n-1)

''' 트리의 순회(출력 초과) '''
import sys
sys.setrecursionlimit(10**8)
def preorder(in_start,in_end,post_start,post_end):
    print(postorder[post_end], end = ' ')
    if in_start == in_end:
        return
    cut = pos[post_end]
    if cut-1 >= in_start:
        preorder(in_start,cut-1,post_start,cut-1) #좌/우를 나누는 커팅지접을 기준으로 왼쪽과 오른쪽 구분
    if cut + 1 <= in_end:
        preorder(cut+1,in_end,cut,post_end-1)

n = int(input())
inorder = list(map(int,input().split()))
pos = [x for x in range(n+1)]
for i in range(n):
    pos[inorder[i]] = i
postorder = list(map(int,input().split()))
preorder(0,n-1,0,n-1)

## 인터넷을 참고한 정답 풀이
import sys
sys.setrecursionlimit(10**9)
 
n = int(sys.stdin.readline())
inorder = list(map(int, sys.stdin.readline().split()))#중위순회
postorder = list(map(int, sys.stdin.readline().split()))#후위순회
in_location=[0 for _ in range(n+1)]#인자를 찾을때 한번에 찾기위해서
for i in range(n):
    in_location[inorder[i]]=i
 
 
def pre_order(in_l,in_r,post_l,post_r): #중위순회 범위 후위순회 범위
    if post_l <= post_r:
        parents=postorder[post_r]#후위순회에서 부모노드 찾기
 
        print(parents,end=" ")
        p_index=in_location[parents]
        l_count=p_index-in_l#왼쪽인자 갯수
        r_count=in_r-p_index#오른쪽인자 갯수
 
        pre_order(in_l , in_l+l_count-1 , post_l , post_l+l_count-1)#부모노드를 기준으로 왼쪽노드
        pre_order(in_r-r_count+1 , in_r , post_r-r_count , post_r-1)#부모노드 기준 오른쪽
 
pre_order(0,n-1,0,n-1)

kckc0608 3년 전 0

반례를 발견하였습니다.

12
8 4 9 2 10 5 11 1 12 6 3 7
8 9 4 10 11 5 2 12 6 7 3 1

kckc0608 3년 전 2

1. 출력초과의 이유

29행 cut = pos[post_end] 에서. pos 배열은 post order의 "특정 값"을 넣으면 "그 값의 인덱스" 를 알려주도록 설계했습니다.

그러나 리스트의 인덱스로 넣는 post_end 는 post_order 에서 값을 참조할 때 쓰이는 "인덱스" 입니다. 값을 넣어야 할 곳에 인덱스를 넣어서 꼬이기 시작하며 출력초과가 발생했습니다.

2. 메모리 초과의 이유

31 preorder(in_start,cut-1,post_start,cut-1)

33 preorder(cut+1,in_end,cut,post_end-1)

처음 함수가 호출 될 때는 in_end 값과 post_end 값이 같습니다.

따라서 계속 왼쪽 값을 찾아나갈 때는 in order 와 post order 에서 똑같이 cut-1을 해도 상관 없었습니다.

그러나 우측 값을 찾으러 한번 이동하면 in order는 끝값이 변하지 않지만, post order는 끝값이 줄어듭니다.

이 상태에서 좌측값을 찾으러 이동하면, in order 와 post order의 양 끝값이 서로 다른 상태에서 동일한 cut-1을 빼게되므로, 참조하는 post order값이 바뀌어

출력에 이상이 생기게 되고, 재귀 깊이가 무한대로 깊어지며 메모리 초과가 발생합니다.

따라서 좌측 요소의 개수, 우측 요소의 개수로 인덱스를 조절하여 해결해야 하는 것으로 스스로 이해했습니다 :)

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

문제

문제

출처

ICPC

[파이썬] 메모리초과, 출력 초과 질문입니다.

kckc0608 3년 전 2

kckc0608 3년 전 0

kckc0608 3년 전 2

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말