자료구조의 정의
- 자료를 효율적으로 사용하기 위해서 자료의 특성에 따라서 분류하여 구성하고 저장 및 처리하는 모든 작업
- 효율적인 자료구조는 프로그램의 실행시간을 단축, 메모리 용량 절약
자료구조
1. 선형 구조
1. 리스트
- 선형 리스트
- 연결 리스트(희소행렬(행렬 요소 0이 많은 경우))
2. 스택(LIFO구조)(push(삽입), pop(삭제))
스택의 용도
- 인터럽트 처리
- 수식의 계산
- 서브루틴의 복귀번지 저장
- 웹 브라우저 방문기록
- 재귀호출
- 깊이 우선 탐색(DFS, Depth-First Search)
삽입 - 스택 먼저 증가 후, 데이터 삽입
삭제 - 데이터 먼저 삭제 후, 스택 삭제
3. 큐(FIFO구조)
큐의 용도
- 인쇄작업 대기목록
- 프로세스 관리,
- 너비 우선 탐색(BFS, Breath-First Search)
enQueue 연산 시 rear포인터 이용
deQueue 연산 시 front포인터 이용
4. 데크
Scroll(입력제한 데크)
- 입력이 한 쪽에서만 발생하고 출력은 양쪽에서 일어남
Shelf(출력제한 데크) - 입력은 양쪽에서 일어나고 출력은 한 쪽에서만 일어남
2. 비선형 구조
1. 트리
노드(Node) - 트리의 기본 구성 요소
근 노드(Root Node) - 가장 상위에 위치한 트리의 시작 노드
레벨(Level) - 근 노드를 기준으로 특정 노드까지의 경로 길이
조상 노드(Ancestors Node) - 특정 노드에서 루트에 이르는 경로상의 노드
자식 노드(Child Node) - 특정 노드에 연결된 다음 레벨의 노드
부모 노드(Parent Node) - 특정 노드에 연결된 이전 레벨의 노드
형제 노드(Sibling) - 같은 부모를 가진 노드
깊이(Depth) - 트리의 최대 레벨
차수(Degree) - 특정 노드에 연결된 자식의 수 = Attribute
트리의 차수 - 트리의 최대 차수
단말노드 - 트리의 제일 마지막에 위치한 노드
BAC(삼각형모양)
트리의 순회 방법
전위 순회(Pre-Order) A->B->C
중위 순회(In-Order) B->A->C
후위 순회(Post-Order) B->C->A
트리의 종류
- 이진 트리(Binary Tree)
- 차수가 2이하로 구성된 트리
최대 노드 수 = 2의n승 - 1
특정 레벨의 최대 노드수 = 2(n - 1)
- 완전 이진 트리(Complete Binary Tree)
- 마지막 레벨을 제외하고 모든 노드가 채워진 트리
- 중간에 노드가 비어있으면 안 된다.
- 포화 이진 트리(Full Binary Tree)
- 모든 레벨에서 모든 노드가 채워진 트리
- 편향 이진 트리(Skewed Binary Tree)
- 왼쪽이나 오른쪽으로 편향된 트리
- 균형 이진 트리( Binary Tree)
- 모든 노드의 왼쪽과 오른쪽 서브 트리 높이가 1 이상 차이가 나지 않는 트리
- 이진 탐색 트리(Binary Search Tree) (검색)
- 이진탐색의 효율적인 탐색 능력을 유지하면서, 빈번한 자료 입력과 삭제를 가능하게끔 고안된 트리
- AVL 트리
- 스스로 균형을 잡는 이진 탐색 트리
- 각 노토의 왼쪽 서브트리의 높이와 오른쪽 서브트리의 높이 차이가 1이하인 이진 탐색 트리
- 탐색 시간이 빠른 장점
- B - 트리
- 데이터베이스와 파일 시스템에서 널리 사용되는 트리
- 신장 트리
- 그래프에서 간선들이 사이클이 생기지 않도록 만든 트리
2. 그래프(Grapth)
그래프의 개념
G = (V, E) : 그래프 G는 2개의 집합 V와 E로 구성되어 있는 자료구조
- 정점(Vertex) : 노드들의 집합
- 간선(Edge) : 정점들 사이의 상호 연결의 집합
- 무방향 그래프(Undirected Graph)
- 간선을 표현하는 두 정점 사이의 순서가 없는 그래프
- n개의 정점으로 구성된 무방향 그래프의 최대 간선수는? (n(n-1))/2
- 방향 그래프(Directed Graph)
- 간선을 표현하는 두 정점 사이의 순서가 있는 그래프
- n개의 정점으로 구성된 방향 그래프의 최대 간선수는? n(n-1)
그래프의 표현 방법
- 인접 행렬(Adjacency Matrix)
- 그래프의 정점을 2차원 배열로 만든 것
- 인접 리스트(Adjacency List)
- 그래프의 각 정점에 인접한 정점들을 연결한 리스트(Linked List)로 표현하는 방법
그래프 순회 방법
- 깊이 우선 탐색(DFS, Depth First Search)
- 최대한 깊이 내려간 뒤, 더 이상 깊이 갈 곳이 없을 경우, 백트래킹하여 옆으로 이동
- 스택을 이용
- 너비 우선 탐색(BFS, Breath-First Search)
- 큐를 이용
안녕하세요!