[71] 자료구조 01차시 자료구조와 분류

1. 자료구조의 개요와 정의

가. 자료구조란?

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

컴퓨터에 자료를 효과적으로 표현하고 표현한 자료를 좀 더 효율적으로 저장하고 처리할 수 있도록 논리적인 구조를 만들어 프로그램적으로 처리하는 것

정보의 홍수로 부를 만큼 자료가 방대해 지면서 "자료를 얼마나 많이 가지고 있느냐?" 보다 "얼마나 효율적으로 잘 사용하는지가?" 중요함.

나. 자료구조를 배워야하는 이유

컴퓨터가 자료를 효율적으로 처리하려면 문제도출과 문제 변환 단계에서 문제를 자료구조 측면에서 분석하고 구성해야 함.

프로그래머는 문제를 더 효율적이고 효과적으로 해결하기 위해 문제를 정의하고 분석하여 효율적으로 문제를 처리하기 위해 처리방식을 결정하여 알고리즘을 작성하고 자료를 정의해서 그에 대한 최적의 프로그램을 작성해야 함.

이러한 과정에서 자료구조의 개념을 이해하고 이를 활용하는 능력이 필요함.

다. 자료구조의 내용

자료구조는 이론적 측면, 효율적 측면, 실제적인 측면에서 응용을 모두 다루어야 함.

2. 자료구조의 분류

가. 자료의 형태에 따른 분류

표현할 자료의 특성과 주된 사용 방법, 수행하는 연산의 특성, 구현에 필요한 저장 공간 용량과 실행 소요 시간 등을 고려하여 가장 효율적인 자료구조를 선택해야 함.

1) 단순 구조

자료 값을 사용하기 위한 기본 형태

프로그래밍 언어에서 제공하는 정수, 실수, 문자, 문자열 등의 데이터 타입에 해당함.

2) 선형 구조

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

순차 리스트, 연결 리스트, 스택, 큐, 데크 등이 있음.

순차 리스트는 자료의 논리적인 순서와 기억장소에 저장되는 물리적 순서가 일치하는 구조

연결 리스트는 물리적인 순서와 상관없이 포인터를 사용하여 논리적인 순서대로 연결하는 구조

스택, 큐, 데크는 자료의 삽입이나 삭제 위치에 대한 제한 조건이 있는 리스트

3) 비선형 구조

자료들 사이의 관계가 1:다 또는 다:다 관계

계층구조나 망구조를 갖는 자료구조로 트리, 그래프 등이 있음.

4) 파일 구조

서로 관련 있는 필드로 구성된 레코드의 집합인 파일에 대한 구조로 보조기억장치에 데이터가 실제 기록되는 형태

파일 구성 방식에 따라 순차 파일, 색인 파일, 직접 파일 등이 있음.

3. 디지털 표현 방법 - 수치 자료표현

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

컴퓨터는 자료를 표현하기 위해 1과 0의 조합으로 구성되는 2진수 코드를 사용함.

숫자, 문자, 그림, 소리, 기호 등 자료의 형식이 아무리 다양해도 컴퓨터 내부에서는 오직 1과 0을 조합한 2진수 코드 형태로 모든 형식의 자료를 표현하고 저장 및 처리함.

2진수 코드 = 비트(bit) 단위

1과 0, On과 Off, 참(True)과 거짓(False)의 조합

한 자리에서 나타낼 수 있는 숫자를 1 또는 0으로 표현하는 단위로 bit라고 함.

\(n\)개의 비트로 \(2^{n}\)개의 상태 표현

나. 컴퓨터 내부에서 표현할 수 있는 자료의 종류

수치자료, 문자자료, 논리자료, 포인터 자료, 문자열 자료 등이 있음.

이 모든 자료는 1과 0의 조합인 2진수로 표현

다. 수치 자료의 표현

컴퓨터가 자료를 표현할 때 쓰는 2진수와 우리가 실생활에서 쓰는 10진수는 형태가 다르기 때문에 2진수로 쓰여진 자료 값을 보면 이해하거나 쓰기 어렵다고 느낄 수 있음.

그래서 2진수 형태이지만 10진수로 쉽게 해석할 수 있도록 만든 존(Zone) 형식과 팩(Pack) 형식이 있음.

https://ko.wikipedia.org/wiki/이진화_십진법

이진화 십진법 - 위키백과, 우리 모두의 백과사전

1) 존(Zone) 형식 표현

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

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

마지막 자리의 존 영역에 부호를 표시(양수: 1100, 음수: 1101)

2) 팩(Pack) 형식 표현

숫자만 사용하는 10진수 연산에서 존 형식을 사용하면 부호를 표시하는 최하위 바이트의 존 영역을 제외한 나머지 존 영역은 항상 1111을 저장해야 하므로 기억공간이 낭비되고 처리가 지연되는데 이러한 문제를 해결한 것이 팩 형식

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

최하위 4비트에 부호를 표시(양수: 1100, 음수:1101)

3) 2진수의 정수 표현

2진수는 일정한 길이의 n비트로 표현

실생활에서 사용하는 정수는 음수 양수를 표현하기 위해 -와 +와 같은 부호를 사용하지만 컴퓨터는 자료를 표현할 때 2진수만 사용하기 때문에 음수와 양수를 표현하기 위해 부호가 아닌 2진수 형태를 사용함.

2진수를 정수로 표현하는 방법으로는 "부호를 어떻게 표현하느냐?"에 따라 부호와 절대값 형식, 1의 보수 형식, 2의 보수 형식으로 구분됨.

부호와 절대값 형식: 최상위 1비트에 부호 표시(양수: 0, 음수: 1)하고 나머지 n-1 비트에 이진수 값을 표시

1의 보수 형식: 양수를 1의 보수로 바꾸어 음수로 사용하는 방법

1의 보수로 바꾸는 방법은 0은 1로 1은 0으로 바꾸면 됨.

2의 보수 형식: 양수를 2의 보수로 바꾸어 음수로 사용하는 방법

2의 보수로 바꾸는 방법은 1의 보수에 1을 더하면 됨.

실제 컴퓨터 시스템에서는 2의 보수 형식을 사용

4) 2진수의 실수 표현

실수는 정수부와 소수부 사이에 소수점이 있는 숫자

컴퓨터는 2진수만으로 실수를 표현해야 하므로 소수점을 직접 표현하지 못하고 정수부와 실수부의 위치를 정의하여 실수를 표현

고정소수점 표현 방식: 소수점 위치가 항상 같은 자리(최상위 비트의 왼쪽)로 고정

부동소수점 표현 방식: 소수점 위치가 변함.

부동소수점 형식이 고정 소수점 형식에 비해서 표현 가능한 값의 범위가 넓음.

현재 컴퓨터에서는 실수를 표현할 때 IEEE 754 표준표기방식에 따른 부동소수점 표현 방식을 사용

https://ko.wikipedia.org/wiki/고정소수점

고정소수점 - 위키백과, 우리 모두의 백과사전

https://ko.wikipedia.org/wiki/부동소수점

부동소수점 - 위키백과, 우리 모두의 백과사전