02. 데이터 입 · 출력 구현 | 자료 구조, 정렬(Sort)

 

 

060. 자료 구조

- 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

1) 선형 구조(Linear Structure)
- 배열(Array)
     : 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합

- 연속 리스트(Contiguous List)
     : 연속되는 기억장소에 저장되는 자료 구조(데이터 삽입을 위해서는 연속된 빈 공간이 있어야 함)

- 연결 리스트(Linked List)
     : 자료들을 임의의 기억공간에 기억시키되, 노드의 포인터 부분을 이용하여 서로를 연결시킨 구조

- 스택(Stack)
     : 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조(LIFO)

- 큐(Queue)
     : 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 구조(FIFO)

- 데크(Deque)
     : 양쪽에서삽입,삭제가능

 

2) 비선형 구조(Non-Linear Structure)

- 그래프(Graph)
     : 정점(Vertex)와 간선(Edge)의 두 집합으로 이루어지는 자료 구조 

     : 사이클이 없는 그래프를 트리(Tree)라고 함
     : 방향 그래프의 최대 간선 수 = n(n-1)
     : 무방향 그래프의 최대 간선 수 = n(n-1)/2

 

- 트리(Tree)
     : 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태 

 

     : 노드(Node)
          - 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것 

 

     : 근 노드(Root Node)
          - 트리의 맨 위에 있는 노드

 

     : 디그리(Degree, 차수)
          - 각 노드에서 뻗어나온 가지의 수

     : 단말 노드(Terminal Node) = 잎 노드(Leaf Node)

          - 자식이 하나도 없는 노드, 즉 Degree가 0인 노드 

 

     : 비단말 노드(Non-Terminal Node)

          - 자식이 하나라도 있는 노드 

 

     : 조상 노드(Ancestors Node)

          - 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들 

 

     : 자식 노드(Son Node)

          - 어떤 노드에 연결된 다음 레벨의 노드들 

 

     : 부모 노드(Parent Node)

          - 어떤 노드에 연결된 이전 레벨의 노드들 

 

     : 형제 노드(Brother Node, Sibling)
          - 동일한 부모를 갖는 노드들 

반응형

     : Level
     : 깊이(Depth, Height)
          - Tree에서 노드가 가질 수 있는 최대의 레벨

     : 숲(Forest)
          - 여러 개의 트리가 모여 있는 것

     : 트리의 디그리
          - 노드들의 디그리 중에서 가장 많은 수

     : 이진 트리
          - 차수(Degree)가 2 이하의 노드들로 구성된 트리 

          - 트리의 운행법
               : Preorder 운행         - Root -> Left -> Right

               : Inorder 운행            - Left -> Root -> Right 
               : Postorder 운행        - Left -> Right -> Root
          - 수식의 표기법
               : 전위 표기법(PreFix)          - 연산자 -> Left -> Right, +AB 
               : 중위 표기법(InFix)             - Left -> 연산자 -> Right, A+B 
               : 후위 표기법(PostFix)        - Left -> Right -> 연산자, AB+

 

 

 

063. 정렬(Sort)

1) 삽입 정렬(Insertion Sort)

- 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

2) 선택 정렬(Selection Sort)
- 최솟값을 찾아 첫 번째 레코드 위치에 놓고, 다시 최솟값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복

3) 버블 정렬(Burbble Sort)
- 인접한 두 개의 레코드 키값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

4) 쉘 정렬(Shell Sort)
- 매개변수의 값으로 서브 파일을 구성하고, 각 서브 파일을 Insertion 정렬 방식으로 순서 배열

5) 퀵 정렬(Quick Sort)
- 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 정렬 방식

 

6) 힙 정렬(Heap Sort)
- 전이진 트리를 이용한 정렬 방식

7) 2-Way 합병 정렬(Merge Sort)
- 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

8) 기수 정렬(Radix Sort) = Bucket Sort
- Queue를 이용하여 자릿수(Dight)별로 정렬하는 방식