정보처리기사 - 데이터 입출력 구현 #61~63

61. 트리(Tree)

61.1 트리(Tree)

정점(Node, 노드)과 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태

• 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 함

61.2 트리 관련 용어

• 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
  • 예) A, B, C, D, E, F, G, H, I, J, K ,L ,M
• 근 노드(Root Node) : 트리의 맨 위에 있는 노드
  • 예) A
• 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
  • 예) A=3, B=2, C=1, D=3
• 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 즉 Degree가 0인 노드
  • 예) K, L, F, G, M, I, J
• 비단말 노드(Non-Terminal Node) : 자식이 하나라도 있는 노드, 즉 Degree가 0이 아닌 노드
  • 예) A, B, C, D, E, H
• 조상 노드(Ancestors Node) : 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들
  • 예) M의 조상 노드는 H, D, A
• 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
  • 예) D의 자식 노드는 H, I, J
• 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
  • 예) E, F의 부모 노드는 B
• 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들
  • 예) H의 형제 노드는 I, J
• Level : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식 노드는 L+1
  • 예) H의 레벨은 3
• 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대 레벨
  • 예) 위 트리의 깊이는 4
• 숲(Forest) : 여러 개의 트리가 모여 있는 것
  • 예) 위 트리에서 근 노드 A를 제거하면 B, C, D를 근 노드로 하는 세 개의 트리가 있는 숲이 생성
• 트리의 디그리 : 노드들의 Degree 중에서 가장 많은 수
  • 예) 노드 A나 D가 세 개의 Degree를 가지므로 위 트리의 Degree는 3

---

62. 이진 트리(Tree)

62.1 이진 트리(Tree)

차수(Degree)가 2 이하인 노드들로 구성된 트리, 즉 자식이 둘 이하인 노드들로만 구성된 트리

• 이진 트리의 레벨i에서 최대 노드의 수는 2^i-1
• 이진 트리에서 Terminal Node의 수가 n₀, 차수가 2인 노드 수가 n₂라고 할 때 n₀ = n₂+1이 됨

• 예) 레벨 3에서 최대 노드의 개수는 2^3-1 = 4
• Terminal Node의 개수가 4개이고, 차수가 2인 노드가 3개이므로 4 = 3+1에 의해 n₀ = n₂+1이 성립됨

62.2 트리의 운행법(Traversal)

트리를 구성하는 각 노드들을 찾아가는 방법

• 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 가짐
• 이진 트리의 운행법은 다음 세 가지가 존재

• Preorder 운행 : Root→Left→Right 순으로 운행 (A, B, C)
  • 루트가 앞(Pre)에 위치
• Inorder 운행 : Left→Root→Right 순으로 운행 (B, A, C)
  • 루트가 안(In)에 위치
• Postorder 운행 : Left→Right→Root 순으로 운행 (B, C, A)
  • 루트가 뒤(Post)에 위치

62.3 Preorder 운행법

이진 트리를 Root→Left→Right 순으로 운행하며 노드들을 찾아가는 방법

• Preorder 운행법의 방문 순서
  • 서브트리를 하나의 노드로 생각할 수 있도록 그림과 같이 서브트리 단위로 묶음

1. Preorder는 Root→Left→Right이므로 A, 1, 3이 됨
2. 1은 B, 2, E이므로 A, B, 2, E, 3이 됨
3. 2는 D, H, I이므로 A, B, D, H, I, E, 3이 됨
4. 3은 C, F, G이므로 A, B, D, H, I, E, C, F, G가 됨

• 방문 순서 : A, B, D, H, I, E, C, F, G

62.4 Inorder 운행법

이진 트리를 Left→Root→Right 순으로 운행하며 노드들을 찾아가는 방법

• Inorder 운행법의 방문 순서

1. Inorder는 Left→Root→Right이므로 1, A, 3이 됨
2. 1은 2, B, E이므로 2, B, E, A, 3이 됨
3. 2는 H, D, I이므로 H, D, I, B, E, A, 3이 됨
4. 3은 F, C, G이므로 H, D, I, B, E, A, F, C, G가 됨

• 방문 순서 : H, D, I, B, E, A, F, C, G

62.5 Postorder 운행법

이진 트리를 Left→Right→Root 순으로 운행하며 노드들을 찾아가는 방법

• Postorder 운행법의 방문 순서

1. Inorder는 Left→Right→Root이므로 1, 3, A가 됨
2. 1은 2, E, B이므로 2, E, B, 3, A가 됨
3. 2는 H, I, D이므로 H, I, D, E, B, 3, A가 됨
4. 3은 F, G, C이므로 H, I, D, E, B, F, G, C, A가 됨

• 방문 순서 : H, I, D, E, B, F, G, C, A

62.6 수식의 표기법

이진 트리로 만들어진 수식을 Preorder, Inorder, Postorder로 운행하면 각각 전위(Prefix), 중위(Infix), 후위(Postfix) 표기법이 됨

• 전위 표기법(Prefix) : 연산자→Left→Right (+, A, B)
• 중위 표기법(Infix) : Left→연산자→Right (A, +, B)
• 후위 표기법(Postfix) : Left→Right→연산자 (A, B, +)

62.6.1 Infix 표기를 Postfix나 Prefix로 바꾸기

Postfix나 Prefix는 스택을 이용하여 처리하므로 Infix는 Postfix나 Prefix로 바꾸어 처리

• 예제 : 다음과 같이 Infix로 표기된 수식을 Prefix와 Postfix로 변환하라

• Prefix로 변환하기

1. 연산 우선순위에 따라 괄호로 묶음

2. 연산자를 해당 괄호의 앞(왼쪽)으로 옮김

3. 필요 없는 괄호를 제거

• Postfix로 변환하기

1. 연산 우선순위에 따라 괄호로 묶음

2. 연산자를 해당 괄호의 뒤(오른쪽)으로 옮김

3. 필요 없는 괄호를 제거

62.6.2 Postfix나 Prefix로 표기된 수식을 Infix로 바꾸기

• 예제 : 다음과 같이 Postfix로 표기된 수식을 Infix로 변환하라
  • Postfix는 Infix 표기법에서 연산자를 해당 피연산자 두 개의 뒤로 이동한 것이므로 연산자를 다시 해당 피연산자 두 개의 가운데로 옮기면 됨

1. 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶음

2. 연산자를 해당 피연산자의 가운데로 이동

3. 필요 없는 괄호를 제거

• 예제 : 다음과 같이 Prefix로 표기된 수식을 Infix로 변환하라
  • Prefix는 Infix 표기법에서 연산자를 해당 피연산자 두 개의 앞으로 이동한 것이므로 연산자를 다시 해당 피연산자 두 개의 가운데로 옮기면 됨

1. 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶음

2. 연산자를 해당 피연산자 사이로 이동

3. 필요 없는 괄호를 제거

---

63. 정렬(Sort)

63.1 삽입 정렬(Insertion Sort)

가장 간단한 정렬 방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬하는 방식

• 평균/최악 수행 시간 복잡도 : O(n²)
• 예제 : 8, 5, 6, 2, 4를 삽입 정렬로 정렬하라

1. 초기 상태

2. 1회전 : 두 번째 값을 첫 번째 값과 비교하여 5를 첫 번째 자리에 삽입하고 8을 한 칸 뒤로 이동

3. 2회전 : 세 번째 값을 첫 번째, 두 번째 값과 비교하여 6을 8 자리에 삽입하고 8은 한칸 뒤로 이동

4. 3회전 : 네 번째 값 2를 처음부터 비교하여 맨 처음에 삽입하고 나머지를 한 칸씩 뒤로 이동

5. 4회전 : 다섯 번째 값 4를 처음부터 비교하여 5 자리에 삽입하고 나머지를 한 칸씩 뒤로 이동

63.2 선택 정렬(Selection Sort)

n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두 번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식

• 평균/최악 수행 시간 복잡도 : O(n²)
• 예제 : 8, 5, 6, 2, 4를 선택 정렬로 정렬하라

1. 초기 상태

2. 1회전

3. 2회전

4. 3회전

5. 4회전

63.3 버블 정렬(Bubble Sort)

주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

• 평균/최악 수행 시간 복잡도 : O(n²)
• 예제 : 8, 5, 6, 2, 4를 버블 정렬로 정렬하라

1. 초기 상태

2. 1회전

3. 2회전

4. 3회전

5. 4회전

63.4 쉘 정렬(Shell Sort)

입력 파일을 어떤 매개변수의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식

• 삽입 정렬(Insertion Sort)을 확장한 개념
• 평균 수행 시간 복잡도 : O(n^1.5)
• 최악 수행 시간 복잡도 : O(n²)

63.5 퀵 정렬(Quick Sort)

키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 과정을 반복하는 정렬 방식

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
• 평균 수행 시간 복잡도 : O(nlog₂n)
• 최악 수행 시간 복잡도 : O(n²)

63.6 힙 정렬(Heap Sort)

전이진 트리를 이용한 정렬 방식

• 구성된 전이진 트리(Complete Binary Tree)를 Heap Tree로 변환하여 정렬
• 평균/최악 수행 시간 복잡도 : O(nlog₂n)

63.7 2-Way 합병 정렬(Merge Sort)

이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

• 평균/최악 수행 시간 복잡도 : O(nlog₂n)

63.8 기수 정렬(Radix Sort) = Bucket Sort

Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식

• 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 버킷의 순서대로 레코드를 꺼내어 정렬
• 평균/최악 수행 시간 복잡도 : O(dn)