[정보처리기사] 실기 노트 - 데이터 입출력 구현 4

1. 자료구조
   1. 자료구조의 개요
      1. 자료 구조 (Data Structure): 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것
   2. 자료 구조의 분류
      1. 배열 (Array): 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합
      2. 선형리스트 (Linear List): 일정한 순서에 의해 나열된 구조
         1. 연속 리스트 (Contiguous List): 배열과 같이 연속되는 기억장소에 저장되는 자료 구조
         2. 연결 리스트 (Linked List): 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조
      3. 스택 (Stack): 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
      4. 큐 (Queue): 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조
      5. 데크 (Deque): 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조
      6. 그래프 (Graph): 정점 (Vertex)과 간선 (Edge)의 두 집합으로 이루어지는 자료 구조
      7. 트리 (Tree)
         1. 트리의 개념
            1. 정점 (Node, 노드)과 선분 (Branch, 가지)을 이용하여 사이클을 이루지 않도록 수정한 그래프 (Graph)의 특수한 형태
         2. 트리 관련 용어: 노드 (Node), 근 노드 (Root Node), 디그리 (Degree, 차수), 단말 노드 (Terminal Node) 또는 잎 노드 (Leaf Node), 비단말 노드 (Non-Terminal Node), 조상 노드 (Ancestors Node), 자식 노드 (Son Node), 부모 노드 (Parent Node), 형제 노드 (Brotheer Node, Sibling), 레벨 (Level), 깊이 (Depth, Height), 숲 (Forest), 트리의 디그리 (Degree)
2. 이진 트리의 개념과 운행법
   1. 이진트리의 개념
      1. 이진트리: 차수 (Degree)가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리
      2. 이진 트리의 레벨 i에서 최대 노드의 수: 2^(i - 1)
   2. 이진 트리의 운행법
      1. Preorder 운행법: 이진 트리를 Root->Left->Right 순으로 운행하며 노드들을 찾아가는 방법
      2. Inorder 운행법: 이진 트리를 Left->Root->Right  순으로 운행하며 노드들을 찾아가는 방법
      3. Postorder 운행법: 이진 트리를 Left->Right->Root 순으로 운행하며 노드들을 찾아가는 방법
   3. 수식의 표기법
      1. 수식의 표기법 개요
         1. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위 (Infix), 전위 (Prefix), 후위 (Postfix) 표기법이 됨
         2. Infix 표기를 Postfix나 Prefix로 바꾸기
         3. Postfix나 Prefix로 표기된 수식을 Infix로 바꾸기
3. 정렬의 개념과 정렬방식의 특징
   1. 정렬 (Sort)의 개념
      1. 정렬 (Sort): 2개 이상의 자료를 특정 기준에 의해 작은 값부터 큰 값 혹은 그 반대 순서로 재배열하는 것 (오름차순 (Ascending Order) 정렬 / 내림차순 (Descending order) 정렬)
   2. 정렬 방식의 주요 특징
      1. 삽입 정렬 (Insertion Sort): 가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식
      2. 선택 정렬 (Selection Sort): n 개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n - 1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식
      3. 버블 정렬 (Bubble Sort): 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식
      4. 쉘 정렬 (Shell Sort): 입력 파일을 어떤 매개변수 (h)의 값으로 서브 파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식 (보통 h^root)
      5. 퀵 정렬 (Quick Sort): 키를 기준으로 작은 값을 왼쪽에, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식
      6. 힙 정렬 (Heap Sort): 전이진 트리 (complete Binary Tree)를 이용한 정렬 방식
      7. 2-Way 합병 정렬 (Merge Sort): 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식
      8. 기수 정렬 (Radix Sort) 또는 버킷 (Bucket sort): 큐 (Queue)를 이용하여 자릿수 (Digit)별로 정렬하는 방식