2원 합병정렬에서 런(run)의 크기가 다를 경우, 런의 병합 순서에 … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지
1[7급 국가직 자료구조론] 10년 1회차
2원 합병정렬에서 런(run)의 크기가 다를 경우, 런의 병합 순서에 따라 실행 속도의 차이가 발생한다. 초기 런의 수가 5개이며 각 런의 크기가 아래와 같을 때, 5개의 런을 하나로 병합하는 최소 시간은?
(단, 크기가 a, b인 두 개의 런을 병합하는 시간은 a + b라고 가정한다)
| 런 이름 | r1 | r2 | r3 | r4 | r5 |
|---|---|---|---|---|---|
| 크기 | 2 | 4 | 5 | 7 | 8 |
1
26
2
58
3
84
4
88
해설
최소 병합 시간은 58이다.
매번 가장 작은 두 런을 먼저 합치면(허프만 방식) 전체 병합 시간이 최소가 된다.
- 26: 마지막 병합 한 번의 비용(전체 데이터 크기)일 뿐 중간 병합 비용이 빠졌다.
- 84: 큰 런부터 합치는 순서()의 비용으로, 큰 런이 여러 번 다시 병합되어 최소가 아니다.
- 88: 어떤 병합 순서로도 나오지 않는 값이다. 가장 불리한 순서도 85에 그친다.
오류나 개정된 내용이 보이면 알려주세요