해설 보기
정답3가지 (3^(3-2) = 3)
핵심 개념
완전 그래프의 신장 트리 개수 (케일리 공식)
신장 트리(spanning tree)는 그래프의 모든 정점을 포함하면서 사이클이 없는 연결 부분 그래프로, 정점이 n개면 간선은 항상 n-1개입니다. n개의 정점을 가진 무방향 완전 그래프 Kn의 서로 다른 신장 트리 개수는 케일리(Cayley) 공식에 따라 n^(n-2)개입니다. 정점이 3개인 완전 그래프 K3은 세 정점을 모두 이은 삼각형이므로 간선이 3개이고, 신장 트리는 간선 2개짜리 트리입니다. 즉 세 간선 중 하나를 제외하는 경우의 수와 같아 3가지가 되며, 케일리 공식으로도 3^(3-2)=3으로 일치합니다.
선지별 해설
①1가지는 트리 자체가 유일할 때의 값입니다. K3은 간선이 3개이고 그중 어느 하나를 빼도 서로 다른 신장 트리가 되므로 1가지일 수 없습니다.
②2가지는 정점 3개짜리 경로 그래프처럼 간선이 2개뿐인 그래프에서 나올 법한 수치이며, 완전 그래프 K3에는 해당하지 않습니다.
③케일리 공식 n^(n-2)에 n=3을 넣으면 3^1=3입니다. 실제로 삼각형에서 간선 하나씩을 제외한 세 가지 형태의 신장 트리가 만들어지므로 정답입니다.
④4가지는 K3의 간선 수(3개)보다 많은 값으로, 간선 하나를 제외하는 경우의 수가 3가지뿐인 이상 나올 수 없는 개수입니다.
해설 보기
정답4, 2, 5, 1, 6, 3, 7
핵심 개념
이진 트리의 중위 순회(inorder traversal)
중위 순회는 '왼쪽 서브트리 → 루트 → 오른쪽 서브트리' 순서로 노드를 방문하는 방법입니다. 재귀적으로 각 서브트리에도 같은 규칙을 적용하므로, 루트는 항상 왼쪽 서브트리의 모든 노드 뒤, 오른쪽 서브트리의 모든 노드 앞에 나옵니다. 주어진 트리는 루트 1, 왼쪽 자식 2(자식 4, 5), 오른쪽 자식 3(자식 6, 7)인 완전 이진 트리입니다. 왼쪽 서브트리를 중위로 돌면 4, 2, 5이고 그다음 루트 1, 오른쪽 서브트리를 중위로 돌면 6, 3, 7이 됩니다. 따라서 최종 결과는 4, 2, 5, 1, 6, 3, 7입니다. 참고로 전위는 1,2,4,5,3,6,7, 후위는 4,5,2,6,7,3,1입니다.