한국어
메뉴

자료 구조와 알고리즘

병합 정렬에서 오름차순으로 정렬된 두 열 1, 4, 7, 9와 2, 3, 8, 10을, 맨 앞끼리 비교하여 작은 쪽을 출력하는 것을 반복하여 하나의 열로 합친다(병합한다). 한쪽 열이 비면 나머지는 비교하지 않고 그대로 출력한다. 비교 횟수는 몇 회인가?

  1. A4회
  2. B7회
  3. C8회
정답과 해설 보기

정답: B. 7회

1과 2, 4와 2, 4와 3, 4와 8, 7과 8, 9와 8, 9와 10을 비교하고, 여기서 첫 번째 열이 비므로 나머지 10은 비교하지 않고 출력합니다. 비교는 7회이며, 길이 m과 n인 열을 병합할 때의 최대 횟수 m + n − 1 = 7에 해당합니다. 병합은 정렬된 열을 앞에서부터 한 번씩 보기만 하므로 O(m + n)으로 끝나며, 이를 log₂ n단 반복하므로 병합 정렬 전체는 O(n log n)이 됩니다.

이 분야 연습하기 분야로 돌아가기

자료 구조와 알고리즘의 다른 문제

  1. 이진 힙을, 루트를 a[0]으로 하는 배열 a[0], a[1], a[2], …에 위쪽 단부터 차례로 왼쪽부터 채워 저장한다. a[4]의 자식과 부모로 올바른 것은?
  2. 부모의 값이 자식의 값 이상이 되는 최대 힙을, 루트를 a[0]으로 하는 배열로 나타내고 있다. 힙 50, 30, 40, 10, 20, 35에 45를 추가한다. 맨 끝에 놓은 뒤 부모보다 큰 동안은 부모와 교환하는 조작을 수행한 후의 배열은?
  3. 이진 탐색 트리를 중위 순회(왼쪽 서브트리, 그 노드, 오른쪽 서브트리 순으로 방문한다)로 따라갔을 때, 방문한 노드의 값은 어떻게 늘어서는가? 값은 모두 서로 다르다고 한다.
  4. 빈 이진 탐색 트리에 50, 30, 70, 20, 40, 60, 80의 순서로 값을 삽입했다. 이 트리를 후위 순회(왼쪽 서브트리, 오른쪽 서브트리, 그 노드 순으로 방문한다)로 따라갔을 때의 순서는?
  5. 빈 이진 탐색 트리에 1, 2, 3, …, 1000의 순서로 값을 삽입했다(균형을 잡는 조작은 하지 않는다). 이 트리에서 1000을 찾을 때, 루트부터 비교하기 시작하여 찾을 때까지 비교하는 노드의 수는?