[자료구조] 개념 PART.1

자료구조의 개념

• 자료를 효율적으로 이용할 수 있도록 컴퓨터에 저장하는 방법
• 신중히 선택한 자료구조는 더 효율적인 알고리즘을 사용할 수 있게 한다.
• 자료구조의 선택문제는 대개 추상적 자료구조의 선택으로부터 시작하는 경우가 많다.
• 효과적으로 설계된 자료구조는 실행시간 혹은 메모리 용량과 같은 자원을 최소한으로 사용하면서 연산을 수행하도록 해준다.

 

자료구조의 필요성

컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여 그에 대한 최적의 프로그램을 작성해야 해서 자료구조에 대한 개념과 활용 능력이 있어야 한다.

 

 

형태에 따른 자료구조의 분류

자료구조
단순구조		정수	실수	문자	문자열
선형구조		리스트	연결리스트	스택	큐	데큐
선형구조 - 연결리스트		단일	이중	원형
비선형구조		트리	그래프
비선형구조 - 트리		일반 트리	이진 트리
비선형구조 - 그래프		방향	무방향
파일구조		순차파일	색인파일	직접파일

 

단순구조

• 프로그램 언어에서 제공하는 기본적인 자료형(data type)
• 일반적으로 데이터라고 표현하는 자료를 뜻함

선형구조

• 여러 개의 자료를 한 줄로 순서대로 저장하는 구조
• 각각의 자료들 사이의 관계가 1:1인 경우

비선형구조

• 각각의 자료들 사이의 관계가 1:1이 아닌 계층 및 망 구조를 가지는 경우

파일구조

• 보조기억장치에 저장되는 파일에 대한 자료구조
• 메모리에 한 번에 올릴 수 없는 대용량을 다룸

 

자료의 표현 - 수치자료

1. 수치 데이터 표현

• 비트(bit) : 컴퓨터에서 사용하는 최소의 단위로써 0, 1을 나타냄
• 바이트(byte) : 영문 1글자를 나타내는 단위로 8bit로 이루어짐
• 워드(word) : 워드의 크기는 컴퓨터의 종류에 따라 2byte, 4byte, 8byte 등이 있는데 통상 2byte를 말함

* 강의에서는 통상 4byte라고 하는데 word 기본형의 크기는 2byte다. 어셈블리에서도 word 기본형이 2byte이므로 강의에서 말한 4byte가 어떤 의미로 말한 것인지 설명하지 않아 기본형의 크기 2byte를 적음

워드(word) 종류

자료형	크기	정의	비고
word	16bit (2byte)	unsigned short	word 1개
dword	32bit (4byte)	unsigned long	double word (word 2개)
qword	64bit (8byte)	unsigned __int64	quad word (word 4개)

 

2. 수의 진법

1) 2진법

- 0과 1의 조합으로 숫자를 표현

2) 8진법

- 0 ~ 7의 조합으로 숫자를 표현

3) 10진법

- 0 ~ 9의 조합으로 숫자를 표현, 10을 한자리의 기본 단위로 하는 진법

4) 16진법

- 0 ~ 9, A ~ F의 조합으로 숫자를 표현, 10진법과 비슷하지만, A = 10, B = 11, C = 12, D = 13, E =14, F = 15로 사용함

  10개의 숫자와 그 뒤를 표현하는 숫자는 앞 숫자의 조합이므로 알파벳으로 대체해 숫자를 표현

 

3. 자료의 표현방식

1) 내부적 표현 방식

내부적 표현 방식

 

(1) 고정 소수점 방식

 

• MSB(Most Significant Bit) : 부호 비트(양수 : 0, 음수 : 1) 가장 왼쪽에 있는 비트
• 양수의 경우 정수 부분 : 10진수를 2진수로 변환하여 표시
• 음수의 경우 정수 부분 : 부호와 절댓값의 표현법 1의 보수법이나 2의 보수법 중 하나를 사용하는데 보통 2의 보수법을 많이 사용

(2) 부동 소수점 방식 (float)

 

• MSB(Most Significant Bit) : 부호 비트(양수 : 0, 음수 : 1) 가장 왼쪽에 있는 비트, sign, 가수부의 부호
• 지수부 : 지수를 2진수로 변환하여 표시, 지수 승의 표현
• 가수부 : 소수점 안의 유효 숫자를 2진수로 표현 이때 소수점은 지수부와 가수부 사이에 있는 것으로 가정, 정규화된 소수점 아래의 유효숫자

sign (부호)

Exponent (지수부)

Mantissa (가수부 = 소수부)

 

(3) 10진 연산

 - 언팩(Unpack) 형식 표현 (F(Zone), Digit 하나가 1byte임, 두 개씩 짝을 이룸)

 

	F(Zone)	Digit	F(Zone)	Digit	F(Zone)	Digit	Sign	Digit
+1234	1111	0001	1111	0010	1111	0011	1100	0100
	F	1	F	2	F	3	양수(C)	4
-1234	1111	0001	1111	0010	1111	0011	1101	0100
	F	1	F	2	F	3	음수(D)	4

 

 - 팩(Pack) 형식 표현 (Digit 두 개가 1byte임, 두 개씩 짝을 이룸, F(Zone) 비트가 빠짐)

 

	Digit	Digit	Digit	Digit	Digit	Sign
+1234	0000	0001	0010	0011	0100	1100
		1	2	3	4	양수(C)
-1234	0000	0001	0010	0011	0100	1101
		1	2	3	4	양수(D)

2) 외부적 표현 방식

 - 자료의 외부적 표현 방법은 사람이 확인할 수 있도록 출력할 때의 문자를 표현하는 방법

 

외부적 표현 방식

BCD (2진화 10진 코드)

ASCII (미국 표준화 정보 코드)

EBCDIC (확장 2진화 10진 코드)

 

• BCD 코드 : 6bit 코드로 IBM사에서 개발, 1개의 문자를 2개의 Zone 비트와 4개의 Digit 비트로 표현
• ASCII 코드 : 미국표준협회에서 개발한 7bit 코드, 1개의 문자를 3개의 Zone 비트와 4개의 Digit 비트로 표현 
• EBCDIC 코드: 8bit 코드로 IBM사에서 개발, 1개의 문자를 4개의 Zone 비트와 4개의 Digit 비트로 표현

 

4. 수치연산 및 논리연산

1) 컴퓨터 연산

 - 입력된 데이터, 기억 장치 내의 데이터, 중아 처리 장치 내의 레지스터에 기억되어 있는 데이터 등을 중앙 처리 장치 내의 연산기(ALU)를 이용하여 처리하는 것

2) 연산

(1) 비수치적인 데이터 연산

 - complement, AND, OR 등과 같은 논리적인 연산과 시프트(Shift), 로테이트(Rotate) 등

 

(2) 수치적인 데이터 연산

 - 고정 소수점 표현 방식과 부동 소수점 표현 방식의 수치에 대한 사칙 연산과 산술적 시프트

 

5. 음수의 표현

컴퓨터에서 음수를 표현하는 방법은 이론적으로 3가지 있다.

 

1) 부호화 절대치 방법(Signed-magnitude representation)

 - 최상위 비트는 부호표현이고, 나머지는 자릿값을 갖는 크기를 나타냄

2) 1의 보수 방법 (1's complement)

 - 음수를 1의 보수로 표현하는 방법은 비트를 0은 1로 1은 0으로 바꿔준다. 0이 2개가(+0, -0) 존재하는 모순성이 있음

이론적으로만 있으며 사용하지 않음.

3) 2의 보수 방법 (2's complement)

 - 1의 보수에다가 +1을 한다. +0, -0과 같이 0이 2개 존재하는 1의 보수의 모순이 없어진다. 따라서 컴퓨터의 음수 표현은 2의 보수를 사용한다.

 

자료의 표현 - 문자자료

문자자료는 외부적 표현에 해당하는 것을 말한다. 위 외부적 표현에서 설명한 것을 더 자세하게 설명한다.

1) 외부적 표현 방식

 - BCD 코드 : 6bit 코드로 IBM사에서 개발, 1개의 문자를 상위 2개의 Zone 비트와 하위 4개의 Digit 비트(2진수 비트)로 표현, 64가지 표현 가능, 대, 소문자 구별 못 함

Zone 비트와 2진수 비트를 조합하여 10진수 0 ~ 9와 영어 대문자와 특수문자를 표현

 

Zone 비트		숫자 비트 (2진수)
A	B	8	4	2	1
X	X	X	X	X	X

 

Zone 비트 A, B의 값
00	0, 1 ~ 9 (1010, 0001 ~ 1001)
01	문자 A ~ I (0001 ~ 1001)
10	문자 J ~ R (0001 ~ 1001)
11	문자 S ~ Z (0001 ~ 1001)

 

 - ASCII 코드 : 미국표준협회에서 개발한 7bit 코드, 1개의 문자를 상위 3개의 Zone 비트와 하위 4개의 Digit 비트(2진수 비트)로 표현, 128가지 표현 가능, 대, 소문자 구별 가능, 데이터 통신용 코드

Zone 비트와 2진수 비트를 조합하여 10진수 0 ~ 9와 영어 대, 소문자와 특수문자를 표현

 

Zone 비트			숫자 비트 (2진수)
			8	4	2	1
X	X	X	X	X	X	X

 

 - EBCDIC 코드 : 8bit 코드로 IBM사에서 개발, 1개의 문자를 상위 4개의 Zone 비트와 하위 4개의 Digit 비트(2진수 비트)로 표현, 256가지 표현 가능, 대형컴퓨터에서 사용되는 코드

Zone 비트와 2진수 비트를 조합하여 10진수 0 ~ 9와 영어 대, 소문자와 특수문자를 표현

 

Zone 비트				숫자 비트 (2진수)
A	B	C	D	8	4	2	1
X	X	X	X	X	X	X	X

 

Zone 비트 A, B의 값		Zone 비트 C, D의 값
00	여분	00	문자 A ~ I (0001 ~ 1001)
01	특수 문자	01	문자 J ~ R (0001 ~ 1001)
10	영어 소문자	10	문자 S ~ Z (0001 ~ 1001)
11	영어 대문자	11	0 ~ 9 (0000 ~ 1001)