42. [세그먼트 트리 실전 문제] 구간 합 구하기3 (백준 20... - 인프런

안녕하세요.

백준 2042 세그먼트 문제 답 코드 중에 이해안되는 부분이 있어서 질문 드립니다.

-----------------------------------------------------

int treeHeight = 0;

int length = n;

while (length != 0)

{

length /= 2;

treeHeight++;

}

int treeSize = int(pow(2, treeHeight + 1));

int leftNodeStartIdx = treeSize / 2;

-----------------------------------------------------

위의 코드가 잘 이해가 안됩니다

treeSize가 16이 나오기 위해서는 5, 6, 7, 8이 해당됩니다

근데 위의 코드로 결과를 구하게 된다면 5, 6, 7만 해당하고 8이 포함이 되지 않고 더 많은 배열이 선언되는 것 같습니다.

혹시 모자란 것보단 과한 건 결과값에 미치는 영향이 없기 때문에 위와 같은 코드로 구성했는지 궁금합니다.

안녕하세요, 인프런 AI 인턴입니다.
박빈나(shine)님, 질문 주신 부분에 대해 설명드리겠습니다.

세그먼트 트리의 초기화 과정에서 treeHeight와 treeSize를 결정하는 부분은 주어진 수의 개수(n)를 기반으로 트리의 높이를 계산하고 트리 배열의 크기를 결정하는 중요한 과정입니다.

treeHeight는 트리의 높이를 결정하는 변수로, length를 2로 나누면서 높이를 증가시킵니다. 이 과정은 n을 이진 트리의 노드 수로 맞추기 위해 필요한 트리의 깊이를 계산합니다.
treeSize는 실제 배열의 크기를 결정하는데 사용되며, (2 ^ (treeHeight + 1))으로 계산됩니다. 이 크기는 트리의 루트에서 가장 아래 레벨까지의 완전 이진 트리를 수용하기 위한 것으로, 실제로 필요한 것보다 더 큰 공간을 사용할 수 있습니다. 이렇게 과잉으로 잡아도 성능 면에서는 큰 문제가 되지 않으며, 버그를 피할 수 있는 안정된 방법이기도 합니다.

이는 세그먼트 트리의 경우, 이진 트리의 노드 수가 “완전 이진 트리”의 형태를 유지해야 하기 때문에 배열의 크기를 최소 크기로 하드코딩하기보다는 어느 정도 여유를 두는 것입니다. 그래서 실제로 필요한 수보다 큰 treeSize를 사용할 수 있습니다.

추가적인 설명이나 실전 예제를 보시길 원하신다면, 백준 문제 해설이나 별도의 구현 예시 블로그에서 관련 정보를 찾아보실 수 있습니다. 도움이 되셨길 바랍니다!

인프런 커뮤니티 질문&답변