해설 보기
정답7은 여섯 번째로 삽입되어 인덱스 6에 자리 잡고, 이후 20이 삽입되어도 위치가 바뀌지 않으므로 정답은 6입니다.
핵심 개념
배열로 구현한 최대 힙의 삽입과 상향 조정(up-heap)
최대 힙은 부모의 키가 자식보다 항상 크거나 같은 완전 이진 트리입니다. 배열로 구현하면 인덱스 1을 루트로 두고, 인덱스 i의 왼쪽 자식은 2i, 오른쪽 자식은 2i+1, 부모는 i/2가 됩니다. 새 키는 항상 배열의 마지막 빈자리에 넣은 뒤 부모와 비교하여 부모보다 크면 교환하는 상향 조정을 반복합니다. 삽입 순서를 하나씩 따라가며 배열 상태를 갱신하는 것이 문제 해결의 핵심입니다.
선지별 해설
①삽입을 모두 마친 배열은 [20, 10, 15, 8, 9, 7, 12]이며 인덱스 4에는 8이 저장되어 있습니다. 8은 네 번째로 삽입될 때 부모(인덱스 2의 10)보다 작아 교환 없이 그 자리에 그대로 남았습니다.
②인덱스 5에는 다섯 번째로 삽입된 9가 있습니다. 9 역시 부모인 인덱스 2의 10보다 작아 상향 조정이 일어나지 않았으므로 7의 위치가 아닙니다.
③15, 10, 12, 8, 9까지는 교환 없이 [15, 10, 12, 8, 9]가 됩니다. 여섯 번째 7은 인덱스 6에 들어가고 부모인 인덱스 3의 12보다 작아 그대로 머뭅니다. 마지막 20은 인덱스 7에 들어간 뒤 12, 15와 차례로 교환되어 루트로 올라가므로 7의 인덱스 6은 변하지 않습니다.
④인덱스 7에는 20이 올라가면서 밀려 내려온 12가 저장됩니다. 20은 인덱스 7 → 3 → 1로 두 번 상향 이동했고, 그 과정에서 12가 인덱스 7로 내려왔습니다.
해설 보기
정답중위 순회 결과는 키의 오름차순이므로 0 1 2 3 4 5 6 7 8 9입니다.
핵심 개념
이진 탐색 트리의 중위 순회는 항상 오름차순 정렬
이진 탐색 트리는 모든 노드에 대해 왼쪽 서브트리의 키가 자신보다 작고 오른쪽 서브트리의 키가 자신보다 크다는 성질을 유지합니다. 중위 순회는 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 순으로 방문하므로, 이 성질에 의해 방문 순서가 반드시 키의 오름차순이 됩니다. 따라서 삽입 순서가 어떠하든, 중복 없는 키 집합이 같다면 중위 순회 결과는 언제나 동일한 정렬 결과가 됩니다.
선지별 해설