[정보처리산업기사 필기] 데이터베이스 활용(3과목)

데이터베이스 활용

 

자료 구조의 분류

 

• 선형 구조 : 배열, 선형 리스트, 스택, 큐, 테크
• 비선형 구조 : 트리, 그래프

 

스택(Stack)

 

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료구조입니다.
• 가장 나중에 삽입됩 자료가 가장 먼저 삭제되는 후입선출(LIFO)방식으로 자료를 처리한다.

 

스택의 응용 분야

 

• 함수 호출의 순서 제어
• 인터럽트의 처리
• 수식 계산 및 수식 표기법
• 컴파일러를 이용한 언어 번역
• 부 프로그램 호출 시 복귀주소 저장
• 서브루틴 호출 및 복귀 주소 저장

스택의 삽입(Push)과 삭제(Pop)

 

• PUSH : 스택에 자료를 입력하는 명령
• POP : 스택에서 자료를 출력하는 명령

예제 : 순서가 A, B, C, D로 정해진 입력 자료를 스택에 입력하였다가 B, C, D, A순서로 출력하는 과정을 나열하시오.
Push : A	Push : B	Pop : B	Push : C	Pop : C	Push : D	Pop : D	Pop : A

 

큐(Queue)

 

• 리스트의 한쪽에서만 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지는 자료 구조입니다.
• 가장 먼저 사입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리한다.

 

데크(Deque)

 

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조입니다.
• 입력 제한 : 입력은 한쪽에서만 일어나고, 출력은 양쪽에서 일어남.
• 출력 제한 : 입력은 양쪽에서 일어나고, 출력은 한쪽에서만 일어남.

 

방향/무방향 그래프의 최대 간선 수

 

• 무방향 그래프의 최대 간선 수 : n(n-1)/2
• 방향 그래프의 최대 간선 수 : n(n-1)

트리(Tree)

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

노드(node)	트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친것.
디그리(Degree, 차수)	각 노드에서 뻗어 나온 가지의 수
단말 노드(Terminal Node) = 잎 노드(Leaf Node)	자식이 하나도 없는 노드, 즉, 디그리가 0인 노드

 

 

이진 트리의 운행법

다음 트리를 Inorder, Preorder, Postorder 방법으로 운행했을 때 각  노드를 방문한 순서는?

Preorder 운행법의 방문 순서

 

• Preorder는 Root -> Left -> Right이므로 A13이 됩니다.
• 1은 B2E이므로 AB2E3
• 2는 DHI이므로 ABDHIE3
• 3은 CFG이므로 ABDHIECFG가 됩니다.
• 방문 순서 : ABDHIECFG

 

Inorder 운행법의 방문 순서

 

• Inorder는 Left -> Root -> Right 이므로 1A3이 됩니다.
• 1은 2BE이므로 2BEA3이 되고,
• 2는 HDI이므로 HDIBEA3이 되고,
• 3은 FCG이므로 HDIBEAFCG가 됩니다.
• 방문 순서 : HDIBEAFCG

 

Postorder 운행법의 방문 순서

 

• Postorder는 Left -> Right -> Root 이므로 13A가 됩니다.
• 1은 2EB이므로 2EB3A가 됩니다.
• 2는 HID이므로 HIDEB3A가 되고,
• 3은 FGC이므로 HIDEBFGCA가 됩니다.
• 방문 순서 : HIDEBFGCA