[정처기 필기] 「2」 | 데이터 입 / 출력 구현 - (1.1) 자료구조, 트리

[정처기 필기] 「2」 | 데이터 입 / 출력 구현 - (1.1) 자료구조, 트리

「1」 소프트웨어 설계

> 「2」 소프트웨어 개발

- > 데이터 입 / 출력 구현, 통합 구현, 제품 소프트웨어 패키징, 애플리케이션 테스트 관리, 인터페이스 구현

「3」 데이터베이스 구축

「4」  프로그래밍 언어 활용

「5」  정보시스템 구축 관리

 

> 1 자료구조

> 2 트리(Tree)

3 정렬(Sort)

4 검색 - 이분 검색 / 해싱

5 데이터베이스 개요

6 절차형 SQL

1. 자료구조

자료 구조의 정의

  

프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법, 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등 연구 분석하는 것

 

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

 

배열(Array)

 

동일한 자료형의 데이터들이 같은 크기로 나열, 순서 가지고 있는 집합

 

- 정적인 자료 구조, 기억장소의 추가 어렵고, 삭제 시 빈 공간으로 남아있어, 메모리 낭비 발생

- 첨자를 이용하여 데이터에 접근

- 반복적인 데이터 처리 작업에 적합

- 데이터마다 동일한 이름의 변수 사용하여 처리가 간편

- 사용한 첨자의 수에 따라 n차열 배열이라 부름

 

선형 리스트(Linear List)

 

일정한 순서에 의해 나열된 자료구조

 

- 빈 공간 없이 데이터 저장

- 배열을 이용하는 연속 리스트(Contiguous List)와 포인터를 이용하는 연결 리스트(Linked List)로 구분

 

연속 리스트(Contiguous List)

: 배열과 같이 연속되는 기억장소에 저장

: 기억장소를 연속적으로 배정받기 때문에, 기억장소 이용 효율은 밀도가 1로 가장 좋음

: 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입 / 삭제 시 자료의 이동 필요

 

연결 리스트(Linked List)

: 자료들을 연속 배열하지 않고, 임의의 기억공간에 기억시키고 차례로 노드의 포인터를 이용하여 서로 연결

: 노드의 삽입 / 삭제 작업 용이

: 기억 공간이 연속적으로 놓여 있지 않아도 저장 가능

: 포인터 부분이 필요하기 때문에 추가공간이 필요, 연속 리스트에 비해 기억 공간의 이용 효율이 떨어짐

: 연결을 위한 포인터 찾는 시간이 필요, 접근 속도가 느림

: 중간 노드 연결이 끊어지면, 다음 노드 찾기 힘듦

 

스택(Stack)

 

리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이뤄짐

 

- 후입선출(LIFO; Last In First Out) 방식

- 함수 호출의 순서 제어, 인터럽트 처리, 수식 계산, 수식 표기법, 컴파일러 이용한 언어 번역, 부 프로그램 호출 시 복귀 주소, 재귀함수 호출, 후위 표현의 연산, 깊이 우선 탐색 등 왔던 길을 되돌아가는 방식에 사용

- 오버플로(Overflow) : 모든 기억 공간이 채워져 있는 상태에서 삽입

- 언더플로(Underflow) : 삭제할 데이터가 없는 상황에서 삭제

- TOP : 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소

- Bottom : 스택의 가장 밑바닥

- PUSH, POP : 마지막에서 삽입, 삭제

- TOP Pointer 값이 스택의 크기보다 커지면 Overflow 발생

- TOP Pointer 주소가 0이면 Underflow 발생

 

큐(Queue)

 

리스트의 한쪽에서는 삽입, 다른 한 쪽에서 삭제

 

- 선입선출(FIFO; First In First Out) 방식

- 시작과 끝을 표시하는 두 개의 포인터

- 프런트 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터, 삭제 작업

- 리어 포인터 : 가장 마지막에 삽입된 자료가 위치의 기억공간을 가리키는 포인터, 삽입 작업

- 운영체제의 작업 스케줄링에 사용

 

데크(Deque)

 

삽입, 삭제가 양끝 모두에서 발생

 

- Stack과 Queue의 장점만 따서 구성

- 입력 제한 : 입력이 한쪽에서만 발생, 출력은 양쪽에서 발생, Scroll

- 출력 제한 : 출력이 한쪽에서만 발생, 입력은 양쪽에서 발생, Shelf

 

그래프(Graph)

 

정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이뤄짐

 

- 방향성 유무에 따라 방향 그래프, 무방향 그래프

- 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분해법 등 응용

- 트리(Tree)는 사이클이 없는 그래프

 

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

 

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

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

2. 트리(Tree)

트리의 개요

 

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

 

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

- 가족의 계보, 조직도 등 표현

 

A  ↙        ↓        ↘ ↙                   ↓                  ↘  ↙                             ↓                           ↘							Level 1
↙                B  ↙   ↘			↓  C  ↓	↘                              D  ↙    ↓    ↘			Level 2
↙  E  ↙   ↘		↘                   F	↓  G	↙  H	↓  I	↘                 J	Level 3
↙  K	↘             L						Level 4 = Depth

 

트리 관련 용어

- 노드(Node) : 트리의 기본 요소, 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

> A, B, C, D, R, F, G, H, I, J, K, L, M

- 근 노드(Root Node) : 트리의 맨 위에 있는 뿌리 노드

> A

- 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지 수

> A = 3, B = 2, C = 1, D = 3

- 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식이 하나도 없는 노드, 디그리 0

> K, L, F, G, M, I, J

- 자식 노드(Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들

> D의 자식 노드 : H, I, J

- 부모 노드(Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들

> E, F의 부모 노드 : B

- 형제 노드(Brother Node, Sibling) : 동일한 부모를 갖는 노드들

> H의 형제 노드 : I, J

- 트리의 디그리 : 노드들의 디그리 중 가장 많은 수

> A나 D가 3개의 디그리를 가지므로 3

 

트리의 운행법

 

각 노드들을 찾아가는 방법을 운행법(Traversal)이라 함

 

- 이진트리를 운행하는 방법은 산술식 표기법과 연관성

- 이진트리의 운행법은 3가지가 있다

: Preorder 운행 = Root > Left > Right

: Inorder 운행 = Left > Root > Right

: Postorder 운행 = Left > Right > Root

 

수식의 표기법

 

산술식을 계산하기 위해 기억 공간에 기억시키는 방법, 이진 트리 사용

 

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

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

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

 

ex) X = A / B * (C + D) + E

 

PreFix

> =X+*/AB+CDE

PostFix

> XAB/CD+*E+=

 

 

 

 

 

 

 

출처 | <시나공> 정보처리기사 필기 2024 기본서 (길벗알앤디)