컴퓨터과학개론 4강 - 자료구조 (2)
이번 강의에서는 계층적 관계를 표현하는 트리와 다양한 연결 관계를 표현하는 그래프를 학습합니다. 트리의 기본 용어, 이진 트리의 순회와 유형, 그래프의 표현 방법, 깊이 우선 탐색과 너비 우선 탐색을 차례로 정리합니다.
1. 트리의 개념과 구성 요소
트리(tree)는 자료 사이의 계층적 관계를 나타내는 비선형 자료구조입니다. 선형 리스트가 자료를 한 줄의 순서로 연결한다면, 트리는 하나의 자료에서 여러 자료로 가지가 뻗어 나가는 형태를 취합니다. 조직도, 파일 시스템의 폴더 구조, 가계도처럼 상하 관계가 있는 정보를 표현할 때 적합합니다.
트리는 정보를 담는 노드(node)와 노드 사이를 연결하는 가지 또는 간선(edge)으로 구성됩니다. 비어 있지 않은 트리의 가장 위에는 하나의 루트 노드(root node)가 있으며, 루트에서 시작하여 자식 노드로 관계가 확장됩니다.
| 용어 | 의미 |
|---|---|
| 노드 | 트리를 구성하며 정보를 저장하는 항목 |
| 루트 노드 | 비어 있지 않은 트리에서 가장 위에 있는 하나의 시작 노드 |
| 부모 노드 | 어떤 노드의 바로 위에서 그 노드와 연결된 노드 |
| 자식 노드 | 어떤 노드의 바로 아래에서 그 노드와 연결된 노드 |
| 형제 노드 | 같은 부모 노드를 갖는 노드들 |
| 노드의 차수 | 그 노드가 가진 자식 노드의 수 |
| 단말 노드 또는 잎 노드 | 차수가 0인 노드, 즉 자식이 없는 노드 |
| 내부 노드 또는 비단말 노드 | 트리의 내부에서 자식 노드를 갖는 노드 |
시험 핵심: 노드의 차수는 자식의 수입니다. 따라서 잎 노드의 차수는 0이며, 루트는 트리 전체에서 하나만 존재합니다.
2. 트리의 계층, 깊이, 서브트리와 포리스트
트리의 노드는 루트를 기준으로 한 위치와 연결 관계에 따라 조상, 자손, 레벨로 설명할 수 있습니다. 어떤 노드까지 루트에서 내려오는 경로에 있는 노드는 그 노드의 조상(ancestor)이고, 어떤 노드에서 잎 노드 방향으로 내려가는 경로에 있는 노드는 그 노드의 자손(descendant)입니다.
레벨(level)은 루트에서 해당 노드까지 지나온 가지의 수입니다. 루트의 레벨은 0이고, 루트의 자식은 레벨 1입니다. 트리의 깊이 또는 높이는 가장 높은 레벨을 기준으로 나타내며, 강의록에서는 최대 잎 노드의 레벨에 1을 더한 값으로 설명합니다. 최대 레벨이 3이면 트리의 깊이는 4입니다.
서브트리(subtree)는 특정 노드를 루트로 보고 그 아래에 연결된 노드와 가지를 하나의 트리로 묶은 것입니다. 원래 트리의 루트를 제거하면 서로 분리된 서브트리들의 집합이 남는데, 이를 포리스트(forest)라고 합니다.
조상과 자손은 바로 위나 아래의 한 노드만 가리키지 않습니다. 경로 위에 있는 모든 상위 노드는 조상이고, 아래 방향 경로에 있는 모든 하위 노드는 자손입니다. 바로 연결된 경우만 부모와 자식이라고 합니다.
3. 이진 트리의 개념과 높이
이진 트리(binary tree)는 모든 노드의 차수가 2 이하인 트리입니다. 각 노드는 최대 두 개의 자식을 가지며, 자식이 만드는 서브트리를 각각 왼쪽 서브트리와 오른쪽 서브트리라고 합니다.
이진 트리에서는 왼쪽과 오른쪽을 구분합니다. 같은 두 노드가 자식으로 연결되어 있어도 어느 노드가 왼쪽에 있는지에 따라 서로 다른 이진 트리가 됩니다. 또한 왼쪽이나 오른쪽 서브트리가 비어 있을 수도 있습니다.
노드 수가 같아도 트리의 모양에 따라 높이는 달라집니다. 노드가 한쪽 방향으로만 이어지면 노드가 N개일 때 높이가 최대 N이 됩니다. 반대로 노드를 가능한 한 균형 있게 배치하면 높이는 최소가 되며, 그 높이는 대략 ⌊log₂N⌋ + 1로 증가합니다.
| 구분 | 구조 | N개 노드의 높이 |
|---|---|---|
| 한쪽으로 치우친 경우 | 각 노드가 사실상 하나의 자식만 가져 긴 사슬을 이룸 | 최대 N |
| 균형 있게 채운 경우 | 각 레벨에 노드를 가능한 한 많이 배치 | 최소 약 ⌊log₂N⌋ + 1 |
이진 트리는 자식이 반드시 두 개인 트리가 아니라, 각 노드가 가질 수 있는 자식의 수가 최대 두 개인 트리입니다.
4. 이진 트리의 순회
순회(traversal)는 트리의 모든 노드를 빠짐없이 한 번씩 방문하는 과정입니다. 이진 트리의 기본 순회 방법은 루트 노드를 언제 방문하는가에 따라 전위 순회, 중위 순회, 후위 순회로 구분합니다. 여기서 D는 루트, L은 왼쪽 서브트리, R은 오른쪽 서브트리를 뜻합니다.
| 순회 방법 | 방문 순서 | 기억 방법 |
|---|---|---|
| 전위 순회(preorder) | D → L → R | 루트를 먼저 방문 |
| 중위 순회(inorder) | L → D → R | 왼쪽과 오른쪽 사이에서 루트를 방문 |
| 후위 순회(postorder) | L → R → D | 루트를 마지막에 방문 |
순회는 전체 트리에 한 번만 적용하는 규칙이 아니라 각 서브트리에 재귀적으로 같은 규칙을 적용합니다. 예를 들어 전위 순회는 루트를 방문한 뒤 왼쪽 서브트리를 전위 순회하고, 마지막으로 오른쪽 서브트리를 전위 순회합니다.
강의록의 예시 트리 순회 결과는 다음과 같습니다.
- 전위 순회: A → B → D → E → G → C → F → H
- 중위 순회: D → B → G → E → A → F → H → C
- 후위 순회: D → G → E → B → H → F → C → A
순회 문제에서는 먼저 D, L, R 중 루트 D의 위치를 확인합니다. 전위는 DLR, 중위는 LDR, 후위는 LRD로 적어 두고 각 서브트리에 동일한 규칙을 반복하면 실수를 줄일 수 있습니다.
5. 포화·완전·편향 이진 트리
이진 트리는 노드가 채워진 모습에 따라 여러 유형으로 나뉩니다. 서로 비슷해 보이지만 각 레벨이 모두 채워졌는지, 마지막 레벨이 어느 방향부터 채워졌는지를 구분해야 합니다.
| 유형 | 특징 | 핵심 판별 기준 |
|---|---|---|
| 포화 이진 트리 | 모든 레벨이 노드로 가득 차고 모든 내부 노드가 두 자식을 가짐 | 깊이가 k이면 전체 노드는 2k-1개, 잎 노드는 2k-1개 |
| 완전 이진 트리 | 마지막 레벨 전까지 가득 차며 마지막 레벨은 왼쪽부터 차례로 채워짐 | 레벨 순서로 붙인 노드 번호가 중간에 끊기지 않음 |
| 편향 이진 트리 | 노드가 한쪽 방향의 자식으로만 이어짐 | 왼쪽 편향과 오른쪽 편향으로 구분 |
깊이가 k인 포화 이진 트리에서는 레벨이 내려갈 때마다 노드 수가 두 배가 됩니다. 따라서 전체 노드 수는 1 + 2 + 4 + … + 2k-1 = 2k-1이고, 마지막 레벨의 잎 노드는 2k-1개입니다.
완전 이진 트리는 포화 이진 트리일 수도 있지만 항상 포화 상태일 필요는 없습니다. 마지막 레벨이 덜 채워져도 왼쪽부터 빈자리 없이 채워져 있으면 완전 이진 트리입니다. 반면 오른쪽에 노드가 있으면서 그보다 왼쪽 자리가 비어 있으면 완전 이진 트리가 아닙니다.
포화는 모든 레벨이 가득 찬 상태이고, 완전은 마지막 레벨만 덜 찰 수 있으나 반드시 왼쪽부터 채워진 상태입니다.
6. 그래프의 개념과 종류
그래프(graph)는 객체와 객체 사이의 다양한 연결 관계를 표현하는 비선형 자료구조입니다. 그래프 G는 유한한 정점의 집합 V와 두 정점을 연결하는 유한한 간선의 집합 E로 이루어지며, G=(V, E)로 나타냅니다.
트리가 하나의 루트에서 시작하는 계층 구조를 중심으로 한다면, 그래프는 정점 사이의 연결 자체를 중심으로 합니다. 도로망, 지하철 노선, 통신망, 사람 사이의 관계 등을 그래프로 표현할 수 있습니다.
| 종류 | 간선의 특징 | 표현 |
|---|---|---|
| 무방향 그래프 | 간선에 방향이 없어 양쪽으로 연결됨 | 두 정점의 순서가 없는 집합 {u, v} |
| 방향 그래프 | 간선에 출발점과 도착점의 방향이 있음 | 순서가 있는 쌍 (u, v) |
무방향 그래프에서 {1, 2}와 {2, 1}은 같은 간선입니다. 방향 그래프에서는 (1, 2)와 (2, 1)이 서로 다른 방향의 간선이므로 별도로 구분합니다.
트리는 그래프의 특수한 형태입니다. 트리는 사이클이 없고 모든 정점이 서로 연결된 무방향 그래프로 볼 수 있습니다.
7. 그래프의 기본 용어와 연결성
두 정점이 하나의 간선으로 직접 연결되어 있으면 두 정점은 인접(adjacent)한다고 합니다. 이때 그 간선은 두 정점에 부속(incident)되어 있다고 합니다. 인접은 정점과 정점 사이의 관계이고, 부속은 정점과 간선 사이의 관계입니다.
경로(path)는 간선으로 연결된 정점들의 순서이며, 경로에 포함된 간선 수를 경로의 길이라고 합니다. 경로에 나타나는 정점이 모두 다르면 단순 경로입니다. 세 개 이상의 정점을 거쳐 시작 정점으로 되돌아오는 경로는 사이클(cycle)이고, 시작과 끝을 제외한 정점이 모두 다르면 단순 사이클입니다.
두 정점 사이에 경로가 존재하면 두 정점은 연결되어 있다고 합니다. 무방향 그래프에서 모든 정점 쌍 사이에 경로가 존재하면 그 그래프는 연결 그래프입니다.
| 구분 | 의미 |
|---|---|
| 무방향 그래프의 차수 | 한 정점에 부속된 간선의 수 |
| 진입 차수(indegree) | 방향 그래프에서 해당 정점으로 들어오는 간선의 수 |
| 진출 차수(outdegree) | 방향 그래프에서 해당 정점에서 나가는 간선의 수 |
경로의 길이는 경로에 포함된 정점 수가 아니라 간선 수입니다. 정점 다섯 개를 네 개의 간선으로 이어 방문했다면 경로의 길이는 4입니다.
8. 그래프의 표현 방법
그래프를 컴퓨터에 저장하는 대표적인 방법은 인접 행렬(adjacency matrix)과 인접 리스트(adjacency list)입니다. 두 방법은 같은 그래프를 표현하지만 필요한 저장 공간과 인접 정점 확인 방식이 다릅니다.
인접 행렬
정점이 n개이면 n×n 크기의 2차원 배열을 만들고, 정점 vi와 vj 사이에 간선이 있으면 A[i][j]를 1로, 없으면 0으로 표시합니다. 무방향 그래프의 인접 행렬은 주대각선을 기준으로 대칭이 됩니다.
인접 리스트
각 정점마다 그 정점과 인접한 정점들의 목록을 연결 리스트 형태로 저장합니다. 정점별 머리 포인터 또는 목록을 두고, 그 뒤에 이웃 정점을 차례로 연결합니다. 실제 간선이 많지 않은 그래프에서는 존재하는 연결만 기록하므로 인접 행렬보다 공간을 절약할 수 있습니다.
| 비교 항목 | 인접 행렬 | 인접 리스트 |
|---|---|---|
| 기본 구조 | n×n 2차원 배열 | 정점별 인접 정점 목록 |
| 간선 존재 확인 | 행렬의 한 칸을 바로 확인 | 해당 정점의 목록을 탐색 |
| 저장 공간 | 간선이 적어도 n²개의 칸이 필요 | 주로 실제 정점과 간선 수에 비례 |
| 적합한 경우 | 간선이 많은 그래프, 빠른 연결 확인 | 간선이 적은 그래프, 이웃 순회 |
9. 깊이 우선 탐색과 너비 우선 탐색
그래프 순회는 한 정점에서 출발하여 그래프의 모든 정점을 체계적으로 방문하는 과정입니다. 대표적인 방법은 깊이 우선 탐색과 너비 우선 탐색입니다. 이미 방문한 정점을 다시 처리하지 않도록 방문 여부를 기록해야 합니다.
깊이 우선 탐색
깊이 우선 탐색(DFS, Depth-First Search)은 현재 정점에서 방문하지 않은 인접 정점 하나를 선택해 가능한 한 깊이 이동합니다. 더 진행할 곳이 없으면 이전 정점으로 되돌아가 다른 길을 탐색합니다. 강의록 예시의 방문 순서는 1 → 2 → 4 → 5 → 7 → 6 → 3입니다.
너비 우선 탐색
너비 우선 탐색(BFS, Breadth-First Search)은 현재 정점과 가까운, 아직 방문하지 않은 인접 정점들을 먼저 방문한 뒤 다음 거리의 정점으로 넓혀 갑니다. 강의록 예시의 방문 순서는 1 → 2 → 3 → 4 → 5 → 6 → 7입니다.
| 구분 | DFS | BFS |
|---|---|---|
| 탐색 방향 | 한 경로를 가능한 한 깊게 탐색 | 출발점에서 가까운 정점부터 넓게 탐색 |
| 진행 방식 | 막히면 되돌아가 다른 경로 선택 | 같은 거리의 이웃을 먼저 모두 방문 |
| 대표 보조 구조 | 스택 또는 재귀 호출 | 큐 |
인접 정점을 어떤 순서로 선택하는지에 따라 구체적인 방문 순서는 달라질 수 있습니다. 그러나 DFS는 깊이 진행한 뒤 되돌아오고, BFS는 가까운 정점부터 층별로 진행한다는 원리는 변하지 않습니다.
핵심 개념 정리
- 트리는 노드와 가지로 계층 관계를 표현하는 비선형 자료구조입니다.
- 루트는 트리의 시작 노드이며, 노드의 차수는 자식 노드의 수입니다.
- 차수가 0인 노드는 잎 노드이고, 루트의 레벨은 0입니다.
- 서브트리는 특정 노드를 루트로 하는 부분 트리이고, 루트를 제거해 생긴 서브트리의 집합은 포리스트입니다.
- 이진 트리는 각 노드가 최대 두 자식을 가지며 왼쪽과 오른쪽 서브트리를 구분합니다.
- 전위 순회는 DLR, 중위 순회는 LDR, 후위 순회는 LRD 순서입니다.
- 포화 이진 트리는 모든 레벨이 가득 차고, 완전 이진 트리는 마지막 레벨을 왼쪽부터 채웁니다.
- 그래프 G=(V,E)는 정점 집합 V와 간선 집합 E로 구성됩니다.
- 경로의 길이는 경로에 포함된 간선의 수입니다.
- 인접 행렬은 n×n 배열, 인접 리스트는 정점별 이웃 목록으로 그래프를 표현합니다.
- DFS는 한 경로를 깊이 탐색하고, BFS는 출발점에서 가까운 정점부터 탐색합니다.
최종 정리: 트리는 계층 관계에 특화된 그래프의 한 형태이며, 이진 트리는 왼쪽과 오른쪽을 구분하는 최대 차수 2의 트리입니다. 그래프를 이해할 때는 정점과 간선, 경로와 연결성, 인접 행렬과 인접 리스트를 구분하고, 순회에서는 DFS의 깊이 중심 진행과 BFS의 거리 중심 진행을 정확히 비교해야 합니다.
예상문제 20선
1. 트리에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
트리는 노드와 가지를 이용하여 자료의 계층적 관계를 나타내는 비선형 자료구조입니다.
2. 비어 있지 않은 트리에서 가장 위에 있는 하나의 시작 노드는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
루트 노드는 트리의 최상위 시작 노드이며 비어 있지 않은 트리에 하나만 존재합니다.
3. 잎 노드의 차수는 얼마인가?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
노드의 차수는 자식의 수입니다. 잎 노드는 자식이 없으므로 차수가 0입니다.
4. 강의록의 정의에 따라 최대 잎 노드의 레벨이 3일 때 트리의 깊이는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
강의록에서는 트리의 깊이를 최대 잎 노드의 레벨에 1을 더한 값으로 설명합니다.
5. 이진 트리에서 한 노드가 가질 수 있는 자식 노드의 최대 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
이진 트리는 각 노드의 차수가 2 이하인 트리이므로 자식은 최대 두 개입니다.
6. 전위 순회의 방문 순서로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
전위 순회는 루트 D를 먼저 방문한 뒤 왼쪽 L, 오른쪽 R의 순서로 진행합니다.
7. 중위 순회의 방문 순서로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
중위 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리의 순서인 LDR입니다.
8. 후위 순회에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
후위 순회는 L → R → D 순서이므로 루트를 마지막에 방문합니다.
9. 깊이가 k인 포화 이진 트리의 전체 노드 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
깊이가 k인 포화 이진 트리의 각 레벨을 합하면 전체 노드 수는 2k-1입니다.
10. 완전 이진 트리의 마지막 레벨에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
완전 이진 트리는 마지막 레벨 전까지 가득 차고 마지막 레벨은 왼쪽부터 차례로 채워집니다.
11. 노드가 한쪽 방향의 자식으로만 계속 이어지는 트리는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
편향 이진 트리는 노드가 왼쪽 또는 오른쪽 한 방향으로 치우쳐 연결된 이진 트리입니다.
12. 그래프 G=(V,E)에서 V와 E가 의미하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
그래프는 유한한 정점 집합 V와 정점을 연결하는 유한한 간선 집합 E로 구성됩니다.
13. 무방향 그래프의 간선에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
무방향 간선은 출발과 도착의 구분이 없으므로 두 정점의 순서를 바꾸어도 같은 간선입니다.
14. 인접과 부속의 관계를 바르게 설명한 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
직접 연결된 두 정점은 인접하고, 그 연결 간선은 두 정점에 부속됩니다.
15. 그래프에서 경로의 길이를 결정하는 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
경로의 길이는 그 경로를 이루는 간선의 개수로 정의합니다.
16. 단순 사이클에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
단순 사이클은 시작 정점으로 되돌아오되 시작과 끝을 제외한 중간 정점이 중복되지 않는 사이클입니다.
17. 방향 그래프에서 한 정점으로 들어오는 간선의 수는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ①
정점으로 들어오는 방향 간선의 수는 진입 차수이고, 정점에서 나가는 간선의 수는 진출 차수입니다.
18. 정점이 n개인 그래프의 인접 행렬 크기는?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ②
인접 행렬은 각 정점 쌍의 연결 여부를 나타내므로 정점이 n개이면 n개의 행과 n개의 열이 필요합니다.
19. 깊이 우선 탐색(DFS)의 진행 방식은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ③
DFS는 방문하지 않은 인접 정점을 따라 깊이 진행하고 더 갈 수 없을 때 이전 정점으로 돌아갑니다.
20. 너비 우선 탐색(BFS)에 대한 설명으로 옳은 것은?
정답입니다.
오답입니다. 답안을 다시 선택해 보세요.
정답 및 해설 보기
정답: ④
BFS는 현재 정점과 가까운 미방문 인접 정점을 먼저 방문하면서 탐색 범위를 넓혀 갑니다.
댓글
댓글 쓰기