[자료구조] 자료구조의 개요 및 자료표현 방법

자료와 정보

자료

현실 세계에 대한 관찰을 통해, 즉 어떤 측정을 통해 얻어진 단순한 값(사실)으로서
가공되지 않은 그 자체를 의미함

정성 데이터(qualitative data)

언어, 문자, 이미지, 신호(signal), 동영상 등 비정형 데이터

정량 데이터(quantitative data)

수치, 도형, 기호 등
저장/검색/분석 활용에 용이함
e.g.) 키, 몸무게, 국어점수, 날씨, 월별 매출액 등

정보

정보처리시스템을 통하여 어떤 조직체에 의미 있게 적절히 자료를 처리(분석) 하여
얻어진 값, 의사결정을 위한 지식을 말함

데이터를 가지고 있는 패턴 또는 모델에 적용하고, 분석하여 나온 결과

e.g.) 1학년 학생들의 국어 점수에 대한 평균값, 최고/최저점수
열차시간표의 열차의 출발과 도착시간, 월별 매출자료 추이 등

자료구조(data structure)

자료의 효율적인 접근 및 수정을 가능하도록 자료의 조직, 관리, 저장하는 일련의 작업으로
데이터 값의 모임 또는 데이터 간의 관계 그리고 데이터에 적용할 수 있는 함수나 명령을 의미함

프로그램(program)

특정 작업을 수행하는 일련의 명령어들의 모음, 즉 데이터를 표현(자료구조)하고,
표현된 데이터를 처리(알고리즘)하는 명령어 집합체를 의미함

컴퓨터(정보처리시스템)

자료를 수집, 분석, 저장하고 컴퓨터를 이용하여 유용한 형태의 정보로 가공하고 공유하는
일을 체계적이고 효율적으로 가능하도록 해주는 시스템을 말함
(주어진 문제와 관련된 자료들을 처리하여 문제를 해결하는 개체)

자료구조의 종류

Primitive(단순)와 non-primitive(비단순) 자료구조

단순구조(simple structure)

True/False, 정수, 실수, 문자 및 문자열과 같이 컴퓨터가 기본적으로 제공하는 자료형을 의미

비단순 구조

선형구조(linear structure) : 데이터들이 일렬로 저장되어 있는 형태
비선형구조(non-linear structure) : 데이터들이 상하관계의 계층구조의 형태

파일구조(file structure)

다양한 자료구조의 데이터를 파일에 저장하는 형태

자료표현 방법

자료 표현의 단위

자료의물리적단위와논리적단위 디지털 시스템에서의 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료는 물리적 단위(2진수 코드)로 표현하여 저장 및 처리함

저장장치

 비트(bit) : 정보 표현의 최소 단위로서 2 가지 상태를 표시하는 2진수 1자리 1과 0, ON과 OFF, 참(true)과 거짓(false)의 조합

 니블(nibble=4bit)

 바이트(byte=8bit)

 워드(word) : CPU가 한 번에 처리할 수 있는 명령 단위(half word, full word, double word) – 워드의 크기가 4바이트인 컴퓨터의 경우 > half word = 2바이트

---

정보저장/처리

 필드(field) : 자료구성 단위, 자료처리의 최소단위, 파일구성의 최소 단위

 레코드(record) : 하나 이상의 관련된 필드들의 모임, 프로그램 처리의 기본 단위

 블록(block) : 프로그램(저장장치)에 입출력될 때의 기본 단위(물리적 레코드)

 파일(file) : 응용 프로그램 구성의 기본 단위(레코드들의 집합)

 데이터베이스(database) : 서로 관련된 파일들의 집합

자료 표현의 개수

컴퓨터에 2진수 n개의 비트로 표현할 수 있는 수의 개수

자료 표현의 종류

컴퓨터에서 자료의 내부/외부적 표현(종류)

진법

개요

임의의 숫자를 사용하여 수를 표현하는 방법(기수법)을 말함

2진법 - 모든 데이터가 0과 1로 저장되는 컴퓨터의 특성상 컴퓨터 구조 및 동작을 이해하는 데 아주 중요한 역할을 함
10진법 - 일반적으로 사용하는 0 ~ 9까지의 숫자를 사용하여 수를 나타내는 방법
현재 프로그래밍에서 많이 사용되고 있는 진법의 종류

진법	사용하는수
2진법	0,1
8진법	0,1,2,3,4,5,6,7
10진법	0,1,2,3,4,5,6,7,8,9
16진법	0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F

진법 변환

임의의 진법(진수)을 다른 진법으로 바꾸는 방법

2진법을 10, 8, 16진법으로 변환하는 예

수치자료의 표현

10진수의 표현(zone 형식)

10진수 한 자리를 표현하기 위해서 1바이트(8비트)를 사용하는 형식

존 영역(상위 4비트) : 항상 1111로 표현 수치 영역(하위 4비트) : 표현하고자 하는 10진수 한 자리 값에 대한 2진수 값을 표시

여러 자리의 10진수를 표현하는 방법

10진수의 자릿수만큼 존 형식을 연결하여 사용함
마지막 자리의 존 영역에는 부호를 표시 - 양수(+) : 1100 -> C, 음수(-) : 1101 -> D

10진수의 표현(pack 형식)

10진수 한 자리를 표현하기 위해서 존 영역 없이 4비트를 사용하는 형식

존 형식의 문제점(처리속도와 기억공간)을 개선
최하위 4비트에는 부호를 표시 - 양수(+) : 1100 -> C, 음수(-) : 1101 -> D

보수(complement)

개요

컴퓨터가 기본적으로 수행하는 덧셈 연산을 이용하여 뺄셈을 수행하기 위해 사용함(A-B => A+(-B))
두 수의 합이 진법의 밑수(N)가 되게 하는 수

10진수 4에 대한 10의 보수는 6, 10진수 2에 대한 10의 보수는 8

r진법에는 r의 보수와 r-1의 보수가 있음

10진법의 경우(10의 보수와 9의 보수)

2진법의 경우(2의 보수와 1의 보수)

보수의 계산

보수 계산의 예

1의 보수 뺄셈
빼는 수의 1의 보수를 구한 다음 더함

덧셈 결과가 최상위 비트에서 자리올림이 생기면 최상위 비트를 제외하고 최하위 비트에 1을 더함

자리올림이 생기지 않으면 연산 결과에 대해 1의 보수를 구한 후 -부호를 붙임

2의 보수 뺄셈
빼는 수의 2의 보수를 구한 다음 더함

덧셈 결과가 최상위 비트에서 자리올림이 생기면 자리올림을 제외한 나머지 부분이 연산 결과임

자리 올림이 생기지 않으면 연산 결과의 2의 보수를 구한 후 -부호를 붙임

수치자료의 표현

2진수의 정수 표현(8비트로 부호화 절대치 형식)

최상위 비트에 부호를 표시

부호가 양수인 경우에는 최상위 비트 -> 0

부호가 음수인 경우에는 최상위 비트 -> 1

나머지 7비트는 2진수의 절대값을 표현

부호화 절대치 표현 방법을 이용한 수의 표현 개수: $-2^{n-1}+1 \sim 2^{n-1}-1$

2진수의 정수 표현(8비트로 1의 보수형식)

음수의 표현에서 부호 비트를 사용하는 대신 1의 보수를 사용하는 방법

n비트를 1로 한 2진수에서 변환하고자 하는 2진수를 뺌

1의 보수표현 방법을 이용한 수의 표현 개수: $-2^{n-1}+1 \sim 2^{n-1}-1$

2진수의 정수 표현(8비트로 2의 보수 형식)

음수의 표현에서 부호 비트를 사용하는 대신 2의 보수를 사용하는 방법

2의 보수표현 방법을 이용한 수의 표현 개수: $-2^{n-1} \sim 2^{n-1}-1$

2진수의 실수 표현 (고정소수점 형식)

소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있음
00011010 -> 0.00011010

2진수의 실수 표현 (부동소수점 형식)

고정소수점 표현 방식보다 표현 가능한 값의 범위가 큼(적은 비트로 매우 크거나 작은 값을 표현하여 효율적임): 오차가 발생, 연산속도가 느림

부동소수점 표현에 대한 IEEE754 표준

single precision에서는 부호 1비트, 지수부 8비트, 가수부 23비트를 사용(32비트)

double precision에서 부호 1비트, 지수부 11비트, 가수부 52비트를 사용(64비트)

부동소수점 표현의 예

정규화 - 값을 1.xxx형태로 표현
(-12.31)₁₀ = (-1100.010011………..)₂ = -1.100010011\cdots\times 2³ 지수부 = 3, 가수부 = 100010011….

지수부 바이어스 표현법 지수부는 2⁸ (0~255가지)를 표현[-127(0000 0000) ~ 128(1111 1111)]
음수 : 0~126, 127(=0), 양수 : 128 ~ 255
(00000000)₂는 underflow 처리용(음수 값이 지수부의 음수표현 범위를 초과할 경우)
(11111111)₂는 overflow 처리용(지수부가 최대 영역보다 커질 경우)
바이어스 값 : 가운데 값 127(0111 1111)
바이어스 값을 더하면 127 + 3 = 130
지수부 = (130)₁₀ = (10000010)₂ 정형화(결과)

문자자료의 표현

컴퓨터에서 문자자료 표현

문자 코드

문자에 대한 2진 코드를 정의해 놓은 코드로서 컴퓨터 내부에서는 문자 자료도 1과 0의 2진수 조합으로 표현함

문자 코드의 종류
BCD(Binary-Coded Decimal) 코드
EBCDIC(Extended Binary-Coded Decimal Interchange Code) 코드
ASCII(American Standard Code for Imformation Interchange) 코드
유니 코드(Unicode) 등

BCD(Binary-Coded Decimal) 코드

6비트를 이용하여 표현함
상위 2비트: 존 비트(zone bit), 하위 4비트: 숫자 비트(2진수)

0 ~ 9까지의 10진수 숫자, 영어 대문자와 일부 특수문자를 나타낼 수 있음
영어 소문자는 표시할 수 없음

BCD 코드 표

EBCDIC(Extended Binary-Coded Decimal Interchange Code) 코드

미국의 IBM사가 개발한 방식으로 8비트를 이용하여 표현함
상위 4비트: 존 비트(zone bit), 하위 4비트: 숫자 비트(2진수)

BCD를 확장하여 기존의 2비트였던 존 비트(zone bit)를 4비트로 늘림으로써 더 많은 문자를 표현할 수 있음 => 영어 소문자를 표현
표현할 수 있는 문자에 한계가 있었고 영어 알파벳 이외의 다른 문자는 표현 할 수 없음

EBCDIC 코드 표

영문자 A에 대한 EBCDIC 코드 = 11000001

ASCII(American Standard Code for Imformation Interchange) 코드

미국 표준협의회(ASA)에서 개발한 방식, 7비트를 이용하여 표현함
상위 3비트: 존 비트(zone bit), 하위 4비트: 숫자 비트(2진수)

존 비트와 숫자 비트를 조합하여 0-9까지의 10진수 숫자, 영어 대소문자, 특수문자를 나타낼 수 있음
EBCDIC코드와 같은 양의 문자를 나타낼 수 있지만 사용하는 비트의 수가 더 적어 효율적임
7비트의 크기를 가지기 때문에 남는 1비트를 데이터 통신 과정에서 데이터의 변조, 손상을 확인할 수 있는 패리티 비트로 활용할 수 있음
영어 알파벳 이외 언어의 문자를 표현 할 수 없음

ASCII 코드 표

영문자 A에 대한 ASCII 코드 = 1000001

유니 코드(Unicode)

국제 표준코드(ISO/IEC 10646)로서 16비트의 코드 값을 4자리의 16진수로 표시하여 전 세계의 모든 문자를 컴퓨터에서 일관되게 표현하고 다룰 수 있도록 설계된 표준코드

1byte로 BCD, EBCDIC, ASII 코드는 영어 알파벳 이외 언어의 문자를 표현할 수 없음 => 2byte로 다양한 언어를 포현할 수 있게 됨
PC가 보급되기 시작하던 때의 초기 IBM 컴퓨터 시스템에서는 BCD 코드를 사용
컴퓨터가 발전함에 따라 더 많은 문자를 표현할 수 있는 방안인 EBCDIC 코드가 사용됨
미국의 표준 코드인 ASCII가 일반화 됨
현재는 표현의 한계를 극복하기 위해 유니코드가 일반적으로 사용되고 있음

유니 코드 표

영문자 A에 대한 유니코드 = (0041)₁₆ = (0000\,0000\,0100\,0001)₂

논리자료의 표현

논리값(logic value) 자료

논리값을 표현하기 위한 자료로서 참(true)와 거짓(false)중 하나를 표시한 값

0과 1을 이용하여 1비트로도 표현할 수 있음
컴퓨터 내부에서는 1바이트나 1워드(word)로도 표현할 수 있음

방법	참	거짓
1	최하위 비트를 1로 표시(0000 0001)	전체 비트를 0으로 표시(0000 0000)
2	전체 비트를 1로 표시(1111 1111)	전체 비트를 0으로 표시(0000 0000)
3	하나 이상의 비트를 1로 표시	전체 비트를 0으로 표시(0000 0000)

포인터 자료의 표현

포인터(pointer) 자료

메모리 주소를 표현(저장)하기 위한 자료
자료를 저장하고 있는 변수나 특정 위치의 메모리 주소에 대해 주소 연산을 할 때 사용함
포인터 자료를 사용하면 복잡한 자료구조 연산을 메모리에서의 주소 연산만으로 처리할 수 있음

문자열 자료의 표현

문자열(string) 자료

한 글자만 표현하는 문자 자료와 달리 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료

문자열 하나는 부분 문자열(substring)을 여러 개 포함할 수 있음

부분 문자열을 포함하는 문자열 자료를 메모리에 저장하는 방법

문자형과 문자열 자료형 표현(C언어)

문자 : char a = ‘A’; //변수에 문자 ‘A’를 저장
문자열 : char*s1 = “I LOVE YOU”; //포인터에 문자열 “I LOVE YOU”의 주소 저장