이진 힙(binary heap)과 이를 이용한 힙 정렬(heap sor… | [7급 서울시 알고리즘] 26년 1회차 기출문제 상세 페이지

1[7급 서울시 알고리즘] 26년 1회차
이진 힙(binary heap)과 이를 이용한 힙 정렬(heap sort)에 대한 설명으로 가장 옳은 것은? (단, nn은 힙에 저장된 원소의 개수이다.)
1
최소 힙에서 최댓값은 O(log⁡n)O(\log n) 시간에 찾을 수 있다.
2
삽입식 힙 생성 알고리즘은 입력 순서와 무관하게 Θ(nlog⁡n)\Theta(n\log n) 시간이 필요하다.
3
힙 정렬은 별도의 배열 없이 제자리(in-place)에서 수행 가능하지만, 안정(stable) 정렬은 아니다.
4
힙 정렬은 O(n)O(n) 시간에 수행 가능하다.
해설

힙 정렬은 제자리 정렬이지만 안정 정렬은 아니다.

힙 정렬은 배열 안에서 루트를 마지막 원소와 교환하고 힙을 재구성하므로 추가 배열이 필요 없지만, 멀리 떨어진 원소끼리 교환하기 때문에 같은 키의 상대 순서가 바뀔 수 있다.

  • 최소 힙의 최댓값: 리프 어디에나 있을 수 있어 리프 전체(약 절반의 원소)를 살펴야 하므로 O(n)O(n)이 든다.
  • 삽입식 힙 생성: 이미 힙 순서로 들어오는 입력이면 삽입마다 상향 이동이 없어 O(n)O(n)에 끝나므로 입력 순서와 무관하지 않다.
  • 힙 정렬의 시간: 비교 기반 정렬이라 Ω(nlog⁡n)\Omega(n\log n) 하한을 넘을 수 없으며 O(nlog⁡n)O(n\log n)이 든다.

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

이어서 풀어보기

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