티스토리 뷰
자료구조 선택시 중요사항
- 자료의 처리 시간
- 자료의 크기
- 자료의 활용 빈도
- 자료의 갱신 정도
- 프로그램의 용이성
수치자료의 표현
## 존형 : 각 숫자를 문자로 취급하여 기억시키되 한 바이트 내에 10진수 한 자리를 표현.
Zone 부분에는 16진수 F 삽입, Digit 부분에는 수 값 표현
마지막 Zone 부분에는 부호를 표시 (1100(+), 1101(-))
+213
| 1111 | 0010 | 1111 | 0001 | 1100(부호) | 0011 |
| F | 2 | F | 1 | + | 3 |
## 팩형 : 10진 연산을 위한 저장방식, 각 바이트에 10진수 2자리를 표현, 가장 오른쪽 바이트는 수치의 마지막 한자리와 부호화 같이 기억 -> 존형의 단점을 보완하기 위해 등장
존형의 단점 : 처리속도가 늦음, 기억공간의 낭비
-213
| 0010 | 0001 | 0011 | 1101(부호) |
| 2 | 1 | 3 | - |
## 1의 보수 , 2의 보수
21(10진수)의 1의 보수와 2의 보수를 구하는 방법
21 -> 00010101 (2진수)
11111111 (1의 보수를 구하기 위해 비트의 수에 만큼의 1을 뺀다.)
- 00010101
-------------------
11101010 ==> 21의 1의 보수
+ 1 ==> 21의 2의 보수는 1의 보수에 1을 더한 값
-----------------------
11101011 ==> 21의 2의 보수
##고정소수점
: 고정 소수점은 부호비트, 정수부, 소수부 로 나뉘어 진다.
16비트 체계를 쓴다고 가정하고 7.625 를 고정 소수점으로 나타내 보자
7 -> 111(2진수)
0.625 -> 0.101(2진수) => 7.625 = 111.101(2진수) 이다.
비트로 나타내면 아래와 같이된다.
## 부동소수점
: 부동 소수점은 소수점이 floating 한다는 것을 말한다. 즉, 소수점을 움직여서 수를 표현한다.
따라서 부동소수점은 소수부와 지수부로 나뉜다.
1324.232 => 0.1324232 * 10^4 ==> 지수부는 10의 4승으로 4이다. 가수부는 1324232
일반적으로 16진수로 변환 후 표현
예) -123.45 를 32비트로 표현하기
우선 해당 10진수 숫자123을 16진수로 바꾸기 -> 123(진수) / 16 = 몫:7, 나머지 11(B) ==> 7B(16진수)
10진수 소수부 0.45를 16진수로 바꾸기 ->
0.45 * 16 = 7.20 => 7은 16진수의 값
0.20 * 16 = 3.20 => 3은 16진수의 값
.... 계속해서 반복 => 따라서 0.45를 16진수로 나타내면 0.7333...
-123.45 = -7B.7333.... => -0.7B7333 * 16^2 으로 표현 가능
지수부를 구하기 위해서는 bias 값을 더해야 한다. 16비트의 bias 값은 40이다.
40 + 2 = 지수부 / 소수부 = 7B7333
위의 숫자를 그림으로 나타내면 아래와 같다.
| 1 (부호) | 100 0010 | 0111 1011 0111 0011 0011 0011 | |||||
| 1(부호)100 = C, 0010 = 2 | 7 B 7 3 3 3 | ||||||
C27B7333(16진수)로 기계 내부에서 표현한다.
문자자료의 표현(BCD, EBCDIC ASCII)
## BCD 코드 : 6비트 코드이다. Zone 2비트 + Digit 4비트 로 표현
Zone = 00 (0, 1~9), 01 (A~I), 10(J~R), 11(S~Z) 표현
- 특징 : 숫자와 영어 대문자 표현(소문자 표현 X), 64가지 표현
## EBCDIC 코드 : Zone 4bit + Digit 4bit = 8bit
특징 : 256 가지 문자 표현 가능, 대문자와 소문자 구별 가능, 미지정 코드가 있어 추가 문자 표현 가능
## ASCII 코드 : Zone 3bit + Digit 4bit = 7bit
특징 : 별도로 1 패리티 비트 사용, 128 종류 문자 표현 가능, 데이터 통신용으로 사용
## Parity bit : 정보의 전달과정에서 오류가 생겼는지 검사하기 위해 원래의 정보에 덧붙이는 비트. 이는 시스템의 논리구조에 따라 1로 된 비트들의 개수가 항상 짝수 또는 홀수가 되도록 바이트의 끝에 붙인다.
0010110 -> 짝수 패리티가 되기 위해서 00101101 => 끝에 1을 붙인다.
기타형식의 코드
## 가중치 코드 : 각 비트의 위치에 특정한 크기의 가중치를 갖는 코드(8421, BCD, EBCDIC...)
## 비가중치 코드 :
# 3초과 코드 : BCD코드에서 3을 더하여 얻은 코드
# 2-OUT OF-5 코드
# 그레이 코드 : 인접한 코드값을 단일비트 변화만으로 표현할 수 있는 코드
2진수 코드 그레이 코드로 변화하는 방법!!
10001 (2진수) 숫자를 그레이 코드로 바꾸기 위해서 XOR 연산을 행해야 한다.
2진수의 최대비트는 그대로 내려온다 그후 최대 비트와 그 오른쪽에 있는 수를 XOR 계산하여 그레이 코드를 채워 나간다.
빨간색 1이 보라색 1로 그대로 내려온다. 이후 빨간색 1과 파란색 0을 XOR 연산한다. 그 후 2진수의 숫자들을 XOR 연산
| 1 | 0 | 0 | 0 | 1 | 2진수 |
| 1 | 1 | 0 | 0 | 1 | 그레이 |
그레이 코드는 11001 이 된다.
그렇다면 그레이 코드를 2진수로 바꾸려면 어떻게 해야할까?
11001 을 2진수로 바꿔보자
우선 그레이비트의 최대비트의 값 또한 그대로 2진수의 최대비트값이 된다.
그 후 2비트의 최대 비트와 그레이코드의 최대비트 바로 옆에 수와 XOR 연산을 진행한다.
| 1 | 1 | 0 | 0 | 1 | 그레이 |
| 1 | 0 | 0 | 0 | 1 | 2진수 |
빨간색 1이 보라색 1로 그대로 내려온다. 그후 보라색 1과 그레이 코드의 파란색 1을 XOR연산한다. 즉 대각선으로 연산을 한다. 계속해서 XOR연산하여 2진수의 값을 구한다.
포인터 자료의 표현과 저장구조
: 포인터 자료는 자료구조에 참조의 의미로서 기억장소에 저장한 자료의 주소를 말한다.
주소는 양의 정수로서 고정된 크기의 비트들로 표현, 자료 상호간의 관련성을 표현할 수 있다.
이를 통해 자료를 첨가하거나 제거하는 작업을 빠르게 수행할 수 있다.
장점 : 자료 상호간의 관련성을 표현, 삽입 삭제 작업을 빠르게 수행
단점 : 연산속도가 늦어진다. / 디버깅이 느리다 / 수행시간이 느리다 / 시스템 성능이 저하될 가능성이 있다.
파일의 구조
: 파일을 구성하기 위해서는
- 파일의 크기, 정보의 양
- 데이터의 검색빈도
- 파일의 갱신빈도
- 레코드에 포함되는 접근 키 필드의 수(Primary Key가 1개 이상 반드시 존재)
파일로 구성하는 이유
- 대량의 데이터로 주 기억장치에 한꺼번에 전부 적재할 수 없다.
- 프로그램은 어느 일정 시간만 데이터에 접근하므로 전부 적재할 필요없다.
- 데이터의 독립성을 유지하므로 여러 응용 프로그램과 서로 공용하기 쉽다.
## 레코드의 종류
: 논리적으로 취급되는 레코드를 논리 레코드라고 하며, 보조기억장치 상에서 실제 입출력의 단위가 되는 레코드를 물리레코드라고 한다. 물리 레코느는 1개 이상의 논리 레코드로 구성되며, 여러개의 논리 레코드를 물리 레코드로 만드는 작업을 블록화 작업 이라고 한다. 이러한 물리 레코드를 블록 이라고 한다.
- 고정 길이 레코드
- 고정 길이 비 블록화 레코드 : 각 논리 레코드의 길이가 일정하다. 물리 레코드 길이 = 논리 레코드 길이
- 고정 길이 블록화 레코드 : 블록화된 레코드로서 논리 레코드의 길이가 일정하다. 하나의 물리 레코드 내에 2개 이상의 논리 레코드가 존재.
- 가변 길이 레코드
- 가변길이 비 블록화 레코드 : 각 논리 레코드의 길이가 일정하지 않다. 따라서 논리 레코드의 길이가 얼마인가 알려주는 필드가 있다.
- 가변길이 블록화 레코드 : 길이가 일정하지 않은 논리 레코드가 블록화 되어 있는 형식으로 각 블록마다 블록의 길이를 알려주는 필드가 있고 블록 내의 각 레코드마다 레코드의 길이를 알려주는 필드가 있다.(필드가 2개 존재 : 블록의 길이, 레코드의 길이)
파일의 종류
처리과정 : 입력파일, 임시파일, 출력파일
기록매체 : 카드파일, 자기테이프 파일, 자기디스크 파일
파일의 내용 : 데이터, 프로그램 파일, 요약파일, 보고서 파일
# 데이터 파일
- 원시파일 : 기본적인 파일
- 마스터 파일 : 자료를 수록한 파일로 원장 파일이라고 하며 비교적 고정화된 자료들이 장기적으로 보관
트랜잭션 파일에 의해 수정, 갱신될 수 있으며 급여 마스터 파일, 재고 마스터 파일 등이 있다.
- 트랙잭션 파일 : 변동사항이 발생할 경우 마스터 파일을 갱신하거나 수정하기 위해 만들어진 파일로써 일시적으로 기록하는 변동파일
- 히스토리 파일 : 과거에 사용한 마스터 파일이나 트랜잭션 파일을 지정하는 것으로 통계 처리나 사고발생시 원상 복구하기 위한 내용을 담고 있는 기록파일
- 요약 파일 : 통계처리나 집계를 편리하기 위해 다른 데이터 파일을 보다 간단한 형태로 축소한 요약 파일
# 작업 파일 : 자료를 다른 프로그램의 입력으로 사용하기 위해 일시적으로 기록한 파일로 작성되는 시점이나 성격에 따라 분류
# 프로그램파일 :
파일의 편성 방법
## 순차파일 :
파일 매체에 레코드들이 연속적, 순서적으로 편성되어 있는 파일. 파일의 구조는 논리적 순서에 따라 특정 키의 순서로 정렬되어 물리적으로 저장되어 있고 검색시에는 레코드들을 순차적으로 접근하기 때문에 일괄 처리에 적합
장점 :
- 레코드를 키순으로 처리할 경우 파일의 편성 방법이나 처리속도가 빠르며 기본이 된다.
- 어떤 매체에서도 사용이 가능
- 기억공간을 차례대로 사용하므로 매체의 사용 효율이 좋다.
- 처리할 양이 많거나 전체 데이터를 모두 처리할 경우 효율적이다.
단점 :
- 특정한 레코드를 검색할 경우 항상 처음부터 조사해야 하므로 검색 속도가 느리다.
- 레코드의 삽입과 삭제 시 전체 파일을 새로운 매체에 복사해야 한다.
- 하나의 키에 따라 연속적으로 정렬 시켜야 한다.
- 활동량에 관계엾이 파일 저네의 검색이 필요하다.
- 레코드나 블록 길이 블록킹 요소를 결정할 때 주의해야한다.
## 색인 순차 편성 파일
: 순차적으로 접근하거나 주어진 키 값에 따라 직접 레코드에 접근할 수 있는 파일
1) 기본 데이터 영역 (Prime data area) : 실제 데이터가 기록는 부분으로 키 순서대로 저장
2) 색인 영역(index area) : 저장된 레코드의 키와 주소를 저장하는 영역
- 트랙 색인 영역 (track index Area) : 데이터 구역의 한 트랙 상에 저장되어 있는 데이터 레코드 중 최대 키 값과 그 주소에 대한 정보가 기록
- 실린더 색인 영역 (cylinder index Area) : 처리해야 할 레코드가 어느 실린더에 있는가를 나타내 주는 정보가 수록되어 있고 각 실린더에서 가장 큰 값과 주소를 보관한다.
- 마스터 색인 영역 (master index Area) : 실린더 색인 정보의 양이 많을 경우 일정한 크기의 블록으로 블로킹하여 처리해야 할 키 값을 갖는 레코드가 어느 실린더 상에 기록되어 있는가를 나타냄
3) 오버플로우 영역 (overflow area) : 새로 추가되는 레코드가 많아 기본 데이터 영역에 더 이상 보관할 수 없을 때 오버플로우 된 레코드를 저장하는 영역
- 실린더 오버플로우 영역 : 기본 데이터 영역에 더 이상 레코드를 보관할 수 없을 대 오버플로우된 레코드를 저장하는 영역으로 각 실린더 내에 만들어 놓은 오버플로우 영역이다.
- 독립 오버플로우 영역 : 실린더 오버플로우 영역에 다시 오버플로우가 발생한 경우에 레코드를 기록할 수 있도록 별도록 만들어진 오버플로우 영역
장점 :
- 순차처리와 랜덤처리가 가능해 융통성이 있다.
- 레코드의 삽입, 삭제 시 순차파일처럼 전체 레코드를 복사할 필요가 없다.
단점 :
- 색인 및 오버플로우 구역이 필요하다
- 색인을 사용하므로 직접 편성보다 엑세스 시간이 느리다.
- 처리의 표율을 높이기 위해 파일의 재처리가 필요하다.
## 직접 편성 파일
: 직접 처리와 순차 처리가 가능하다. 레코드를 엑세스 할 때 그 레코드가 저장되어 있는 주소를 직접 사용자가 지정하는 방법으로 편성, 이 때 주소를 결정하는 방법으로 직접 주소법, 디렉토리 조사, 해싱
장점 :
- 직접처리 또는 임의 처리에 적합하다.
- 모든 레코드의 접근 시간이 일정하여 빈번한 자료 검색에 효율적이다.
- 대화식 처리에 이용할 수 있다.
단점 :
- 연속적이며 전체적인 검색이 어렵다.
- 기억 공간의 효율성이 감소
- 모든 레코드는 반드시 키가 있어야 하며 키의 위치는 일정해야 한다.
1) 데이터 레코드가 순차적으로 저장되어 있지 않고 각 레코드에 주소가 부여되어 있어 처음부터 데이터를 검색 하지 않아도 주소만을 참조하여 찾고자 하는 레코드들을 직접 액세스한다.
2) 레코드 중의 특정항목을 키로 하여 키 변환에 의해 기억가능 한 주소를 계산해 내고 이 주소에 레코드를 기억시키는 방법
주소를 결정하는 방법
(1) 직접 주소법 ;
a. “키값 --> 주소”의 사상함수를 구현하는 가장 간단한 방법
b. 주소공간이 있는 레코드의 실제 주소를 키값으로 직접 지정
c. 별로 사용 안함
(2) 디렉토리 조사 방법 ;
- [키값, 주소]쌍으로 구성된 디렉토리를 유지하여
해당 레코드의 위치를 찾는다.
(3) 해싱 방법 ;
a. 해싱함수를 사용
b. Hash Index를 사용하여 해당 레코드에 접근
c. 해싱함수는 계산이 빠르고 간단.
키-주소 변환방법에 의해 충돌(서로 다른 키값에 의해 동일한 주소공간을 점유하는 현상) 이 발생하므로 이를 위한 기억공간의 확보로 공백이 많아져 효율성이 감소한다.
#색인순차 편성파일
순차 파일과 직접 파일의 장점을 취한 편성방법으로
파일을 만들 때 색인(Index) 를 붙여 편성한 순차 파일이다.
오버플로우 영역
색인순차 파일이 생성된 후 기본 데이터 영역에 빈 공간이 없어 새로운 데이터 레코드의 삽입이 불가능할 때
초과되는 데이터 레코드를 저장할 수 있도록
예비적으로 확보해 두는 영역
#직접편성파일
(그림에 대한 전제조건)
* 기억장치가 몇 개의 구분된 블록으로 되어 있고, 각 블록 내에는 몇 개의 버켓(Bucket : 같은 부류의 레코드를 몇 개씩 묶은 것을 저장하는 장소) 으로 되어 있는 경우
(1) 트랜잭션 키 항목의 값이 “215”가 입력되면
(2) 키 변환 프로그램에 의해 변환된 결과 “9”를 가지고
(3) 9번 블록내에 있는 버켓 215에서 데이터를 읽거나 기록한다.
연접리스트
: 가장 간단한 선형 구조로서 연속된 기억 공간에 리스트를 구성하고 있는 원소들을 순
서대로 차례로 기억시킨 구조를 연접 리스트라고 한다. 그리고 연접 리스트는 원소들이
순차적으로 표현되므로 순차 리스트(sequential list) 순서 리스트(ordered list) 또는 선
형 리스트(linear list)라고도 한다
- 기억 밀도 (density)
연접 리스트의 기억 공간 효율성은 아주 높다고 할 수가 있다.
기억 밀도 = 정보비트수 / 총비트수
즉, 연접 리스트는 총 비트 수와 정보 비트 수가 일치하기 때문에 효율성은 1이다. 이
것은 기억 공간의 낭비가 거의 없다는 것을 나타낸다.
(2) 연접 리스트의 삽입과 제거
▣ 장점
ㆍ각 노드들이 기억된 기억 장소를 쉽게 파악할 수 있다.
ㆍ기억 공간의 효율성이 아주 좋다. (낭비가 없다)
ㆍ임의의 노드를 검색 시 access time이 빠르다.
▣ 단점
ㆍ중간 노드의 삽입과 제거가 어렵다.
ㆍ반드시 연속적인 기억 공간이 확보되어야 한다.
필요시 : 중간에 삽입과 삭제가 적은 데이터 처리하는 곳에 필요시된다
#이동횟수
크기가 3인 배열에 인덱스 1번에 데이터를 삽입 하려고 한다.
데이터의 이동 횟수는 어떻게 되는가? => 인덱스 3 인 공간을 생성하고 인덱스 1번과 2번을 각각 2번과 3번으로 옮겨준다. 즉, 2번의 이동 횟수가 일어났다. 공식으로 나타내면
=> 마지막 원소의 자릿값(2) - 삽입할 자리의 인덱스(1) + 1
2 - 1 + 1 = 2 => 2번의 이동횟수 발생
만약 크기가 200 인 배열에 인덱스 3,4번에 데이터를 추가 삽입하려고 한다. 이동횟수는?
추가기전 마지막 인덱스 갯수 (200) - 추가할 마지막 인덱스 (4) + 1 => 197
자료의 개수가 n개일 때 삽입 시의 평균 이동 횟수는 (n+1)/2이고, 삭제 시에는 (n-1)/2이다.
원소 삭제시 자리이동 횟수 = n - k = 마지막 인덱스 - 삭제된 인덱스
'개인공부 > DATA STRUCTURE' 카테고리의 다른 글
| Quick-Sort (0) | 2021.03.08 |
|---|