방송대 이산수학 11강: 이진 탐색 트리와 최소 신장 트리

트리 문제는 그림이 나무처럼 보이는지를 묻는 데서 끝나지 않습니다. 연결성과 변의 수로 트리를 판정하고, 이진 트리의 높이를 계산하며, 키의 비교 경로를 추적하고, 가중 그래프에서 최소 비용의 연결을 골라야 합니다. 이 글은 이 네 가지 대표 문제를 직접 풀 수 있는 기준과 검산법을 구성합니다.

문제의 동사를 읽으면 사용할 도구가 결정된다

같은 트리 그림을 보더라도 질문에 따라 확인할 정보가 달라집니다. 먼저 문제가 무엇을 요구하는지 분류하면 정의와 공식을 잘못 선택하는 일을 줄일 수 있습니다.

문제의 요구	먼저 확인할 것	핵심 도구	마지막 검산
트리인지 판정	연결 여부와 사이클	`\|E\|=\|V\|−1`	연결 조건을 빠뜨리지 않았는가
노드 수·높이 계산	루트의 레벨이 0인지	`2^h+1−1`, `⌊log₂n⌋`	완전·포화 조건에 맞는가
키 구성·검색	왼쪽·오른쪽 서브트리의 대소 관계	비교 후 한쪽 서브트리 선택	루트부터 비교 경로를 기록했는가
최소 비용 연결	모든 꼭지점 포함, 사이클 금지	Kruskal 또는 Prim 알고리즘	변이 `n−1`개이고 총가중치가 최소인가

풀이 나침반: ‘판정’은 연결과 변의 수, ‘용량’은 레벨별 최대 노드 수, ‘검색’은 비교 방향, ‘최소 비용’은 사이클 없는 변 선택을 중심으로 풉니다.

트리 판정은 연결과 n−1개의 변을 함께 확인한다

트리(tree)는 사이클이 없는 단순 연결 그래프입니다. 꼭지점 하나만 있는 트리는 자명 트리(trivial tree), 꼭지점이 하나도 없는 경우는 공트리(empty tree), 한 개 이상의 트리로 이루어진 그래프는 숲(forest)이라고 합니다.

꼭지점이 n개인 트리의 변은 정확히 n−1개입니다. 역으로 n개의 꼭지점을 가진 연결 그래프에 변이 n−1개라면 그 그래프는 트리입니다. 연결된 상태에서 변 하나를 더하면 사이클이 생기고, 트리에서 변 하나를 빼면 두 부분으로 끊어집니다.

예를 들어 꼭지점 8개와 변 7개가 있어도 두 연결성분으로 나뉘어 있다면 트리가 아닙니다. |E|=|V|−1이라는 숫자만 맞춘 풀이가 실패하는 이유는 정리의 전제인 연결성을 확인하지 않았기 때문입니다.

양방향 검산: 트리라고 판단했다면 사이클이 없어야 하고, 변 하나를 제거했을 때 연결이 끊어져야 합니다. 반대로 연결 그래프에서 변이 n−1개임을 확인하면 사이클 없음까지 따로 전부 찾아다닐 필요가 없습니다.

루트를 정하면 가족 관계와 높이가 생긴다

루트 트리(rooted tree)는 특별한 노드 하나를 루트로 정한 트리입니다. 루트를 제외한 노드들은 서로 분리된 서브트리들에 속하고, 각 서브트리 역시 같은 방식으로 루트 트리가 됩니다. 루트를 정하면 방향 없는 연결에 위아래 관계가 생깁니다.

학습용 예로 루트 A의 자식이 B, C, D이고, B의 자식이 E, F, G이며, D의 자식 H, H의 자식이 I, J, K라고 하겠습니다.

용어	이 예에서의 값	판단 기준
부모·자식	D는 H의 부모, H는 D의 자식	루트에서 한 단계 아래로 직접 연결
형제	B, C, D	같은 부모를 공유
노드의 차수	`deg(B)=3`	그 노드의 자식 수
트리의 차수	3	모든 노드 차수의 최댓값
리프 노드	E, F, G, C, I, J, K	자식이 없는 단말 노드
내부 노드	A, B, D, H	한 개 이상의 자식을 가짐
레벨·높이	`level(H)=2`, 높이 3	루트에서 노드까지의 경로 길이와 그 최댓값
무게	7	리프 노드의 개수

그래프에서의 꼭지점 차수는 발생한 변의 수였지만, 루트 트리에서 강의가 정의한 노드 차수는 자식의 수입니다. 루트를 제외한 노드는 부모로 향하는 변도 하나 가지므로 두 차수를 기계적으로 같다고 두면 안 됩니다.

표현이 바뀌어도 부모·자식 관계는 보존된다

같은 루트 트리를 중첩된 집합, 중첩된 괄호, 결각(들여쓰기)으로 표현할 수 있습니다. 앞의 A~K 트리는 괄호로 다음처럼 나타낼 수 있습니다.

(A (B (E) (F) (G)) (C) (D (H (I) (J) (K))))

여는 괄호 다음의 첫 노드가 해당 서브트리의 루트이고, 같은 깊이에서 나란히 닫히는 묶음은 형제입니다. 들여쓰기 표현에서는 한 단계 깊게 들어갈 때마다 부모의 자식이 됩니다. 중첩된 집합에서는 바깥 집합 안의 부분집합이 서브트리를 나타냅니다.

노드에 저장된 데이터가 달라도 부모·자식 연결 구조가 같으면 두 트리는 닮은 트리입니다. 따라서 표현을 번역할 때 노드 이름의 모양보다 어떤 노드가 누구의 자식인지, 형제들의 묶음이 어디에서 끝나는지를 보존해야 합니다.

이진 트리는 자식 수뿐 아니라 왼쪽과 오른쪽을 구분한다

이진 트리(binary tree)는 공집합이거나 모든 노드가 최대 두 개의 서브트리를 갖는 루트 트리입니다. 두 서브트리는 왼쪽과 오른쪽으로 구분됩니다. 그래서 루트 A에 자식 B 하나가 있을 때 B가 왼쪽 자식인 트리와 오른쪽 자식인 트리는 서로 다른 이진 트리입니다.

‘자식이 두 개 이하인 루트 트리’만으로 기억하면 공트리를 허용한다는 점과 좌우 순서가 구조의 일부라는 점을 놓치기 쉽습니다. 이진 탐색 트리에서 작은 키를 왼쪽, 큰 키를 오른쪽에 두는 규칙도 이 좌우 구분을 전제로 합니다.

높이 문제는 레벨별 수용량을 합해 푼다

루트의 레벨을 0으로 두면 레벨 i가 담을 수 있는 노드는 최대 2ⁱ개입니다. 높이가 h인 이진 트리의 최대 노드 수는 각 레벨의 최대치를 더한 값입니다.

1+2+4+···+2^h = ∑_i=0^h2ⁱ = 2^h+1−1

높이 4라면 최대 노드 수는 2⁵−1=31개입니다. 반대로 n개 노드를 가능한 한 촘촘히 배치했을 때의 최소 높이는 강의 표기에 따라 H_min=⌊log₂n⌋입니다. 이는 정수 n에 대해 ⌈log₂(n+1)⌉−1과 같은 값입니다.

직접 구성한 예로 노드가 18개라면 2⁴=16≤18<32=2⁵이므로 최소 높이는 4입니다. 높이 3의 최대 용량은 15라서 18개를 담을 수 없고, 높이 4에서는 최대 31개까지 가능하므로 경계가 확인됩니다.

용량 구간: 최소 높이가 h라는 말은 2^h≤n≤2^h+1−1이라는 뜻입니다. 로그값만 계산하지 말고 바로 아래 높이의 최대 용량이 n보다 작은지 확인하면 반올림 오류를 막을 수 있습니다.

완전·포화·경사 이진 트리는 채우는 방식이 다르다

완전 이진 트리는 마지막 레벨 직전까지 모두 채워져 있고 마지막 레벨은 왼쪽부터 빈틈없이 채워진 이진 트리입니다. 같은 노드 수를 가진 이진 트리 가운데 최소 높이를 가집니다. 마지막 레벨의 중간이 비어 있는데 오른쪽에 노드가 있으면 완전 이진 트리가 아닙니다.

이 강의에서 포화 이진 트리는 높이 k의 레벨 0부터 k까지 모든 노드가 채워진 경우를 뜻합니다. 따라서 높이가 5인 포화 이진 트리의 노드 수는 반드시 2⁶−1=63개이므로 60개 노드를 가진 포화 이진 트리는 존재하지 않습니다. 포화 이진 트리는 완전 이진 트리의 특별한 경우입니다.

경사 이진 트리는 각 단계에서 사실상 한쪽 자식만 이어져 노드 n개의 높이가 최대 n−1이 되는 형태입니다. 같은 14개 노드라도 완전 이진 트리는 높이 3까지 줄일 수 있지만 경사 이진 트리는 높이 13이 됩니다. 노드 수만 같다고 검색 비용까지 같은 것은 아닙니다.

존재성 판단: ‘이진 트리’라면 높이 h에서 노드 수는 적어도 h+1, 많아도 2^h+1−1입니다. ‘포화’라는 조건이 붙을 때만 노드 수가 최대치와 정확히 같아야 합니다.

이진 탐색 트리는 한 노드가 아니라 서브트리 전체를 비교한다

이진 탐색 트리(binary search tree)는 각 노드에 탐색용 키를 저장하고, 임의의 노드 키를 k_i라 할 때 왼쪽 서브트리의 모든 키는 k_i보다 작고 오른쪽 서브트리의 모든 키는 더 큰 이진 트리입니다. 강의는 서로 다른 키를 전제로 이 엄격한 부등식을 사용합니다.

루트 12의 왼쪽 자식이 8이고 8의 오른쪽 자식이 15인 트리는 잘못되었습니다. 15는 바로 부모 8보다 크다는 국소 조건은 만족하지만, 루트 12의 왼쪽 서브트리 안에 있으면서 12보다 크기 때문입니다. 각 노드의 직계 자식만 검사하지 말고 조상에서 물려받은 허용 범위를 함께 확인해야 합니다.

범위 검사: 루트에서는 범위가 제한되지 않습니다. 왼쪽으로 내려가면 상한을 현재 키로, 오른쪽으로 내려가면 하한을 현재 키로 갱신합니다. 새 키가 지금까지 누적된 하한과 상한 사이에 있어야 합니다.

삽입 순서가 트리의 모양과 검색 비용을 바꾼다

키를 차례로 삽입할 때 첫 키가 루트가 되고, 이후 키는 루트부터 비교하여 작으면 왼쪽, 크면 오른쪽으로 내려가 빈 자리에 놓입니다. 강의의 순서 7,3,9,6,2,4,8,1,5를 따라가면 7을 루트로 하여 양쪽에 키가 분산됩니다.

7을 루트로 둡니다.
3은 7보다 작아 왼쪽, 9는 커서 오른쪽에 둡니다.
6은 6<7, 6>3이므로 3의 오른쪽에 둡니다.
2와 4는 각각 3의 왼쪽과 6의 왼쪽으로, 8은 9의 왼쪽으로 내려갑니다.
1은 2의 왼쪽, 5는 4의 오른쪽에 놓입니다.

같은 키 집합을 1,2,3,4,5,6,7,8,9처럼 오름차순으로 삽입하면 모든 키가 오른쪽으로 이어져 높이 8인 경사 이진 트리가 됩니다. 즉 이진 탐색 트리의 조건을 만족한다는 사실과 검색이 효율적이라는 사실은 같지 않습니다.

검색은 비교 경로와 실패 위치까지 기록한다

검색은 루트에서 시작합니다. 목표 키와 현재 키가 같으면 성공하고, 작으면 왼쪽 자식, 크면 오른쪽 자식으로 이동합니다. 가야 할 자식이 없으면 해당 키가 없다고 결론 내립니다.

강의의 트리에서 루트가 10, 왼쪽이 8, 오른쪽이 34이고 8의 오른쪽이 12, 12의 왼쪽이 9라고 하겠습니다.

9 검색: 10 → 8 → 12 → 9, 네 번 비교 후 성공
32 검색: 10 → 34 → 32, 세 번 비교 후 성공
7 검색: 10 → 8 → 4 → 6 → 오른쪽 없음, 네 노드를 비교한 뒤 실패

키 k_i가 검색될 확률을 S_i, 도달할 때 필요한 비교 횟수를 C_i=level(k_i)+1이라 하면 평균 비교 횟수는 ∑S_iC_i입니다. 강의 예에서 A, B, C, D의 확률이 0.5, 0.3, 0.1, 0.1이고 비교 횟수가 1, 2, 3, 4이면 기대값은 0.5×1+0.3×2+0.1×3+0.1×4=1.8입니다. 자주 찾는 A가 깊어지는 다른 배치에서는 2.2가 되어 더 비효율적입니다.

강의의 Huffman 부호화 참고 예도 빈도가 높은 문자를 더 얕은 위치에 두어 가중 깊이를 줄이는 관점을 보여 줍니다. 핵심은 단순한 높이뿐 아니라 각 키의 검색 확률까지 고려하면 효율의 판단이 달라질 수 있다는 점입니다.

신장 트리는 모든 꼭지점을 남기고 사이클을 걷어낸다

그래프 G의 신장 트리는 G의 모든 꼭지점을 포함하면서 연결되어 있고 사이클이 없는 부분 그래프입니다. 꼭지점이 n개이므로 선택된 변은 정확히 n−1개입니다. 원래 그래프에 있는 변만 사용할 수 있지만, 조건을 만족하는 신장 트리는 여러 개일 수 있습니다.

가중 그래프의 신장 트리 중 선택한 변의 가중치 합이 가장 작은 것을 최소 신장 트리(minimum spanning tree, MST)라고 합니다. 모든 변의 가중치를 더하는 것이 아니라 선택된 신장 트리의 변만 더합니다. 완전 그래프 K_n의 신장 트리 수가 nⁿ⁻²로 빠르게 늘어나는 예는 모든 후보를 일일이 비교하기보다 선택 알고리즘이 필요한 이유를 보여 줍니다.

Kruskal은 가장 싼 변을 보되 사이클이면 건너뛴다

Kruskal 알고리즘은 그래프 전체의 변을 가중치 오름차순으로 보고, 현재 선택한 변들과 사이클을 만들지 않는 가장 가벼운 변을 추가합니다. 모든 꼭지점이 연결되어 변이 n−1개가 되면 멈춥니다.

강의의 A~G 가중 그래프에서 선택 과정을 재구성하면 다음과 같습니다.

FE(1), AB(2), FG(3), BG(4)를 선택합니다.
가중치 5인 AG와 GE는 이미 연결된 꼭지점들 사이에 사이클을 만들므로 건너뜁니다.
ED(5)는 새 꼭지점 D를 연결하므로 선택합니다.
AF(6)은 같은 연결성분 안에서 사이클을 만들므로 건너뜁니다.
DC(7)로 마지막 꼭지점 C를 연결합니다.

선택된 변은 7개 꼭지점에 필요한 6개이며 총가중치는 1+2+3+4+5+7=22입니다. ‘작은 변부터’만 기억하고 사이클 검사를 생략하면 변 AG나 GE를 불필요하게 넣어 트리가 아닌 결과를 만들 수 있습니다.

Prim은 현재 트리의 경계에서 가장 싼 변을 고른다

Prim 알고리즘은 임의의 시작 꼭지점 하나를 트리에 넣고, 현재 트리 안의 꼭지점과 바깥 꼭지점을 잇는 변 가운데 가중치가 가장 작은 변을 선택합니다. 선택할 때마다 바깥 꼭지점 하나가 트리에 들어오며, 모든 꼭지점이 포함될 때까지 반복합니다.

같은 강의 그래프에서 G를 시작점으로 하면 꼭지점 추가 순서는 G → F → E → B → A → D → C입니다. 선택 변은 차례로 GF(3), FE(1), GB(4), BA(2), ED(5), DC(7)이며 총가중치는 역시 22입니다.

구분	Kruskal	Prim
관찰 대상	그래프 전체의 변	현재 트리와 바깥을 잇는 경계 변
성장 모습	여러 작은 연결 조각이 합쳐질 수 있음	하나의 트리가 시작점에서 계속 자람
거절 기준	선택하면 사이클이 생기는 변	두 끝점이 모두 현재 트리 안에 있는 변
공통 종료	모든 꼭지점을 연결한 `n−1`개의 변

Prim에서 그래프 전체의 최솟값만 찾으면 안 됩니다. 현재 트리와 연결되지 않은 두 바깥 꼭지점 사이의 싼 변은 아직 선택 대상이 아닙니다. 반대로 Kruskal은 특정 시작점이나 현재 트리의 경계를 사용하지 않습니다.

처음 보는 트리 문제는 네 장부로 검산한다

구조 장부: 꼭지점 수, 변의 수, 연결성과 사이클을 적어 트리 여부를 판정합니다.
레벨 장부: 루트를 레벨 0으로 두고 각 레벨의 노드 수와 최대 용량을 비교합니다.
비교 장부: 이진 탐색 트리에서는 현재 키, 비교 결과, 이동 방향과 남은 허용 범위를 기록합니다.
선택 장부: MST에서는 선택한 변, 누적 가중치, 새로 연결된 꼭지점과 거절 이유를 적습니다.

이 네 장부는 서로 다른 문제를 같은 방식으로 억지로 푸는 도구가 아닙니다. 질문에 맞는 불변 조건을 눈에 보이게 만들어 중간 단계의 오류를 찾는 장치입니다. 결과만 맞는지 보는 대신 각 단계가 트리의 조건을 계속 유지하는지 확인할 수 있습니다.

핵심 개념 정리

트리 판정: 연결 그래프에서 꼭지점 n개와 변 n−1개는 트리 여부를 빠르게 판정하는 짝 조건이다.
루트 트리: 부모·자식·형제·레벨·높이는 선택한 루트를 기준으로 결정되며, 노드 차수는 자식 수다.
이진 트리: 왼쪽과 오른쪽이 구분되며, 높이 h에서 최대 노드 수는 2^h+1−1이다.
이진 탐색: 삽입 순서가 모양을 바꾸고, 검색은 누적된 대소 범위에 따라 한쪽 서브트리만 선택한다.
검색 효율: 비교 횟수는 레벨에 1을 더한 값이고, 검색 확률이 다르면 가중 평균으로 비교한다.
최소 신장 트리: Kruskal은 변 전체, Prim은 현재 트리의 경계를 기준으로 고르지만 둘 다 모든 꼭지점을 최소 비용으로 연결한다.

문제를 받으면 먼저 구조 판정, 높이 계산, 키 검색, 최소 비용 연결 중 무엇을 요구하는지 정하십시오. 그다음 트리의 연결+n−1, 이진 트리의 레벨별 용량, 탐색 트리의 누적 키 범위, MST의 사이클 없는 n−1개 변 가운데 하나를 불변 조건으로 잡습니다. 매 단계 뒤 이 조건이 유지되는지 장부로 확인하면 그림이 복잡해져도 같은 풀이를 재현할 수 있습니다.

예상문제 10선

1. 꼭지점이 9개인 연결 그래프가 변 8개를 가진다. 이 그래프에 대한 옳은 결론은?

① 사이클이 하나 있는 숲이다. ② 연결 여부와 무관하게 트리다. ③ 연결되고 변이 n−1개이므로 트리다. ④ 트리라면 변이 9개여야 하므로 트리가 아니다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

① 오답: 숲은 연결되지 않을 수 있지만 문제의 그래프는 연결되어 있으며 n−1개의 변 조건도 만족한다.
② 오답: 변의 수만 n−1이라고 해서 트리가 되는 것이 아니라 연결 전제가 필요하다.
③ 정답: n=9일 때 n−1=8이고 연결 그래프이므로 트리 판정 정리의 조건을 모두 만족한다.
④ 오답: n개 꼭지점을 가진 트리의 변은 n개가 아니라 n−1개다.

2. 루트 트리의 노드 차수와 그래프의 꼭지점 차수를 구분한 설명으로 옳은 것은?

① 강의의 루트 트리에서 노드 차수는 자식 수이고, 그래프의 차수는 발생한 변의 수다. ② 루트가 아닌 노드에서는 두 차수가 언제나 같다. ③ 리프 노드는 부모와 연결되므로 노드 차수가 1이다. ④ 트리의 차수는 모든 노드 차수의 합이다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

① 정답: 루트 트리 용어는 아래쪽 자식만 세지만 그래프 차수는 부모 방향의 변도 센다.
② 오답: 루트가 아닌 내부 노드는 부모로 향하는 변 때문에 그래프 차수가 자식 수보다 1 크다.
③ 오답: 리프는 자식이 없으므로 루트 트리의 노드 차수는 0이다.
④ 오답: 트리의 차수는 합이 아니라 노드 차수 가운데 최댓값이다.

3. 높이가 5인 이진 트리가 가질 수 있는 최대 노드 수는?

① 31개 ② 32개 ③ 62개 ④ 63개

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 31은 높이 4에서 레벨 0부터 4까지 채운 최대값이다.
② 오답: 32는 레벨 5 하나의 최대 노드 수이며 앞 레벨들이 빠졌다.
③ 오답: 등비합 2⁶−1에서 1을 잘못 더하거나 뺀 값이다.
④ 정답: 레벨 0부터 5까지의 합은 1+2+4+8+16+32=63이다.

4. 높이 3의 마지막 레벨에서 왼쪽 위치 하나가 비었지만 그 오른쪽에 노드가 있다. 이 이진 트리의 분류는?

① 포화 이진 트리이지만 완전 이진 트리는 아니다. ② 이진 트리일 수는 있지만 완전 이진 트리는 아니다. ③ 마지막 레벨에 노드가 있으므로 완전 이진 트리다. ④ 노드 수와 관계없이 경사 이진 트리다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 포화 이진 트리는 모든 레벨의 모든 자리가 채워져야 하므로 빈 위치가 있을 수 없다.
② 정답: 자식 수와 좌우 구조는 이진 트리 조건을 만족할 수 있지만 마지막 레벨의 왼쪽 채움 규칙을 어겼다.
③ 오답: 마지막 레벨은 단순히 노드가 존재하는 것이 아니라 왼쪽부터 빈틈없이 채워져야 한다.
④ 오답: 경사 이진 트리는 노드들이 주로 한쪽 자식으로 연속되는 별도의 모양이다.

5. 루트 20의 왼쪽 자식이 8이고, 8의 오른쪽 서브트리에 24가 있다. 이진 탐색 트리 판정으로 옳은 것은?

① 24가 8보다 크므로 올바른 위치다. ② 24가 리프라면 조상 키와 비교할 필요가 없다. ③ 오른쪽 방향으로 한 번 갔으므로 20보다 커도 된다. ④ 20의 왼쪽 서브트리 전체는 20보다 작아야 하므로 잘못된 위치다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 직계 부모와의 대소 관계만 확인하면 루트에서 물려받은 상한 20을 놓친다.
② 오답: 리프 여부와 상관없이 모든 조상의 서브트리 범위 조건을 만족해야 한다.
③ 오답: 8에서 오른쪽으로 가도 그 위치는 여전히 20의 왼쪽 서브트리 안이다.
④ 정답: 허용 범위는 8보다 크고 20보다 작아야 하므로 키 24는 범위를 벗어난다.

6. 이진 탐색 트리에 10, 6, 15, 8을 차례로 삽입할 때 8의 위치는?

① 6의 오른쪽 자식 ② 6의 왼쪽 자식 ③ 15의 왼쪽 자식 ④ 15의 오른쪽 자식

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ①

① 정답: 8은 10보다 작아 왼쪽의 6으로 가고, 6보다 커서 빈 오른쪽 자리에 놓인다.
② 오답: 8과 6의 비교 방향을 반대로 적용한 위치다.
③ 오답: 첫 비교에서 8은 10보다 작으므로 15가 있는 오른쪽 서브트리에 들어갈 수 없다.
④ 오답: 루트 비교와 15 비교 모두 실제 삽입 경로에 포함되지 않는다.

7. 키 X, Y, Z의 검색 확률이 각각 0.5, 0.3, 0.2이고 비교 횟수가 1, 2, 3일 때 평균 비교 횟수는?

① 1.5회 ② 1.6회 ③ 1.7회 ④ 2.0회

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ③

① 오답: 가장 높은 확률과 한 번의 비교만 반영하면 나머지 키의 비용이 빠진다.
② 오답: 마지막 항 0.2×3=0.6을 정확히 더해야 한다.
③ 정답: 0.5×1+0.3×2+0.2×3=0.5+0.6+0.6=1.7이다.
④ 오답: 단순 비교 횟수의 중앙값이나 평균이 아니라 확률을 곱한 가중 평균을 사용한다.

8. Kruskal 알고리즘과 Prim 알고리즘의 차이를 바르게 설명한 것은?

① Kruskal은 시작 꼭지점을 정하고 경계 변만 살핀다. ② Kruskal은 전체 변을 가중치 순으로 보고, Prim은 현재 트리의 경계 변을 본다. ③ Prim은 사이클을 허용한 뒤 마지막에 변을 제거한다. ④ 두 알고리즘은 선택 기준과 성장 방식이 완전히 같다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 시작 꼭지점과 현재 경계를 사용하는 설명은 Prim에 해당한다.
② 정답: 두 알고리즘은 같은 MST를 목표로 하지만 후보 변을 바라보는 범위가 다르다.
③ 오답: Prim은 트리 안과 밖을 잇는 변으로 새 꼭지점을 추가하므로 선택 과정에서 트리를 유지한다.
④ 오답: Kruskal은 여러 연결 조각을 합칠 수 있고 Prim은 하나의 트리를 계속 확장한다.

9. Kruskal 과정에서 현재 선택된 변들이 A-B-C 경로를 이미 이루고 있다. 가중치가 다음으로 작은 변 AC를 만나면 어떻게 해야 하는가?

① 가중치가 작으므로 사이클 여부와 관계없이 선택한다. ② AC를 선택하고 가장 무거운 꼭지점을 제거한다. ③ AC를 선택한 뒤 연결되지 않은 꼭지점을 무시한다. ④ AC가 사이클을 만들므로 건너뛰고 다음 변을 검토한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ④

① 오답: 가중치 순서는 후보 순서일 뿐 트리의 사이클 금지 조건보다 우선하지 않는다.
② 오답: MST 알고리즘은 꼭지점을 제거하지 않고 모든 꼭지점을 포함해야 한다.
③ 오답: 신장 트리는 원래 그래프의 모든 꼭지점을 연결해야 한다.
④ 정답: A와 C가 이미 선택된 경로로 연결되어 있으므로 AC를 더하면 폐회로가 생긴다.

10. 가중 연결 그래프에서 얻은 후보가 꼭지점 6개를 모두 포함하고, 사이클이 없으며, 선택 변 5개의 가중치 합이 18이다. MST라고 결론 내리기 위해 추가로 필요한 확인은?

① 각 꼭지점의 자식 수가 모두 같은지 확인한다. ② 다른 신장 트리보다 더 작은 총가중치가 없는지 선택 과정으로 보장한다. ③ 원래 그래프의 모든 변 가중치 합도 18인지 확인한다. ④ 후보 트리에 변 하나를 더해도 사이클이 없는지 확인한다.

정답입니다.

오답입니다. 답안을 다시 선택해 보세요.

정답 및 해설 보기

정답: ②

① 오답: 모든 노드의 자식 수가 같은 정규성은 신장 트리나 최소성의 조건이 아니다.
② 정답: 주어진 조건은 신장 트리임을 보이지만 MST가 되려면 Kruskal·Prim 같은 올바른 선택으로 최소성도 확보해야 한다.
③ 오답: 총가중치는 원래 그래프 전체가 아니라 후보 신장 트리에 선택된 변만 합한다.
④ 오답: 6개 꼭지점의 트리는 이미 5개 변을 가지므로 변을 더하면 사이클이 생긴다.

참고 자료와 작성 기준

이 글은 해당 차시 강의자료를 바탕으로 학습 목적에 맞게 재구성한 비공식 학습자료입니다. 트리 판정, 높이 계산, 이진 탐색과 최소 신장 트리 선택을 학습자가 직접 재현하고 검산할 수 있도록 풀이 장부와 오류 분석을 구성했습니다.

작성·편집: 올에이클래스 학습연구팀
주요 근거: 한국방송통신대학교 이산수학 11강 「트리」 강의자료 54쪽(2021) :codex-file-citation{path="K1. 컴퓨터과학과/1. 재검토필요/2-1 이산수학/1. 강의록/이산수학_강의록_11강.pdf" purpose="source"}
자료 성격: 강의자료의 정의와 범위를 바탕으로 재구성한 비공식 학습자료
편집 원칙: 올에이클래스 편집 정책
최종 내용 검토: 2026-09-06

방송대 이산수학 11강: 이진 탐색 트리와 최소 신장 트리