[자료구조]CH1. 자료구조 소개

참조 책 : C로 배우는 쉬운 자료구조(이지영 저)

 

<section1> 자료구조의 이해

 

1. 자료구조의 개념

 사회의 정보화와 다양화로 인해 그 정보를 얼마나 효율적으로 사용하는냐가 중요한 사항이 되었다. 자료를 효율적으로 표현하고 저장하고 처리할 수 있도록 정리하는 것이 '자료구조' 이다.

 

 컴퓨터는 자료를 효과적으로 표현하고 효율적으로 저장 및 처리하기 위해서 논리적인 구조로 설계하고 분석하여 프로그램에 사용한다.

 

 자료구조는 이론적 측면에서 알고리즘을 분석하여 검색, 정렬 방법 등을 결정하고, 효울 분석을 통해 최적의 상태를 결정한다. 결정한 내용에 따라서 자료를 여러 구조로 실제적으로 표현하고 알고리즘을 구현하며, 프로그래밍과 파일 작성 및 메모리 관리와 운영체제 등에 사용한다.

 

2. 자료구조의 분류

*단순구조 : 정수, 실수, 문자, 문자열 등의 데이터 타입(Data Type)

*선형구조 : 자료 사이의 관계가 1 :1 구조. 순차리스트(Sequential List), 연결리스트(Linked List), 스택(Stack), 큐(Queue), 데크(Deque) 등이 포함된다.

*비선형구조 : 계층구조나 망 구조를 가짐. 트리(Tree)와 그래프(Graph)가 있다.

*파일구조 : 서로 관련 있는 필드로 구성된 레코드 집합인 파일에 대한 자료구조로 보조 기억 장치에 데이터가 실제로 기억되는 형태. 순차 파일, 색인 파일, 직접 파일 등이 있다.

 

<Section2> 자료의 표현

 

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

 

 자료를 표현하기 위해서는 1과 0(=On&OFF/=True&False)의 조합인 2진수 코드를 사용한다.

2진수 한 자리 단위를 비트(Bit)라고 하며(자료를 표현하는 최소 단위임), 4비트 그룹은 니블(Nibble), 8비트 그룹은 바이트(Byte)라고 한다.

10진수 한 자리를 표현하는 단위는 1바이트(=8비트)이다.

 

 컴퓨터 내부에서 표현할 수 있는 자료에는 수치 자료, 문자 자료, 논리 자료, 포인터 자료, 문자형 자료 등이 있다.

 

2. 수치 자료의 표현

 

 2.1 10진수의 표현1 : 존 형식 표현

  1바이트가 한 단위이며 상위 4비트 존 영역과 하위 4비트 수치 영역으로 구성된다.

 존 영역에는 항상 '1111' 이 입력되며 수치 영역에는 10진수를 2진수로 변환한 자리값이 입력된다.

 자릿수가 긴 10진수를 표현할 때는 한 단위의 존 형식을 표현하고자 하는 10진수의 자릿수만큼 연결하여 표현하고,

 최하위 미트의 존 영역에는 부호를 표시한다. (양수일 경우 : 1100, 음수일 경우 : 1101)

 

 2.2 10진수의 표현2 : 팩 형식 표현

  존 형식의 존 영역의 '1111'을 제외한 형식이 팩 형식이 된다. 1바이트에 10진수 두 자리를 표현하고,

 최하위 바이트의 하위 4비트에 부호를 표현한다. (양수일 경우 ; 1100, 음수일 경우 :1101)

 

 2.3 2진수의 정수 표현

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

 최상위 비트(MSB:Most Significant Bit)인 첫 번째 1비트는 부호를 표시하기 위해 사용한다. (양수 : 0, 음수 : 1)

 *부호와 절댓값 형식 : 최상위비트에 부호를 표시하고 나머지 비트에 2진수의 절댓값을 표시한다.

 *1의 보수 형식 : n비트인 음수 값을 절댓값으로 표현한 후 0은 1로 바꾸고, 1은 0으로 바꾸면 1의 보수가 된다.

 *2의 보수 형식 : 1의 보수에 1을 더하면 2의 보수가 된다.(음수의 경우)

  (양수는 위의 세 가지 형식의 모습이 부호와 절댓값 형식과 같지만, 음수의 경우는 1의 보수 형식,

   2의 보수 형식에서 위의 방법처럼 모습을 바꿔주어야 한다.)

 

 2.4 2진수의 실수 표현

  *고정소수점 표현 방식 : 소수점이 항상 최상위 비트의 왼쪽 밖에 고정되어 있거나 최하위 비트의 오른쪽 밖에

  고정되어 있다.

  *부동소수점 표현 방식 : 부호, 지수, 가수 세 영역을 사용한다.

   -정규화 : 정수부가 1이 되도록 소수점을 이동하여 과학적 표기로 변환

   -부호 : 양수는 0, 음수는 1 저장

   -가수부 : 정수부를 생략한 소수부를 저장

   -지수부 : 단정도 부동소수점 표현방식(4바이트)의 경우는 지수+127,

               배정도 부동소수점 표현방식(8바이트)의 경우는 지수+1023

 

3. 문자 자료의 표현

 3.1 BCD(Binary-Coded Decimal)코드

  6비트를 사용하며, 상위 2비트의 존비트와 하위 4비트의 숫자 비트로 구성된다.

 3.2 EBCDIC(Extended Binary-Coded Decimal Interchange Code)코드

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

 3.3 ASCII(American Standard Code for Information Interchange)코드

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

 데이터 통신용으로 사용할 때는 최상위 비트에 패리티 비트(에러검출용 비트)를 추가하여 8비트로 표현하기도 한다.

 3.4 유니코드

  국제 표준 코드

 

4. 논리 자료의 표현

 참과 거짓을 표시한 값(00000001&00000000/11111111&00000000/하나 이상의 비트가 1&00000000)

 

5. 포인터 자료의 표현

 메모리 주소를 표현하기 위한 자료 형식이다. 자료를 저장하고 있는 특정 변수나 특정 위치의 메모리 주소를 저장하며,

주소 연산을 할 때 주로 사용한다.

 

6. 문자열 자료의 표현

*구분자를 사용하여 저장 : 메모리 이용률(효율) / 부분 문자열 탐색 시간(비효율)

*고정 길이로 저장하는 방법 : 메모리 이용률(비효율) / 부분 문자열 탐색 시간(효율)

*포인터를 사용하는 방법 : 메모리 이용률(효울) / 부분 문자열 탐색 시간(효율)

 

<Section3> 자료의 추상화

 

*자료(Data) : 프로그램의 처리 대상이 되는 모든 것. 값(Value) 자체를 의미하기도 한다.

*연산(Operation) : 어떤 일을 처리하는 과정으로 연산자를 이용하여 수행된다.

*자료형(Data Type) : 자료의 집합과 연산자의 집합, 시스템 정의 자료형과 사용자 정의 자료형이 있다.

 

 자료형의 정의하려면 구체적으로 구현하기 전에 자료형에 대한 자료의 특성, 연산자, 연산자가 무엇을 수행하는지 등을 논리적으로정의해야 한다. 이런 추상화하여 정의한 자료를 추상 자료형(ADT:abstract Data Type)이라고 한다.

 

<Section4> 알고리즘의 이해

 

 알고리즘은 주어진 문제를 해결하는 방법을 추상화하여 일련의 단계적 절차를 논리적으로 기술해 놓은 명세서이다.

 

효과적인 알고리즘이 되기 위한 조건

-입력 : 필요한 자료가 외부에서 입력되어야 한다.

-출력 : 결과를 하나 이상 출력해야 한다.

-명확성 : 알고리즘의 명령어는 명확하게 명세되어야 한다.

-유한성 : 알고리즘이 수행되고 나면 반드시 종료되어야 한다.

-효과성 : 모든 명령어는 기본적이며 실행할 수 있어야 한다.

 

<Section5> 알고리즘의 표현 방법

 

1. 알고리즘의 표현 방법의 종류

* 자연어를 이용한 서술적 표현 : 사람이 쓰는 언어로 표현하는 방법

*순서도를 이용한 도식화

*프로그래밍 언어를 이용한 구체화 : 추가로 구체화 작업을 할 필요가 없지만 해당 언어를 알아야 한다.

*가상코드를 이용한 추상화 : 프로그래밍 언어의 형태를 갖춘 가상코드(Pseudo-code)를 사용한다. 구체화 작업도 쉽다.

 

2. 순서도를 이용한 도식화 : Flow Chart를 작성하는 규칙에 따라 도식화하는 방법

 

3. 가상코드를 이용한 추상화

 의사코드(Pseudo code) 또는 알고리즘 기술 언어라고도 부른다. 가상코드의 요소는 기호, 자료형, 연산자이다.

변수 ← 값  : 변수에 값을 지정하는 지정문 형식

 

 3.1 조건문

 

 *if문

 [if-then-else형]

 if(조건식) then 명령문1;

 else 명령문2;

 

 [if-then형]

 if(조건식) then 명령문1;

 

 [if중첩]

 if(조건식1) then 명령문1;

 else if(조건식2) then 명령문2;

 else 명령문3;

 

*case문

case{

   조건식1: 명령문1;

   조건식2: 명령문2;

....

   조건식n: 명령문n;

   else : 명령문 n+1;

}

 

 3.2 반복문

 

 *for문 for(초깃값;조건식;증감값) do 명령문;

 *while-do문 while(조건식) do 명령문;

 *do-while문

 do명령문;

 while (조건식);

 

 3.3 함수문

 함수 이름(매개 변수)

       명령문;

       ....

       return 결과값;

 end

 

<Section6> 알고리즘의 성능 분석

 

1. 알고리즘 성능 분석 기준 : 정확성, 명확성, 수행량, 메모리 사용량, 최적성 등으로 판단한다. 그 중 최적성이 가장 중요.

 

2. 알고리즘 성능 분석 방법

 2.1 공간 복잡도 : 필요한 고정 공간과 가변 공간을 합하여 구한다.

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

 

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

 3.1 빅-오 표기법 O(f(n)) : 함수의 상한을 나타낸다. 가장 큰 영향을 주는 항을 선택하여 계수를 생략하여 표시한다.

 3.2 빅-오메가 표기법 : 함수의 하한을 나타낸다.

 3.3 빅-세타 표기법 : 상한과 하한이 같은 정확한 차수를 표현한다.