자료구조 종류와 표현 방법

자료

현실 세계에 대한 관찰을 통해, 어떤 측정을 통해 얻어진 단순한 값으로 가공되지 않은 그 자체(Raw data)

정성데이터(qualitative data)

• 언어, 문자, 이미지, 신호, 동영상 등 비정형 데이터
• 상대적으로 많은 비용과 기술적 투자가 수반됨

정량 데이터(quantitative data)

• 수치, 도형, 기호 등
• 저장/검색/분석 활용에 용이

 

정보

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

예) 1학년 학생들의 국어 점수에 대한 평균값 및 최고/최저점수, 열차시간표에서 열차 출발과 도착시간 등

출처 : https://m.khan.co.kr/feature_story/article/201606102200005

 

자료구조

 

정의

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

 

필요성

자료구조를 사용하면 최적의 프로그램을 작성함으로써 공간에 대한 절약(공간복잡도), 시행 시간 최소화가 가능하다(시간복잡도)

자료구조는 다양하게 존재하며, 이는 프로그램의 문제 해결을 위해서 잘 어울리는 자료구조를 선택해서 프로그램의 효율성을 증대하기 위함으로 볼 수 있음

 

자료구조의 선택

순차적인 탐색이 주로 수행되는 문제인지?

삭제 연산이 주로 수행되는 문제인지? 에 따라 자료구조 선택을 달리해야함

1. 문제의 해답을 만족해야 하는 데이터 제약 조건을 파악
2. 문제 해결을 위한 기본 연산을 결정하고, 특별한 데이터 형태가 있는지 파악이 필요
3. 위 요구사항을 가장 잘 만족하는 자료구조를 선택

 

자료구조의 종류

 

단순구조(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개의 비트로 표현할 수 있는 수의 개수

비트 수	자료표현 개수
n=1	2(=2^1)	0, 1
n=2	4(=2^2)	00,01,10,11
n=3	8(=2^3)	000,001,010,011,100,101,110,111
n=4	16(=2^4)	0000,0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,1110,1111

 

진법

임의 숫자를 사용해 수를 표현하는 방법

• 2진법 - 모든 데이터가 0과 1로 저장되는 컴퓨터 특성상 컴퓨터 구조 및 동작을 이해하는데 아주 중요한 역할
• 10진법 - 일반적으로 사용하는 1 ~ 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

 

진법의 변환

사용자가 메모리에 데이터가 어떻게 저장되어 있는지 알 필요가 있어 컴퓨터 내부의 데이터를 표현하기 위함

• 일반적으로 컴퓨터 메모리에 저장되는 데이터는 0101000011과 같이 2진수로 저장
• 2진법으로 표현된 데이터는 읽기가 쉽지 않아 일반적으로 사용하는 10진법이나 주소체계에서 사용되는 16진법 등으로 변환이 필요함

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

진법	사용 숫자
2진법 -> 10진법	(1101.11)2 = (1*2^3)+(1*2^2)+(0*2^1)+(1*2^0)+(1*2^-1)+(1*2^-2) = 8+4+0+1+1/2+1/4=(13.75)10
2진법 -> 8진법(3자리 단위로 변환)	(110111)2 = (110 111)2 = (67)8
2진법 -> 16진법(4자리 다나위로 변환)	(111001111)2 = (0001 1100 1111)2 = (1CF)16

 

수치자료의 표현

10진수의 표현(zone 형식)

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

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

여러 자리의 10진수를 표현할 경우

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

 

10진수의 표현(pack 형식)

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

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

보수

• 컴퓨터가 기본적으로 수행하는 덧셈 연산을 이용하여 뺄셈을 수행하기 위해 사용함(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진수의 정수 표현(8비트로 1의 보수 형식)

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

 

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

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

 

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

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

• 00011010 -> 0.00011010

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

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

부동소수점 표현에 대한 IEEE 754 표준

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

 

부동소수점 표현의 예

(-12.31)10 = (-1100.010011......)2을 32비트로 컴퓨터에 표현하는 경우

 

부동소수점 표현의 예

정규화 - 값을 1.xx 형태로 표현

• (-12.31)10 = (-1100.010011......)2 = -1.100010011... * 2^3
• 지수부 = 3, 가수부 = 100010011......

지수부 바이어스 표현법

• 지수부는 2^8(0~255)를 표현[-127(0000 0000) ~ 128(1111 1111)]
• 음수 : 0~126, 127(=0), 양수 : 128 ~ 255
• (00000000)2는 underflow 처리용(음수 값이 지수부의 음수표현 범위 초과 시)
• (11111111)2는 overflow 처리용(지수부가 최대 영역보다 커질 경우)

바이어스 값을 더하면 127 + 3 = 130

지수부 = (130)10 = (100000010)2

정형화(결과)

 

문자 자료의 표현

문자 코드

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

문자 코드의 종류

• BCD(Binary-Coded Decimal) 코드
• EBCDIC(Extended Binary-Coded Decimal Interchange Code) 코드
• ASCII(American Standard Code for Information Interchange) 코드
• 유니 코드(Unicode) 등

 

BCD

6비트를 이용하여 표현함

상위 2비트 : 존 비트, 하위 4비트 : 숫자 비트(2진수)

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

 

EBCDIC

미국의 IBM사가 개발한 방식으로 8비트를 이용하여 표현

상위 4비트 : 존비트, 하위 4비트 : 숫자 비트(@진수)

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

 

 

ASCII

미국 표준협의회에서 개발한 방식, 7비트를 이용하여 표현

상위 3비트 : 존비트, 하위 4비트 : 숫자비트(2진수)

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

 

유니코드

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

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

 

논리자료의 표현

논리값 자료

논리값을 표현하기 위한 자료로서 True / False 중 하나를 표시한 값

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

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

 

포인터 자료

메모리 주소를 표현(저장)하기 위한 자료

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

 

문자열 자료

한글자만 표현하는 문자 자료와 달리 여러 글자로 이루어진 문자 그룹을 하나의 자료로 취급하여 메모리에 연속적으로 저장하는 자료. 문자열 하나는 부분 문자열(substring)을 여러개 포함할 수 있음

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

 

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

문자 : char a = 'A' // 변수에 문자 'A'를 저장

문자열 : char * s1 = "I LOVE YOU"; // 포인터에 문자열 "I LOVE YOU"의 주소저장

 

내용 정리

• 자료구조는 자료의 효율적 접근 및 수정이 가능하도록 자료의 조직, 관리, 저장하는 일련의 작업
• 프로그램은 데이터를 표현(자료구조)하고, 표현된 데이터를 처리(알고리즘)하는 것으로 추상적인 형태의 알고리즘을 컴퓨터가 수행할 수 있도록 구체화한 결과물
• 보수란 컴퓨터가 기본적으로 수행하는 덧셈 연산을 이용하여 뺄셈을 수행하기 위해 사용
• 디지털 시스템에서의 숫자, 문자, 그림, 소리, 기호 등 모든 형식의 자료는 물리적 단위(2진수 코드)로 표현하여 저장 및 처리한다.
• 코드는 문자에 대한 2진 코드를 정의해 놓은 문자코드로서 컴퓨터 내부에서는 문자 자료도 1과 0의 2진수 조합으로 표현됨.
• 부분 문자열을 구분하여 저장하는 방법에는 부분 문자열 사이에 구분자를 사용하여 저장하거나, 가장 긴 문자열의 길이에 맞춰 고정길이로 저장하는 방법, 그리고 부분 문자열을 연속하여 저장하고 각 부분 문자열에 대한 포인터를 사용하는 세 가지가 존재.