5639번 - 이진 검색 트리
이진트리면 배열에 저장 가능하겠네?
왼쪽 자식 인덱스 = 부모 인덱스 * 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
뭔가 잘못되었다는게 슬슬 느껴지실겁니다
파이썬은 2^10000이 이정도라고 하네요
부끄럽게도 저 역시나 이렇게 풀었다가 이유를 모르고 계속 틀렸습니다
혹시나 해매시는 분들께 도움이 되셨으면 좋겠네요
댓글을 작성하려면 로그인해야 합니다.
thinker99 1년 전 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
뭔가 잘못되었다는게 슬슬 느껴지실겁니다
파이썬은 2^10000이 이정도라고 하네요
부끄럽게도 저 역시나 이렇게 풀었다가 이유를 모르고 계속 틀렸습니다
혹시나 해매시는 분들께 도움이 되셨으면 좋겠네요