9. Routing 연습문제

문제1.

답.

1) 다익스트라 알고리즘

2) 벨만 포드 알고리즘

​

---

 

문제2.

답.

먼저 N 레벨 이진트리의 특징을 알아야 한다.

1. N 레벨 이진트리의 N 레벨에 있는 노드 수는 2^(N-1) 개 이다.

ex. 4 레벨 이진트리의 4레벨에 있는 노드의 개수는 2^(4-1) = 8 개이다.

​

2. N 레벨 이진트리의 N 레벨을 제외한 모든 노드의 수는 2^(N-1) - 1 개 이다.

ex. 4 레벨 이진트리의 1~N-1레벨까지의 모든 노드의 수는 2^(4-1) -1 = 7 개이다.

​

3. 루트에서 N 레벨 까지 가는데 거쳐가는 경로는 N-1이다.

ex. 4레벨 이진트리에서 4레벨 노드까지 가는데 거쳐가는 가지(홉 수)는 4-1 = 3가지이다.

​

그럼 N레벨에 있는 노드를 기준으로 보자.

N 레벨에 있는 노드의 수는 2의 n-1승 개이고, 나머지 모든 노드 수의 합은 그것보다 1개 적다. ( 1,2번 특징 )

n이 무한히 크다고 문제에서 가정했으므로, (N레벨에 있는 노드 수 ) = (나머지 노드 수 ) 라고 볼 수 있다.

( N이 무한히 크면 1개차이는 무시할 수 있으므로 )

따라서 N레벨에 있는 노드가 선택될 확률은 1/2 이다. N레벨 까지가는 데 거치는 홉 수는 N-1 개이다.

정리하면 N레벨에 있는 노드가 선택되서 그곳까지 가는 홉수 = (1/2)*(N-1) 이다.

​

N-1레벨에 있는 노드가 선택될 확률은 다시 절반 이므로 (1/2)^2 이고 홉수는 (N-2) 가 된다.

이를 루트노드까지 전부 더하면

(1/2)*(N-1) + (1/2)^2*(N-2) ......이다. 여기서 N은 N끼리 묶고, 상수는 상수끼리 묶어서 문제의 공식을 적용하면 답은 N-2가 된다.

​

이해를 돕기 위해 아래에 풀이과정을 첨부했다.

​