정보처리기사 실기 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)