[SOS CLASS] 자료구조기초 - 1차시

---

✅ 자료구조의 개념

: 자료를 효율적으로 표현, 저장, 처리할 수 있도록 정리하는 것

---

✅ 자료구조는 왜 배워야 하는가?

컴퓨터가 효율적으로 문제를 처리하기 위해서는 문제를 정의하고 분석하여,

그에 대한 최적의 프로그램을 작성해야 함.

---

✅ 자료의 형태에 따른 분류

 

1. 단순 구조

정수, 실수, 문자, 문자열 등의 기본 자료형

 

2. 선형 구조

- 자료들 사이의 관계가 1:1 관계

- 순차 리스트, 연결 리스트, 스택, 큐, 데크 등

ex) 부부

 

3. 비선형 구조

- 자료들 사이의 관계가 1:多 or  多:多 관계

- 트리, 그래프 등

ex) 가족 (엄마 - 자식들)

 

3. 파일 구조

- 서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조

- 순차 파일, 색인 파일, 직접 파일 등

---

✅ 컴퓨터에서의 자료 표현

2진수 코드로 모든 형식의 자료를 저장 및 처리함

 

⚡ 2진수 코드란?

0과 1, on & off, true & false의 조합

 

⚡ 2진수 코드의 단위

1) 1비트

2) 1니블 (=4비트)

3) 1바이트 (=2니블) (= 8비트)

 

⚡ n개의 비트로 2^n 개의 상태 표현 가능

1) n = 2

00(0) / 01(1) / 10(2) / 11(3)

=> 총 2^2 = 4개의 상태(0,1,2,3) 표현 가능

 

2) n = 4

0000 / 0001 / 0010 / 0011 / ... / 1111

=> 총 2^4 = 16개의 상태(0~15) 표현 가능

---

✅ 수치 자료의 표현 [10진수의 표현]

 

⚡ 존형식

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

- 존 영역 : 상위 4비트 (1111로 표현)

- 수치 영역 : 하위 4비트 (10진수 한 자리 값에 대한 2진수 값 표시)

존 영역				수치 영역
x	x	x	x	2^3	2^2	2^1	2^0

1. 여러 자리의 10진수를 표현

1) 10진수의 자릿수만큼 존 형식을 연결하여 사용

     ex) 3자리수이면 3개의 존 형식을 연결

2) 마지막 자리의 존 영역에 부호를 표시

- 양수 : 1100 = C

- 음수 : 1101 = D

 

ex) + 213

존	수치	존	수치	존	수치
1111	0010	1111	0001	1100	0011
F	2	F	1	C(+)	3

ex) - 213

존	수치	존	수치	존	수치
1111	0010	1111	0001	1101	0011
F	2	F	1	D(-)	3

 

 

⚡ 팩형식

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

- 최하위 4비트에 부호를 표시

- 양수 : 1100 = C

- 음수 : 1101 = D

 

ex) + 213

0010	0001	0011	1100
2	1	3	C(+)

 

ex) - 213

0010	0001	0011	1101
2	1	3	D(-)

---

✅ 수치 자료의 표현 [2진수의 정수 표현]

 

⚡ n비트의 부호와 절댓값 형식

1. 최상위 1비트 : 부호 표시

1) 양수(+) : 0

2) 음수(-) : 1

 

2. 나머지 n-1비트 : 2진수 표시

ex) 8비트 => +21

1비트	7비트
0(부호)	0	0	1	0	1	0	1

ex) 8비트 => -21

1비트	7비트
1(부호)	0	0	1	0	1	0	1

 

⚡ 1의 보수 형식

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

 

1. n비트의 2진수를 1의 보수로 만드는 방법

- n비트를 모두 1로 만든 이진수에서 변환하고자 하는 이진수를 뺌

 

ex) 10진수 21을 1의 보수로 만드는 방법 (1byte사용)

(21의 1의 보수 == -21)

 

1) 21 = 0001 0101 (2진수)

2) -21 = 1111 1111 - 0001 0101 = 1110 1010 (2진수)

	1	1	1	1	1	1	1	1
-	0	0	0	1	0	1	0	1	(21)
	1	1	1	0	1	0	1	0	(-21)

 

⚡ 2의 보수 형식

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

 

1. n비트의 2진수를 1의 보수로 만드는 방법

- 1의 보수에 1을 더함

 

ex) 10진수 21을 2의 보수로 만드는 방법 (1byte사용)

(21의 2의 보수 == -21)

 

1) 21의 1의 보수 = 1110 1010

2) 21의 2의 보수 = 1110 1010 + 1 = 1110 1011

	1	1	1	1	1	1	1	1
-	0	0	0	1	0	1	0	1
	1	1	1	0	1	0	1	0	1의 보수 (-21)
+								1
	1	1	1	0	1	0	1	1	2의 보수 -(21)

 

📛 2진수 정수의 세가지 표현 방법 모두 양수의 표현은 같음!

📛 음수의 표현만 다름!

---

✅ 2진수의 정수 뺄셈

 

1. n비트의 부호와 절댓값 형식

1) 16 - 8을 하는 감산기 회로 사용

2) 8 - 16의 경우 16 - 8 을 하고 그 값에 (-)부호를 붙임

 

2. 1의 보수 형식

1) 16에서 (-8)의 1의 보수를 더하는 가산기 회로 사용

2) Carry bit가 생기면 1을 더해줌

 

3. 2의 보수 형식

1) 16에서 (-8)의 2의 보수를 더하는 가산기 회로 사용

2) Carry bit가 생기면 무시함

 

📛 1의 보수 & 2의 보수 형식은 감산기 회로가 필요 ❌❌

 

---

✅ 2진수를 표현하는 세 가지 방법 비교

 

1. 부호와 절댓값 형식

: n비트로 -(2^(n-1) -1) ~ +(2^(n-1) - 1)의 범위를 표현할 수 있음

1) 장점

- MSB 값 (ex 1000 0000 에서 맨 앞의 부호를 결정하는 1)을 바꿔 음수를 간단하게 표현 가능

2) 단점

- 가산기 & 감산기 모두 필요 => 하드웨어 구성 비용 多

- 0(0000 0000)과 -0(1000 000)이 존재하므로 논리적으로 맞지 않음

 

2. 1의 보수 형식

: n비트로 -(2^(n-1) -1) ~ +(2^(n-1) - 1)의 범위를 표현할 수 있음

1) 장점

- 가산기 회로로 감산 가능 ex 16 + (-8)

2) 단점

- 0(0000 0000)과 -0(1111 1111)이 존재하므로 논리적으로 맞지 않음

 

3. 2의 보수 형식

: n비트로 -2^(n-1)  ~ +(2^(n-1) - 1)의 범위를 표현할 수 있음

1) 장점

- 1의 보수보다 한 자리 더 표현 가능함

- 가산기 회로로 감산 가능 ex 16 + (-8)

- 덧셈 연산에서 발생하는 오버플로 처리가 1의 보수 형식보다 간단함 (무시하면 됨)

- 컴퓨터에서 실제로 사용하는 형식임

---

✅ 수치 자료의 표현 [2진수의 실수 표현]

 

⚡부동 소수점 형식

ex) 213 = 0.213 X 10^3

-> 0.213 (소수부) / 10 (밑수) / 3 (지수)

 

1. 4바이트를 사용하는 단정도 부동 소수점 형식

1비트 (부호)

8비트 (지수부)

23비트 (가수부)

 

2. 8바이트를 사용하는 배정도 부동 소수점 형식

1비트 (부호)

11비트 (지수부)

52비트 (가수부)

---

✅ 2진수 실수 표현의 예

 

ex) 100010.101 을 부동 소수점 형식으로 표현한다면?

 

⚡ 방법 설명

1. 정규화 : 정수부가 1이 되도록 소수점 이동
+1.00010101 X 2^5
1) 지수 : 5

2. 부호 : 양수 = 0 / 음수 = 1

3. 가수부 : 정수부를 생략하고, 소수부(00010101)만 저장

4. 지수부 : 지수의 부호를 표현하기 위해 사용하는 '바이어스'를 더한 값 저장
-1) 단정도 : 바이어스 = 127
-2) 배정도 : 바이어스 = 1023

 

⚡ 단정도 부동소수점 표현

1. 지수부 : 5 + 127 = 132 = 10000100(2진수)

2. 부호 : 0 (양수)

3. 가수부 : 00010101

0 10000100 00010101 000000000000000

 

⚡ 배정도 부동소수점 표현

1. 지수부 : 5 + 1023 = 1028 = 10000000100(2진수)

2. 부호 : 0 (양수)

3. 가수부 : 00010101

0 10000000100 00010101 000000000000000000000000000000000000

---

✅ 오늘의 과제

SOS CLASS 자료구조기초 - 1차시 과제.hwp

0.03MB

과제 기한 : 4/1 ~ 4/7