2원 합병정렬에서 런(run)의 크기가 다를 경우, 런의 병합 순서에 … | [7급 국가직 자료구조론] 10년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 10년 1회차
2원 합병정렬에서 런(run)의 크기가 다를 경우, 런의 병합 순서에 따라 실행 속도의 차이가 발생한다. 초기 런의 수가 5개이며 각 런의 크기가 아래와 같을 때, 5개의 런을 하나로 병합하는 최소 시간은?
(단, 크기가 a, b인 두 개의 런을 병합하는 시간은 a + b라고 가정한다)
런 이름r1r2r3r4r5
크기24578
1
26
2
58
3
84
4
88
해설

최소 병합 시간은 58이다.

매번 가장 작은 두 런을 먼저 합치면(허프만 방식) 전체 병합 시간이 최소가 된다.
2+4=6, 5+6=11, 7+8=15, 11+15=262+4=6,\ 5+6=11,\ 7+8=15,\ 11+15=26
6+11+15+26=586+11+15+26=58

  • 26: 마지막 병합 한 번의 비용(전체 데이터 크기)일 뿐 중간 병합 비용이 빠졌다.
  • 84: 큰 런부터 합치는 순서(8+7=15, 15+4=19, 19+5=24, 24+2=268+7=15,\ 15+4=19,\ 19+5=24,\ 24+2=26)의 비용으로, 큰 런이 여러 번 다시 병합되어 최소가 아니다.
  • 88: 어떤 병합 순서로도 나오지 않는 값이다. 가장 불리한 순서도 85에 그친다.

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

이어서 풀어보기

[7급 국가직 자료구조론] 10년 1회차 20문항 이어서 보기문제·정답·해설을 한 페이지에서 이어서 볼 수 있어요7급 국가직 자료구조론 기출문제 암기장 전체 보기