[C로 배우는 쉬운 자료구조] 1장 개념정리

---

Chapter 1 자료구조 소개

 

01 자료구조의 이해

 

1. 자료구조의 개념

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

 

2. 자료구조의 분류

1) 단순구조 : 정수, 실수, 문자, 문자열

2) 선형구조 : 순차 리스트, 연결 리스트(단순, 이중, 원형), 스택, 큐, 데트

3) 비선형 구조 : 트리, 그래프

4) 파일 구조 : 순차 파일, 색인 파일, 직접 파일

 

 

02 자료의 표현

 

1. 컴퓨터에서의 자료 표현

- 2진수 코드 형태로 처리하고 저장한다.

* 2진수 한자리를 표현하는 단위를 bit 라고 함(4bit = 1nibble, 8bit= 1byte)

 

2. 수치 자료의 표현

1) 10진수 표현 - 존 형식 표현

- 1 바이트를 한 단위로 사용한다.

출처 : IT_Dexter :: 자료의 표현 (10진수 존형식, 팩 형식 표현, 1의 보수, 2의 보수) (tistory.com)

- 존 영역은 항상 1111을 표시하고, 수치 영역에는 표현할 10진수 한 자리 값에 대한 2 진수 값을 표현한다.

- 자릿수가 긴 10진수를 표현할때는 한 단위씩 자릿수 만큼 연결하여 사용한다. 

- 부호는 최하위 바이트의 존 영역에 표시한다. 양수면 1100 음수면 1101 

 

2) 10진수 표현 - 팩 형식 표현

- 존 형식은  존 영역에 항상 1111을 저장해야 하므로 기억 공간이 낭비된다.

- 그래서 팩 형식에서는 1바이트에 10진수 두자리를 표현한다.

- 부호는 최하위 바이트의 하위 4비트에 표현 한다.

 

ex) 양수 213 표현

> 존 형식

1111

0010(2)

1111

0001(1)

1100(+)

0011(3)

> 팩 형식

0010(2)

0001(1)

0011(3)

1100(+)

 

2. 2진수의 정수 표현

1) 부호화 절댓값 형식 : 부호를 최상위 비트에 표시하고 나머지 비트에는 2진수의 절댓값 표시

2) 1의 보수 : 양수는 부호화 절대값으로 표기, 음수는 2진수를 1의 보수로 변환하여 표현

- 1의 보수 변환 : n비트의 x를 절대값으로 표현한 값에서 0은 1로 1은 0으로 바꾸면 됨

3) 2의 보수 : 양수는 부호화 절대값 형식, 음수는 1의보수에서 1더한 값

표현 방법	특징
부호와 절댓값 형식	- 음수를 간단히 표기 가능 - 가산기와 감산기가 둘다 필요하므로 하드웨어 구성 비용up - +0과 -0 두개가 존재 - n비트로 -(2^(n-1)-1)+(2^(n-1)-1) 범위 표현 가능
1의 보수 형식	- 가산기 회로만 필요 - -0과 +0 두개 존재 - n비트로 -(2^(n-1)-1)+(2^(n-1)-1) 범위 표현 가능
2의 보수 형식	- 실제 컴퓨터에서 사용하는 형식 - 오버플로 처리가 1의 보수보다 간단 - n비트로 -2^(n-1)+(2^(n-1)-1) 범위 표현 가능

 

3. 2진수의 실수 표현

1) 고점소수점 표현방식 : 소수점이 항상 최상위 비트/최하위 비트에 고정되어 있다고 취급

2) 부동소수점 표현 방식 : 소수부와 밑수로 나누어서 표기

ⓐ 단정도 : 4바이트(32비트)표현방식

ⓑ 배정도 : 8바이트(64비트)표현방식

출처 : 단정도(single precision), 배정도(double precision)이란? (tistory.com)

- 표기 방법

① 정규화 : 정수부가 1이 되도록 소수점을 이동함

② 부호 : 양수는 0 음수는 1을 저장

③ 가수부 : 정수부를 생략한 나머지만 저장

④ 지수부 : 단정도에서는 지수+127, 배정도에서는 지수+1023을 더한 값을 저장한다. (지수+바이어스)

 

4. 문자 자료의 표현

1) BCD코드

- 6비트를 사용하며 상위 2비트의 존 비트와 하위 4비트 숫자 비트로 구성됨

2) EBCDIC 코드

- 8비트를 사용하며, 상위 4비트는 존 비트와 하위 4비트의 숫자 비트로 구성

3) ASCII 코드

- 7비트를 사용하며, 상위 3비트의 존 비트와 하위 4비트의 숫자 비트로 구성

- 데이터 통신용으로 사용할 때는 최상위 비트에 패리티 비트르 추가해 8비트 형식으로도 사용가능

4) 유니코드

- 다른 코드와 다르게 문자 코드 표에 정의되어 있지 않는 문자 표현 가능

- 2바이트를 조합하여 하나의 글자를 표현 가능함

 

 

5. 논리 자료의 표현

- 참과 거짓중 하나를 표시한 값

- 1바이트나 1워드 단위 사용 

 

6. 포인터 자료의 표현

- 포인터 자료는 메모리 주소를 표현하기 위한 자료 형식

 

7. 문자열 자료의 표현

	메모리 이용률	부분 문자열 탐색 시간
구분자를 사용	문자열 길이+구분자 길이 => 효율적	문자 비교 연산 시간+구분자 식별 시간 => 비효율적
고정 길이로 저장	가장 긴 부분 문자열 길이*부분 문자열 개수 => 비효율적	문자 비교 연산 시간 => 효율적
포인터 사용	문자열 길이+포인터 저장공간 => 효율적	문자 비교 연산 시간+포인터 주소연산 시간 => 효율적

 

03 자료의 추상화

- 추상화 : 무엇인지를 논리적으로 정의하는 것

- 구체화 : 사용을 위해 어떻게 할지를 실제적으로 표현하는 것

구분	자료	연산
추상화	추상 자료형	알고리즘 정의
구체호	자료형	프로그램 구현

 

04 알고리즘의 이해

- 주어진 문제를 해결하는 방법을 추상화하여 논리적으로 기술한 것

- 조건 : 입력, 출력, 명확성, 유한성, 효과성

 

 

05 알고리즘의 표현 방법

 

1. 종류

1) 자연어를 이용한 서술적 표현 : 사람이 쓰는 언어로 표현

2) 순서도를 이용한 도식화 : 특정 기호를 사용해 알고리즘의 실행단계 표현

3) 프로그래밍 언어를 이용한 구체화 

4) 가상코드를 이용한 추상화 : 의사코드(수도코드), 알고리즘 기술 언어라고도 함

 

 

06 알고리즘의 성능 분석

 

1. 분석 기준 : 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등

 

2. 분석 방법

1) 공간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하는 데까지 필요한 총 저장 공간

- 가변공간 + 고정공간(프로그램 저장공간, 변수/상수 저장공간) 

2) 시간 복잡도 : 알고리즘을 프로그램으로 실행하여 완료하는 데까지 소요되는 시간

- 컴파일 시간(고정) + 실행 시간

 

3. 알고리즘 성능 분석 표기법

[Algorithm] 시간복잡도 이해하기 (tistory.com)

[Algorithm] 시간복잡도 이해하기

* 정리했던 거라 링크 첨부