[정보처리기사 필기] 2과목 - 자료구조

자료구조의 분류

• 선형 구조(Linear Structure)
  • 배열(Array)
  • 선형 리스트(Linear List)
    • 연속 리스트(Contiguous List)
    • 연결 리스트(Linked List)
  • 스택(Stack)
  • 큐(Queue)
  • 데큐(Deque)
• 비선형 구조(Non-Linear Structure)
  • 트리(Tree)
  • 그래프(Graph)

 

선형 리스트(Linear List)

연속 리스트(Contiguous List)

• 배열과 같이 연속되는 기억 저장소에 저장되는 자료 구조
• 기억 장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도 1로서 가장 좋음
• 연속 리스트는 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야하며, 삽입, 삭제 시 자료의 이동이 필요

연결 리스트(Linked List)

LinkedList

• 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조
• 노드의 삽입, 삭제 작업이 용이함
• 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있음
• 연결 리스트는 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않음
• 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느림
• 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듬

 

스택(Stack)

Stack

스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

• LIFO(Last In First Out) 방식으로 자료 처리
• 응용 분야
  • 함수 호출의 순서 제어
  • 인터럽트의 처리
  • 수식 계산 및 수식 표기법
  • 컴파일러를 이용한 언어 번역
  • 부 프로그램 호출 시 복귀 주소 저장
  • 서브루틴 호출 및 복귀 주소 저장
• 스택이 가득 차있는 상태에서 데이터가 삽입 되면 오버플로우(Overflow)가 발생, 더 이상 삭제할 데이터가 없는 상태에서 데이터 삭제 시 언더플로(Underflow) 발생

 

큐(Queue)

Queue

리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조

• FIFO(First In First Out) 방식으로 처리
• 시작과 끝을 표시하는 두 개의 포인터가 있음

 

그래프(Graph)

Direct, Undirect Graph

정점과 간선으로 구성된 자료구조

• 방향이 있는 그래프(Direct)와 없는 그래프(Undirect)로 나뉨
• 최대 간선 수를 구하는 공식
  • Direct 그래프 - n(n-1)
  • Undirect 그래프 - n(n-1)/2

 

트리(Tree)

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

 

• 노드(Node) - 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것
  • ex. A, B, C, D, E, F, G, H, I, J, K, L, M
• 루트 노드(Root Node) - 트리의 맨 위에 있는 노드
  • ex. A
• 차수(Degree) - 각 노드에서 뻗어 나온 가지의 수
  • ex. A = 3, B = 2, C = 1, D = 3
• 단말 노드(Terminal Node) - 어떤 노드에 연결된 다음 레벨의 노드
  • ex. K, L, F, G, M, I, J
• 자식 노드(Son Node) - 더떤 노드에 연결된 다음 레벨의 노드
  • ex. D의 자식 노드 : H, I, J
• 부모 노드(Parent Node) - 어떤 노드에 연결된 이전 레벨의 노드
  • ex. E, F의 부모 노드 : B
• 형제 노드(Brother Node, Sibling) - 동일한 부모를 갖는 노드들
  
  • ex. H의 형제 노드 : I, J
• 트리의 디그리 - 노드들의 디그리 중 가장 많은 수
  • ex. 위 그림의 디그리는 3

트리의 순환

• Preorder - Root -> Left -> Right 순으로 순환
  
  • A13
  • 1 -> AB2E3
  • 2 -> ABDHIE3
  • 3 -> ABDHIECFG
• Inorder - Left -> Root -> Right 순으로 순환
  • 1A3
  • 1 -> 2BEA3
  • 2 -> HDIBEA3
  • 3 -> HDIBEAFCG
• Postorder - Left -> Right -> Root 순으로 순환
  • 13A
  • 1 -> 2EB3A
  • 2 -> HIDEB3A
  • 3 -> HIDEBFGCA

 

수식의 표기법

전위 표기법(PreFix) : 연산자 -> Left -> Right

• ex. +AB

중위 표기법(InFix) : Left -> 연산자 -> Right 

• ex. A+B

후위 표기법(PostFix) : Left -> Right -> 연산자

• ex. AB+

전위나 후위 표기법은 Stack을 이용하여 처리하므로 중위 표기법은 전위나 후위 표기법으로 바꾸어 처리함

Ex1. "X = A / B * (C + D) + E" InFix로 표기된 수식을 다음 표기법으로 변경

Prefix

• 연산자 우선 순위에 따라 괄호로 묶고 연산자들을 해당 괄호 앞으로(왼쪽) 이동
  • (X = (((A / B) * (C + D)) + E))
  • =(X + (*(/(A  B) +(C  D))  E))
• 괄호를 제거
  • = X + * / A  B + C  D  E 

=

X

+

*

/

A

B

+

C

D

E

Postfix

• 연산 우선순위에 따라 괄호로 묶고 연산자들을 해당 괄호 뒤로(오른쪽) 옮김
  • (X = (((A / B) * (C + D)) + E))
  • ( X ( ( (A B) / (C D) + ) * E ) + ) =
• 괄호를 제거
  • X A B / C D + * E + =

X

A

B

/

C

D

+

*

E

+

=

 

Ex2. "A B C - / D E F + * +" PostFix로 표기된 수식을 InFix으로 변경

• 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶고 연산자를 피연산자들의 가운데로 이동
  • ( ( A (B C -) / ) ( D ( E F + ) * ) + )
  • ((A / (B - C)) + (D * (E + F)))
• 괄호 제거
  • A / (B - C) + D * (E + F)

 

Ex3. "+ / A - B C * D + E F" PreFix로 표기된 수식을 InFix으로 변경

• 인접한 피연산자 두 개와 왼쪽의 연산자를 괄호로 묶고 연산자를 피연산자들의 가운데로 이동
  • (+ ( / A (-B C) ) (* D (+ E F ) ) )
  • ((A / (B - C)) + (D * (E + F ) ) )
• 괄호 제거
  • A / (B - C) + D * (E + F)