각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 … | [7급 국가직 자료구조론] 08년 1회차 기출문제 상세 페이지

1[7급 국가직 자료구조론] 08년 1회차
각각 1,000 개의 데이터로 이루어진 데이터 세트 ‘A’와 ‘B’에 대해 ‘갑’과 ‘을’의 두 가지 정렬 기법으로 정렬을 수행했을 때 다음과 같은 시간이 소요되었다.
정렬 기법
데이터 세트
갑을
A0.21초0.40초
B6.71초0.39초
‘갑’과 ‘을’이 퀵 정렬(Quick Sort), 합병 정렬(Merge Sort), 힙 정렬(Heap Sort) 중의 하나라면, 바르게 나열된 것은?
갑  을
1
퀵 정렬  합병 정렬
2
힙 정렬  퀵 정렬
3
합병 정렬  퀵 정렬
4
합병 정렬  힙 정렬
해설

갑은 퀵 정렬, 을은 합병 정렬이다.

갑은 데이터 세트 B에서 시간이 30배 이상 늘었다. 데이터 분포(이미 정렬된 경우 등)에 따라 최악 O(n2)O(n^2)로 떨어지는 기법은 퀵 정렬뿐이다.

을은 두 세트에서 시간이 거의 같으므로 분포와 무관하게 O(nlog⁡n)O(n\log n)인 기법이며, 갑이 퀵 정렬인 조합은 을이 합병 정렬인 경우뿐이다.

  • 힙 정렬과 퀵 정렬: 힙 정렬은 입력 분포와 무관하게 O(nlog⁡n)O(n\log n)이라 갑처럼 급격히 느려지지 않는다.
  • 합병 정렬과 퀵 정렬: 합병 정렬도 최악이 O(nlog⁡n)O(n\log n)이라 갑의 큰 편차를 설명하지 못한다.
  • 합병 정렬과 힙 정렬: 둘 다 분포에 둔감해 갑의 큰 편차가 나올 수 없다.

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

이어서 풀어보기

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