본문바로가기
함께 풀고 싶은 문제
창의력을 기를 수 있는 수학 문제 또는 퍼즐을 내는 곳입니다.
[창의 퍼즐] [i'm possible 폴리매스]LCA문제 ( 나도 아직 못푼 문제)
로보카폴리 2020.02.13 07:13 조회 678

어떠한 무한히 이어지는 완벽한 이분 트리가 주어진다. 트리의 각 정점은 1번부터 계속 번호가 매겨져 있으며, 루트는 1번이다.

                                                1

                                         2       /     3

                                   4    ,   5     /  6    ,  7

                               8   , 9 / 10, 11/   12, 13/  14 , 15

                                               .

                                               .

                                               .

 두 노드의 쌍 (a,b)(1 ≤ (a,b) ≤ 10,000)개가 주어졌을 때, 두 노드의 가장 가까운 공통 조상 을 f(a,b)로 정의 한다.(예를 들어 5와 8의 공통조상(LCA)는 2이다.)

(1) f(4096,4095)를 구하시오

(2) f(a,b)=1이 되는 a,b를 구하시오

(3) f(a,b)를 a,b에 대한 식으로 일반화 하시오

이 문제 어떠셨나요?

글쎄요

0

어려워요

0

  • 폴리매스 문제는 과학기술진흥기금 및 복권기금의 재원으로 운영되고, 과학기술정보통신부와 한국과학창의재단의 지원을 받아 수행된 성과물로 우리나라의 과학기술 발전과 사회적 가치 증진에 기여하고 있습니다.

  • ☎문의 02-6749-3911