정답
\(①:\;child < n \land list[child] > list[child+1]\) \(③:\;makeHeap(list,\; i,\; 1)\) \(②:\;2\) \(④:\;40\)
출제 의도
최소 히프(min heap)를 배열로 구현할 때, 히프를 구성하는 과정과 히프 정렬 과정에서의 재구성 연산을 이해하고 있는지를 평가하는 문제이다. 또한 히프 구조에서 특정 키 값의 위치를 찾는 함수를 해석하여, 실제 실행 결과로 어떤 인덱스가 출력되는지 추적하는 능력을 묻는다.
풀이 과정
조건에서 히프는 완전이진트리 형태의 최소 히프이며, 배열 인덱스는 1번부터 사용한다. 함수 \(makeHeap(list,\; n,\; root)\) 는 인덱스 \(root\) 를 루트로 하는 부분트리를 최소 히프로 재구성하는, 이른바 down-heap(또는 heapify) 연산이다.
먼저 ①에 들어갈 부분을 본다. 루트에서 자식으로 내려가며 재구성할 때, 현재 노드의 왼쪽 자식 인덱스를 \(child = 2 \times root\) 로 잡는다. 두 자식 중 더 작은 값을 가진 노드를 선택해야 하므로, 오른쪽 자식이 존재하고(\(child < n\)) 그 값이 왼쪽 자식보다 더 작을 때만 \(child\) 를 오른쪽 자식으로 1 증가시켜야 한다.
따라서 ①에는
$$ child < n \land list[child] > list[child+1] $$
가 들어간다. 이렇게 하면 \(list[child]\) 는 항상 두 자식 중 더 작은 쪽이 된다.
heapSort 함수의 두 번째 for문은 히프 정렬의 본체이다. 각 반복에서
1. \(temp = list[1]\) 으로 히프 루트 값을 저장하고, 2. \(list[1]\) 과 마지막 히프 원소 \(list[i+1]\) 를 교환한 뒤, 3. 히프 크기를 \(i\) 로 줄여 다시 최소 히프로 재구성한다.
이때 재구성은 항상 루트(1번 인덱스)에서 시작하므로, ③에는
$$ makeHeap(list,\; i,\; 1) $$
이 들어간다.
이제 실제 배열 값의 변화를 추적한다. 초기 배열은
$$ list = [\, -, 10, 30, 20, 40, 1, 50, 70\,] \quad (1\sim7번 인덱스 사용) $$
첫 번째 for문에서 \(i = \lfloor n/2 \rfloor, \dots, 1\) 에 대해 makeHeap을 호출하면, 최소 히프가 만들어진다. 계산을 해 보면 히프 구성 후 배열은
$$ list = [\, -, 1, 10, 20, 40, 30, 50, 70\,] $$
이 된다. 따라서 ④에서 출력되는 값은
$$ list[4] = 40 $$
이므로 ④의 출력은 \(40\)이다.
이제 두 번째 for문으로 정렬을 진행한다. \(i = 6, 5, 4, \dots\) 에 대해 루트와 \(list[i+1]\) 를 교환하고, \(makeHeap(list, i, 1)\) 으로 다시 최소 히프를 만든다.
\(i = 6\) 일 때 루트 1과 \(list[7]=70\) 을 교환한 뒤 재구성하면
$$ list = [\, -, 10, 30, 20, 40, 70, 50, 1\,] $$
가 되고, \(temp = 1\) 이므로 \(temp == 20\) 이 아니어서 printNodeIndex는 호출되지 않는다.
\(i = 5\) 일 때 루트 10과 \(list[6]=50\) 을 교환하고 재구성하면
$$ list = [\, -, 20, 30, 50, 40, 70, 10, 1\,] $$
가 되고, \(temp = 10\) 이므로 역시 출력이 없다.
\(i = 4\) 일 때 루트 20과 \(list[5]=70\) 을 교환하고 재구성하면
$$ list = [\, -, 30, 40, 50, 70, 20, 10, 1\,] $$
이 된다. 이때 \(temp = 20\) 이므로 조건 \(temp == 20\) 이 참이 되어,
$$ printNodeIndex(list,\; 40) $$
이 호출된다.
printNodeIndex 함수는 \(k = 1\) 부터 7까지 검사하여, \(list[k] = 40\) 인 인덱스 \(k\) 를 출력한다. 위 배열에서 값 40은 인덱스 2에 있으므로,
$$ k = 2 $$
만 출력된다. 따라서 ②의 출력 결과는 \(2\)이다.
정리하면, 프로그램 전체 실행 시 출력 순서는 먼저 ④에서 \(40\), 그리고 ②에서 \(2\) 가 차례로 출력된다.
<풀이가 부정확할 수 있으니 반드시 교차검증 확인 바랍니다.>