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

안녕하세요 ㅎㅎ

1. 어떻게 저 로그식이 유도된건지 아이디어가 궁금합니다. 도무지 이해가 안됩니다ㅠ

음.. 간단하게 생각하시면 됩니다. 트리의 노드를 세어 볼까요?

n이 4일 때 7번.

n이 8일 때 15번 함수호출되는 것을 볼 수 있습니다.

자 여기서 저 트리의 높이는 얼마일까요? 트리의 높이는 4입니다. 가장 위에서부터 쭉 하나 둘.. 이렇게 세어보면 4인 것을 알 수 있습니다. 이 높이와 n과 연관을 시키면

높이 = log2N + 1임을 알 수 있습니다.

레벨별로 보면

1

2

4

8

이렇게 합쳐지죠? n이 8일 때 이런 레벨이 4개가 있죠?

이게

높이 = log2N + 1

인 것입니다.

이러한 것을 유도하는 것은 그냥 저렇게 함수호출을 노드로 나타내보면서 연관시키는 방법도 있구요. 2주차 때 저희가 트리를 배우는데 그걸 배우면 이 부분이 이해가 더 쉽게 느껴질 수 있으실 겁니다.

1. 영상에서 입력한 값을 나타내는 n과 등비수열의 공식에서 공비 r의 지수에 쓰인 n은 다른 n 맞죠..?? 전자는 입력한 값을, 후자는 덧셈식에서 항의 개수를 의미하는 것 맞나요?

네 전자는 입력한 값을, 후자는 덧셈식에서 항의 개수가 맞습니다.

또 질문 있으시면 언제든지 질문 부탁드립니다.

좋은 수강평과 별점 5점은 제가 큰 힘이 됩니다. :)

감사합니다.

강사 큰돌 올림.