2021년 2회 정보처리기사 기출문제 21번

21. 힙 정렬(Heap Sort)에 대한 설명으로 틀린것은?

① 정렬할 입력 레코드들로 힙을 구성하고 가장 큰 키 값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법이다.

② 평균 수행 시간은 O(nlog2n)이다.

③ 완전 이진트리(complete binary tree)로 입력자료의 레코드를 구성한다.

❹ 최악의 수행 시간은 O(2n4)이다.

 

 

문제 분석: "힙 정렬(Heap Sort)에 대한 설명으로 틀린 것은?"이라는 문제입니다. 힙 정렬은 **완전 이진 트리(Complete Binary Tree)**를 이용한 정렬 알고리즘입니다. 이 문제는 힙 정렬에 대한 여러 가지 설명 중에서 틀린 것을 찾는 문제입니다.

 

 

**힙 정렬(Heap Sort)**의 기본 동작:

1. 힙 구조: 힙은 이진 트리 구조로, 부모 노드가 자식 노드보다 크거나 작은 값을 가지는 힙 속성을 따릅니다. 힙은 크게 최대 힙과 최소 힙으로 구분됩니다.
   • 최대 힙에서는 부모 노드가 자식 노드보다 크며, 최소 힙에서는 부모 노드가 자식 노드보다 작습니다.
2. 정렬 과정:
   • 힙을 구성한 후, 루트 노드(가장 큰 값 또는 가장 작은 값)를 배열의 끝으로 옮깁니다.
   • 힙의 크기를 줄이고, 루트 노드의 값을 교체한 후 힙의 성질을 다시 만족시키기 위해 재구성(Heapify)을 합니다. 이 과정을 반복하여 정렬을 수행합니다.

각 선택지 분석:

1. ① 정렬할 입력 레코드들로 힙을 구성하고 가장 큰 키 값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법이다:
   • 힙 정렬의 정확한 설명입니다. 힙을 구성하고, 루트 노드(가장 큰 값)를 제거하여 결과 배열에 넣고, 그 후 힙을 재구성하여 다시 반복하는 방식입니다.
   • 따라서, 이 선택지는 맞습니다.
2. ② 평균 수행 시간은 O(nlog2n)이다:
   • 힙 정렬의 평균 수행 시간은 O(nlogn)입니다. 힙을 구성하는 데 O(n), 힙을 재구성하는 데 O(logn)의 시간이 걸리며, 전체적으로 O(nlogn)의 시간 복잡도를 가집니다.
   • 따라서, 이 선택지도 맞습니다.
3. ③ 완전 이진트리(complete binary tree)로 입력자료의 레코드를 구성한다:
   • 힙은 완전 이진 트리(Complete Binary Tree) 구조를 사용하여 구현됩니다. 이진 트리의 각 노드는 부모-자식 관계를 만족하며, 힙의 특징을 따릅니다.
   • 따라서, 이 선택지도 맞습니다.
4. ❹ 최악의 수행 시간은 O(2n4)이다:
   • 힙 정렬의 최악의 수행 시간은 **O(nlogn)**입니다. O(2n4)와 같은 복잡도는 존재하지 않습니다. "O(2n4)"는 잘못된 표기법으로, 최악의 경우 시간 복잡도는 O(nlogn)으로 일정합니다.
   • 따라서, 이 선택지는 틀립니다.

결론: 힙 정렬에 대한 설명으로 틀린 것은 ❹ 최악의 수행 시간은 O(2n4)이다입니다. 최악의 수행 시간은 O(nlogn)이어야 합니다.