thinker99   1년 전

이진트리면 배열에 저장 가능하겠네? 

왼쪽 자식 인덱스 = 부모 인덱스 * 2, 오른쪽 자식 인덱스 = 부모 인덱스 * 2 + 1, 와 짱편하네??

문제에서 노드 갯수가 10000개까지라 그랬지? int tree[10001];

어? 분명 내 생각은 틀린게 없는데 왜 OutOfBounds가 뜨지???


입력이 "1, 2, ..."와 같이 기형적으로 계속 오른자식만 쭉쭉 뻗어나가는 경우를 생각해볼 수 있겠습니다

이를 배열에 저장해볼까요?

{1} 저장하는데 트리의 높이는 0, 노드의 갯수는 1

배열의 칸 수는 2^1 - 1 = 1

{1, 2} 저장하는데 트리의 높이는 1, 노드의 개수는 2

배열의 칸 수는 2^2 - 1 = 3

{1, 2, 3} 저장하는데 트리의 높이는 2, 노드의 갯수는 3

배열의 칸 수는 2^3 - 1 = 7

....

{1, 2, 3, ..., 39, 40} 저장하는데 트리의 높이는 39, 노드의 갯수는 40

배열의 칸 수는 2^40 - 1 = 1099511627776 - 1개

int형 배열이라 하면 필요한 메모리는 대략 4TB

뭔가 잘못되었다는게 슬슬 느껴지실겁니다

preview

파이썬은 2^10000이 이정도라고 하네요

preview

부끄럽게도 저 역시나 이렇게 풀었다가 이유를 모르고 계속 틀렸습니다

혹시나 해매시는 분들께 도움이 되셨으면 좋겠네요

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