2-1 데이터 입출력 구현 - 자료 표현 단위와 진법

자료 표현 단위와 진법

 

1. 자료 표현

 

자료 표현 방식

비트(Binary Digit)	컴퓨터 자료 표현 최소 단위로 하나의 2진수 값(0 또는 1)
니블(Nibble)	4개의 비트
바이트(Byte)	8개의 비트 또는 2개의 니블. 문자 표현의 최소 단위로 한글, 특수문자, 한자는 2바이트 필요(256개 정보 표현)
워드(word)	컴퓨터에서 한번에 처리될 수 있는 데이터의 양
필드(Field)	몇개의 워드가 모여 구성되는 정보 표현의 최소 단위. 항목(item)
레코드(Record)	하나 이상의 필드가 모여 구성되는 자료 처리의 기본 단위. 튜플(Tuple)
블록(Block)	여러 개의 논리 레코드가 모여 물리 레코드 구성. 실제 저장 매체에서 한번에 읽어 올수 있는 물리적 크기로 입출력 시 기본 단위
파일(File)	서로 관련 있는 레코드의 모임으로 컴퓨터에 저장하는 기본 단위
데이터 페이스(Database)	서로 관련성 있는 파일들의 집합으로 중복을 제거한 집합체

 

 

 

2. 2,8,16진수 10진수로 변환

 

 

 

 

 

고정 소수점과 부동 소수점

 

1. 고정 소수점(정수)

http://www.tcpschool.com/lectures/img_c_fixed_point.png

 

 

 

2. 부동 소수점(실수)

http://www.tcpschool.com/lectures/img_c_floating_point_32.png

 

 

 

3.  자료형 변환 시 확장과 축소

 

확장(Widening)	정수형을 실수형으로 변환 시 정보의 손실 없음
축소(Narrowing)	실수형을 정수형으로 변환 시 정보의 손실 있음

 

 

 

4. 기억 장치 용량

 

저장 용량 단위

 

속도 및 길이 나타내는 단위

 

 

 

 

자료 구조

 

1. 자료 구조

 

• 프로그램에서 쉽게 사용될 수 있도록 구성된 데이터 간의 논리적인 관계

 

데이터 형에 따른 자료 구조 분류

단순 구조(simple)	Int(정수형) Float(실수형) Double(배정도 실수형) Char(문자형)
선형 구조(liner)	스택(Stack) 큐(Queue) 데크(Deque) 선형 리스트(Linear List) 연결 리스트(Linked List)
비선형 구조(Non Liner)	트리(Tree) 그래프(Graph)
파일 구조(File)	순차 파일 색인 파일

 

 

 

2. 선형 구조

 

스택(Stack)	데이터 삽입과 삭제가 같은 쪽에서 이루어져 최근 데이터가 먼저 출력되는 메모리 사용법 가장 나중에 삽입된 데이터가 가장 먼저 삭제되어 후입 선출(LIFO: Last-In First-Out) 구조 더 이상 삭제할 데이터 없는 상태에서 데이터 삭제 시 언더플로(underflow) 발생 사용 예 함수 호출하여 복귀 시 깊이 우선 탐색(DFS) 재귀적(REcurision) 함수 호출 사용 시 인터럽트 수행 시 현재 수행중인 프로세스 복귀 주소 저장할 때 수식 우선 연산할 때(후위표현 postfix expression 연산) 0-주소 명령어 방법
큐(Queue)	한쪽 방향으로 데이터 삽입되고 반대 방향으로 데이터 삭제되는 데이터 구조 가장 먼저 삽입된 데이터가 가장 먼저 삭제되어 선입 선출(FIFO: First-in First-out) 구조 사용 예 프린터 스풀(Spool)/입출력 버퍼(Buffer) 은행 번호표 서비스 각종 스케줄링, 동영상 버퍼
데크(Deque, Double Ended Queue)	데이터 저장하는 기억장치가 양쪽 모두에 입출구가 있음 가장 많이 사용하는 메모리 사용법 스크롤: 출력은 양쪽에서 모두 가능하나 입력은 한쪽에서만 사용 셀프: 입력은 양쪽에서 모두 가능하나 출력은 한쪽에서만 사용
선형 리스트(Linear List)	배열과 같이 연속되는 기억 공간에 저장되는 리스크 구조 같은 데이터 타입의 요소들이 동일한 크기로 순차적으로 나열되어 있는 집합 삽입시 데이터 평균 이동 회수 = (데이터 수 + 1)/2, 삭제 = (데이터 수 - 1)/2
연결 리스트(Linked List)	자료를 연속으로 배열시키지 않고 임의의 공간에 기억시키되 각 자료의 포인터를 이용하여 연결 포인터를 포함한 자료 구조는 노드(Node), 노드에는 연결을 해주기 위한 포인터의 추가 공간 필요 종류 단일 연결 리스트(Single Linked List) 단일 환형 연결 리스트(Single Circular Linked List) 이중 연결 리스트(Double Linked List) 이중 환형 연결 리스트(Double Circular Linked List)

 

 

 

3. 비선형 구조

 

트리

 

Node	원
Edge, Link	노드와 연결된 선
Leaf, Terminal	자식 없는 노드
노드의 차수(Degree)	자식 노드의 개수
트리의 차수(Degree)	노드의 차수가 가장 큰 값
Level	특정 깊이를 가지는 노드 집합

 

 

그래프

https://blog.kakaocdn.net/dn/dw8QqI/btq7DVw0tCO/nuMCO1xM0YJwfBlAinKvE1/img.png

 

• 무방향성 그래프 간선의 수 = n(n-1)/2
• 방향성 그래프 간선의 수 = n(n-1)

 

 

 

 

4. 이진트리 순회

 

3가지 방법

 

중위(In-order)	좌측→근노드→우측
전위(Pre-order)	근노드→좌측→우측
후위(Post-order)	좌측→우측→근노드

 

 

 

5. 폴리쉬 표기법

 

 

 

 

 

Reference

https://book.naver.com/bookdb/book_detail.naver?bid=17134434 

이기적 정보처리기사 필기 기본서