정보처리기사 실기 2장. 데이터 입출력 구현_9
2-29. 자료구조
| 선형 구조 (Linear Structure) |
배열 (Array) | |
| 선형 리스트 (Linear List) | 연속 리스트 (Contiguous List) | |
| 연결 리스트 (Linked List) | ||
| 스택 (Stack) | ||
| 큐 (Queue) | ||
| 데크 (Deque) | ||
| 비선형 구조 (Non-Linear Structure) |
트리 (Tree) | |
| 그래프 (Graph) |
• 배열 (Array)
크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합
‣ 반복적인 데이터 처리 작업에 적합
‣ 정적인 자료구조, 기억장소의 추가가 어려움
‣ 데이터 삭제 시 기억장소가 빈 공간으로 남아 메모리 낭비가 발생
• 연속 리스트 (Contiguous List)
연속되는 기억장소에 저장되는 자료구조
‣ 데이터 삽입 시 연속된 빈 공간 필요
‣ 삽입, 삭제 시 자료의 이동 필요
• 연결 리스트 (Linked List)
자료들을 임의의 기억공간에 기억시키되 노드의 포인터 부분을 이용해 서로 연결시킨 자료 구조
‣ 링크(포인터) 부분이 필요하기 때문에 이동 효율이 좋지 않음
‣ 접근 속도가 느리고, 연결이 끊어지면 다음 노드를 찾기 어려움
• 스택 (Stack)
리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
‣ 후입선출 방식 (LIFO; Last In First Out)
‣ 오버플로 (Overflow) : 저장할 기억 공간이 없는 상태에서 데이터가 삽입되는 경우
‣ 언더플로 (Underflow) : 삭제할 데이터가 없는 상태에서 데이터를 삭제하는 경우
• 큐 (Queue)
리스트의 한쪽에서는 삽입작업만 이루어지고, 다른 한쪽에서는 삭제 작업만 이루어지는 자료 구조
‣ 선입선출 방식 (FIFO; First In First Out)
‣ 시작 = Front 포인터, 끝 = Rear 포인터
• 그래프 (Graph)
정점(Vertex)과 간선(Edge)의 두 집합으로 이루어진 자료 구조
‣ 트리(Tree) : 사이클이 없는 그래프
‣ 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 나뉨
• 방향/무방향 그래프의 최대 간선 수
- 방향 그래프의 최대 간선 수 : n(n-1)
- 무방향 그래프의 최대 간선 수 : n(n-1)/2
- 정점의 개수 : n
2-30. 트리
• 트리
정점(Node, 노드)과 선분(Branch, 가지)을 이용해 사이클을 이루지 않도록 구성한 그래프의 특수 형태
• 트리 관련 용어
| 노드 (Node, 정점) | 트리의 기본 요소 |
| 근 노드 (Root Node) | 트리의 맨 위에 있는 노드 |
| 디그리 (Degree, 차수) | 각 노드에서 뻗어나온 가지의 수 |
| 단말노드 (Terminal Node) = 잎 노드 (Leaf Node) |
자식이 하나도 없는 노드 즉, 차수가 0인 노드 |
| 비단말 노드 (Non-Terminal Node) | 자식이 하나라도 있는 노드 즉, 차수가 0이 아닌 노드 |
| 조상 노드 (Ancestors Node) | 임의의 노드에서 근노드에 이르는 경로상에 있는 노드들 |
| 자식 노드 (Son Node) | 어떤 노드에 연결된 다음 레벨의 노드들 |
| 부모 노드 (Parent Node) | 어떤 노드에 연결된 이전 레벨의 노드들 |
| 형제 노드 (Brother Node, Sibling) | 동일한 부모를 갖는 노드들 |
| Level | 근 노드의 레벨을 1로 가정한 후, 어떤 레벨이 L이면 자식 노드는 L+1 |
| 깊이 (Depth, Height) | 트리에서 노드가 가질 수 있는 최대의 레벨 |
| 숲 (Forest) | 여러 개의 트리가 모여 있는 것 |
| 트리의 디그리 | 노드들의 디그리 중에서 가장 많은 수 |
| 링크 (Link) | 노드와 노드를 연결하는 선 |
2-31. 이진트리
• 이진 트리
차수(Degree)가 2 이하인 노드들로 구성된 트리
‣ 자식이 둘 이하인 노드들로만 구성된 트리
• 트리의 운행법
| Preorder 운행법 | Root → Left → Right | 예) 전위 표기법 (PreFix) |
| Inorder 운행법 | Left → Root → Right | 예) 중위 표기법 (InFix) |
| Postorder 운행법 | Left → Right → Root | 예) 후위 표기법 (PostFix) |
2-32. 정렬 (Sort)
• 삽입 정렬 (Insertion Sort)
이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
‣ 가장 간단한 정렬 방식
‣ 평균과 최악 모두 수행 시간 복잡도 : O(n^2)
• 선택 정렬 (Selection Sort)
반복적으로 최소값을 찾아 순서대로 레코드를 위치에 놓는 방식
‣ 평균과 최악 모두 수행 시간 복잡도 : O(n^2)
• 버블 정렬 (Bubble Sort)
인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
‣ 평균과 최악 모두 수행 시간 복잡도 : O(n^2)
• 쉘 정렬 (Shell Sort)
매개변수의 값으로 서브 파일을 구성하고 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식
‣ 삽입 정렬을 확장한 개념
‣ 평균 수행 시간 복잡도 : O(n^1.5)
‣ 최악 수행 시간 복잡도 : O(n^2)
• 퀵 정렬 (Quick Sort)
키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해 시키는 과정을 반복하는 정렬 방식
‣ 평균 수행 시간 복잡도 : O(nlog2n)
‣ 최악 수행 시간 복잡도 : O(n^2)
• 힙 정렬 (Heap Sort)
전이진 트리를 이용한 정렬 방식
‣ 전이진 트리를 힙 트리로 변환하여 정렬
‣ 평균과 최악 모두 수행 시간 복잡도 : O(nlog2n)
• 2-Way 합병 정렬 (Merge Sort)
이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
‣ 평균과 최악 모두 수행 시간 복잡도 : O(nlog2n)
• 기수 정렬 (Radix Sort = Bucket Sort)
Queue를 이용하여 자릿수(Difit)별로 정렬하는 방식
‣ 평균과 최악 모두 수행 시간 복잡도 : O(dn)