<보기>와 같이 입력키와 각각의 검색확률이 주어질 때, 최적… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
<보기>와 같이 입력키와 각각의 검색확률이 주어질 때, 최적의 이진 검색 트리(optimal binary search tree)로 가장 옳은 것은? (단, 최상단 노드가 루트 노드이다.)
<보기>
입력키ABCD
검색확률0.30.40.10.2
1
2
3
4
해설

최적 이진 검색 트리는 루트 B, 왼쪽 자식 A, 오른쪽 자식 D, D의 왼쪽 자식 C인 트리이다.

평균 비교 횟수는 각 키의 (깊이×검색확률) 합이며, 이 트리는 1(0.4)+2(0.3)+2(0.2)+3(0.1)=1.71(0.4)+2(0.3)+2(0.2)+3(0.1)=1.7로 가능한 트리 중 최소이다. 확률이 큰 B·A를 위에, 가장 작은 C를 가장 아래에 둔 결과이다.

  • 루트 C, B·D가 자식이고 A가 B 아래인 트리: 0.1+2(0.4)+2(0.2)+3(0.3)=2.20.1+2(0.4)+2(0.2)+3(0.3)=2.2
  • 루트 B, A·C가 자식이고 D가 C 아래인 트리: 0.4+2(0.3)+2(0.1)+3(0.2)=1.80.4+2(0.3)+2(0.1)+3(0.2)=1.8로, 확률이 더 큰 D가 더 깊어 손해이다.
  • 루트 C, A·D가 자식이고 B가 A 아래인 트리: 0.1+2(0.3)+2(0.2)+3(0.4)=2.30.1+2(0.3)+2(0.2)+3(0.4)=2.3으로 확률이 가장 큰 B가 가장 깊다.

오류나 개정된 내용이 보이면 알려주세요

이어서 풀어보기

[7급 서울시 알고리즘] 26년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 서울시 알고리즘 기출문제 암기장 전체 보기