[정보처리기사][데이터 입출력 구현] 자료구조

자료구조

자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리등을 효율적으로 하기 위한 자료의 형태를 말한다.

 

1. 대표적인 자료구조 분류

• 선형 구조 - 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) 방식의 자료구조

입구와 출구가 하나인 자료구조 (상자에 책을 쌓는 것과 같은 느낌)

• 저장할 기억 공간이 없는 상태에서 데이터가 삽입되면 오버플로가 발생한다.
• 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생한다.

큐 - Queue

선입선출(FIFO - First In First Out)방식의 자료구조

리스트 한쪽에서는 삽입작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 구조 (대형 마트 계산대와 같은 느낌)

• 시작을 표시하는 프런트포인터와 끝을 표시하는 리어포인터가 있다.

그래프 - Graph

정점(Vertex)과 간선(Edge)의 두 집합으로 이루어지는 자료 구조

• 사이클이 없는 그래프를 트리라고 한다.
• 간선의 방향성 유무에 따라 방향 그래프, 무방향 그래프로 구분된다.

양방향 그래프

무방향 그래프

1. 그래프의 최대 간선 수

무방향 그래프 : n(n-1)/2

양방향 그래프 : n(n-1)

n : 정점의 개수

 

 

트리 - Tree

사이클을 이루지 않도록 구성한 그래프의 특수한 형태의 자료구조

정점(Node)과 선분(Branch)으로 구성되어 있다.

 

1. 관련용어 

• 노드(Node) - 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것
• 근 노드(Root Node) - 트리의 최 상단에 있는 노드
• 디그리 또는 차수 (Degree) - 각 노드에서 뻗어 나온 가지의 수
• 단말(Terminal) 노드 또는 잎(Leaf) 노드 - 자식이 하나도 없는 노드 (차수가 0인 노드)
• 비단말 노드 - 자식이 하나라도 있는 노드
• 조상(Ancestors) 노드 - 임의의 노드를 기준으로 근 노드에 이르는 경로상에 있는 노드들
• 자식(Son) 노드 - 임의의 노드를 기준으로 연결된 다음 레벨의 노드들
• 부모(Parent) 노드 - 임의의 노드를 기준으로 연결된 이전 레벨의 노드들
• 형제(Brother) 노드 - 동일한 무도를 갖는 노드들
• 레벨(Level) - 근 노드가 Level 1이며 그다음 자식 노드들을 +1
• 깊이(Depth) - 트리에서 노드가 가질 수 있는 최대의 레벨
• 숲(Forest) - 여러 개의 트리가 모여있는 것
• 트리의 디그리 - 노드들의 디그리 중 최대 디그리 수

2. 이진트리

차수가 2 이하인 노드들로 구성된 트리

• 자식이 둘 이하인 노드들로만 구성되어 있다.
• 이진트리의 레벨 i에서 최대 노드의 수는 2^i-1이다.

2.1 이진 트리의 운행법

각 노드들을 찾아가는 방법을 운행법이라 한다.

• Preorder - Root → Left → Right
• Inorder - Left → Root → Right
• Postorder - Left → Right → Root

2.1.1 Preorder 운행법

Root를 기준으로 좌측부터 우측순으로 운행하는 방법이다.

2.1.2 Inorder 운행법

가장 좌측 노드를 기준으로 Root 우측 순으로 운행하는 방법이다.

2.1.3 Postorder 운행법

가장 좌측 노드를 기준으로 우측 Root 순으로 운행하는 방법이다.

2.2 수식의 표기법

이진트리로 만들어진 수식을 Preorder, Postorder, Inorder순으로 Prefix, Postfix, Infix표기법을 사용한다.

 

• Prefix(전위 표기법) - 연산자가 앞으로 온다.
• Postifx(후위 표기법) - 연산자가 뒤로 온다.
• Infix(중위 표기법) - 연산자가 가운데로 온다.

2.2.1 표기법 변환하기

• Infix to Prefix - 예) X=A/B*(C+D)+E
• 연산순위대로 괄호를 추가한다
  • (X=(((A/B)*(C+D))+E))
• 연장자를 각 괄호 앞으로 옮긴다.
  • = (X+(*(/(AB)+(CD))E))
• 괄호를 제거한다
  • • = X+*/AB+CDE

• Infix to Postfix - 예) X=A/B*(C+D)+E
• 연산순위대로 괄호를 추가한다
  • (X=(((A/B)*(C+D))+E))
• 연잔자를 각 괄호 뒤로 옮긴다.
  • (X(((AB)/(CD)+)*E)+)=
• 괄호를 제거한다.
  • XAB/CD+*E+=
• Postfix to Infix - 예) XAB/CD+*E+=
• 인접한 피연산자 두 개와 오른쪽 연산자를 괄호로 묶는다.
  • (X(((AB/)(CD+)*) E+)=)
• 연산자를 피 연산자의 가운데로 이동시킨다
  •  (X=(((A/B)*(C+D))+E))
• 괄호를 제거한다.
  • X=A/B*(C+D)+E

• Prefix to Infix - 예) =X+*/AB+CDE

• 인접한 피연산자 두 개와 왼쪽 연산자를 괄호로 묶는다.
  • (=X(+(*(/AB)(+CD))E)
• 연산자를 피 연산자의 가운데로 이동시킨다
  •  (X=(((A/B)*(C+D))+E)
•  괄호를 제거한다.
  • X=A/B*(C+D)+E