98shcho   2년 전

첫 번째 방식 : 실제로 클래스로 트리를 만들어 전회순회한 결과를 바탕으로 실제로 트리를 만들고 후위순회하여 출력

두 번째 방식 : 인터넷에 검색해 나오는 방식. 전위순회한 결과가 루트노드 + 루트보다 작은 노드들(왼쪽 서브트리) + 루트보다 큰 노드들(오른쪽 서브트리)임을 이용해 왼쪽 서브트리 먼저 출력, 오른쪽 서브트리 그 후에 출력, 그리고 루트를 출력하는 것을 재귀적으로 하는 것.

첫 번째 방식에서 트리를 생성할 때 새 노드를 삽입할 때 최악의 경우 O(n)이 걸리므로 전체적으로 보면 O(n^2)가 걸리는데 n이 최대 10,000이니까 시간초과가 충분히 날 수 있다고 생각해요. 

근데 두 번째 방식에서도 예를 들어 전위순회한 결과가 10 9 8 7 6 5 4 3 2 1 이렇게 주어지면 주어진 구간(left부터 right까지의)에서 루트보다 큰 노드가 등장하는 위치를 찾으려면 무조건 주어진 구간의 끝까지 순회해야 하잖아요? 그렇다면 이 역시도 시간복잡도가 O(n^2)정도가 걸릴 것이라고 생각하는데 왜 이건 통과인지가 넘 궁금합니다 검색을 1시간해도 안나오네요..


djm03178   2년 전

시간 복잡도는 점근적인 효율성을 보여줄 뿐입니다. 단순히 통과/시간 초과로만 나누지 말고, 통과된 코드가 얼마나 시간이 걸렸는지 확인해보세요. 이 문제의 파이썬의 제한은 5초인데, 통과된 코드도 3.6초나 걸렸습니다. 즉, 같은 시간 복잡도라도 세부 단계의 효율성이 1.5배만 안 좋아도 시간이 초과될 수 있다는 뜻입니다. 객체라는 건 그 자체로 상당히 무거운 녀석입니다. 이것들을 전부 노드 하나당 하나의 객체를 할당하고 서로 엮어서 실제로 트리로 구현하는 건 대충 보기에도 매우 무거워 보입니다.

98shcho   2년 전

@djm03178

답변 감사합니다:) 공부가 더 필요함을 느끼네요..

해주신 답변은 객체를 왔다가며 하며 순회하는 것보다 배열에서 조작하는 것이 더 가볍다는 말씀으로 이해했는데 맞을까요?

djm03178   2년 전

네, 배열이 훨씬 가볍습니다.

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