[알고리즘] 5. 알고리즘 작성을 위한 자료구조 (2)

1. 트리(Tree)

• 선으로 구성되며 사이클이 없어야 함 • 트리를 구성하는 정점을 노드(node) 라고 함

 

2) 트리의 예시

• 친족 관계를 나타내는 가계도

• 조직도

• 파일 시스템 구조

 

3) 노드(Node)의 종류

• 루트 노드(root node): 트리의 최상위 노드

• 부모 노드(parent node): 특정 노드의 상위에 연결된 노드

• 자식 노드(children node): 특정 노드의 하위에 연결된 노드

• 조상 노드(ancestor node): 특정 노드에서 루트 노드에 이르기까지의 모든 상위 노드

• 자손 노드(descendant node): 특정 노드에서 하위에 연결된 모든 노드

• 형제 노드(sibling node): 같은 부모 노드를 가진 노드들

 

4) 트리의 구조적 요소

• 레벨(level): 루트 노드를 0으로 하여 한 층씩 내려갈수록 1씩 증가

• 노드의 높이(height):

- 루트에서 해당 노드까지의 간선 수

- 트리 내 모든 노드의 높이 중 가장 큰 값

- 트리의 최대 레벨 (트리의 깊이, depth)

 

5) 노드 및 트리의 차수

• 노드의 차수: 해당 노드에 연결된 자식 노드의 수

• 단말 노드(leaf node): 차수가 0인 노드

• 비단말 노드(internal node): 자식을 가지는 노드

• 트리의 차수: 트리 내 노드들의 차수 중 가장 큰 값

 

6) 포리스트(Forest)

• 루트를 제거하여 생성한 부분 트리들의 집합

 

 

 

2. 이진 트리(Binary Tree)

• 모든 노드들의 자식 노드가 최대 2개인 트리 • 왼쪽 서브트리와 오른쪽 서브트리를 구분

 

1) 이진 트리의 종류

• 포화 이진 트리: 모든 노드가 완전히 채워진 트리

• 완전 이진 트리: 마지막 레벨을 제외한 모든 노드가 2개의 자식을 가지며, 마지막 레벨은 왼쪽부터 채워짐

• 편향 이진 트리: 왼쪽 혹은 오른쪽으로만 자식 노드를 가지는 트리 (탐색 시간 복잡도 O(n))

 

2) 이진 트리의 순회 방법

• 전위 순회(preorder): 루트 → 왼쪽 서브트리 → 오른쪽 서브트리

• 중위 순회(inorder): 왼쪽 서브트리 → 루트 → 오른쪽 서브트리

• 후위 순회(postorder): 왼쪽 서브트리 → 오른쪽 서브트리 → 루트

 

 

 

3. 그래프(Graph)

1) 그래프의 개념

• 정점(Vertex)과 간선(Edge)으로 이루어진 자료구조

• 공집합이 아닌 정점의 집합 V 와 정점의 쌍을 연결하는 간선의 집합 E 로 구성됨

• G = (V, E) • V = {1,2,...,n} • E = {(v1, v2), ...}

• 복잡한 관계를 직관적으로 표현하는 데 유용

 

2) 그래프의 주요 요소

• 정점(vertex): 특정 대상을 나타내는 데이터 단위

• 간선(edge): 정점 간의 연결 관계를 나타내는 선

 

3) 그래프의 응용

• 최단 거리 탐색

• 연구 및 공정 계획 분석

• 전자 회로 분석

• 통계학 등 다양한 분야 활용

 

4) 그래프의 기원

• 1736년, 오일러(Euler)가 "쾨니히스베르크 다리 문제" 해결을 위해 최초 사용

• 그래프의 모든 정점의 차수가 짝수일 경우 오일러 경로(Eulerian Path) 문제 해결 가능

 

5) 그래프의 용어

• 차수(degree): 정점에 연결된 간선의 수

• 무방향 그래프: 정점에 연결된 모든 간선의 개수

• 방향 그래프: 진입 차수(in-degree)와 진출 차수(out-degree)로 구분

• 경로(path): 간선을 따라 정점을 나열한 것

• 경로의 길이(path length): 경로 내 간선 개수

• 단순 경로(simple path): 중복되지 않는 정점들로 구성된 경로

• 사이클(cycle): 시작점과 도착점이 같은 단순 경로

 

6) 그래프의 종류

• 무방향 그래프: 간선에 방향이 없음

• 방향 그래프: 간선에 방향이 있음 (한 방향으로만 이동 가능)

• 완전 그래프: 모든 정점이 서로 연결된 그래프

• 가중 그래프: 간선에 가중치(weight)가 부여된 그래프

 

7) 그래프의 표현 방법

• 인접 행렬(Adjacency Matrix)

• 2차원 배열을 사용하여 간선 정보를 저장하는 방법

• 정점 개수만큼의 행과 열을 갖는 행렬로 표현

• 인접 리스트(Adjacency List)

• 간선 정보를 연결 리스트 형태로 저장하는 방법

• 문제에 따라 적절한 표현 방법을 선택해야 함

---

이 내용은 휴넷사회복지평생교육원의 알고리즘 강의를 듣고 정리한 것입니다.