자료구조/수업2017. 4. 24. 03:27
수치데이터의 표현

- 수치데이터

- 프로그램 실행 중에 덧셈, 뺄셈, 곱셈, 나눗셈 등의 사칙연산이 가능한 자료

- 컴퓨터 내부에서 계산의 용도로 사용

- 컴퓨터 내부에서 2진수(binary number) 형태로 표현


10진 데이터 형식

- 존 10진수(zoned decimal 또는 unpacked)형식

- 10진수의 각 자리수를 8개의 비트로 표현

- 왼쪽 4개의 비트를 존 비트(zoned bit)

오른쪽 4개의 비트는 디지트(digit bit)로 사용


- 팩 10진수(packed decimal)형식

- 10진수를 표현된 정수의 각 자리수를 4자리의 2진수로 표현

- 가장 오른쪽(최하위 바이트)에 있는 4개의 비트를 부호 비트로 사용

- 표현하고자 하는 수가 양수이면 1100(C), 음수는 1101(D), 부호가 없으면 1111(F)로 표시

- 팩 10진수 형식은 최하위 한 바이트를 제외한 나머지 1바이트에 두 개의 10진수를 표현


- 고정 소수점 형식(fixed point data format)

- 정수를 표현하는 형식으로서, 소수점의 위치가 오른쪽 끝에 고정되어 있다고 가정

- 2바이트로 표현되는 단정도형(half word)과 4바이트로 표현되는 장정수형(full word)이 있음

- 고정소수점 표현 방식


- 고정 소수점 형식에서 음수를 표현하는 방법

- 부호와 절대값(signed magnitude)에 의한 표현

- 부호비트와 그 크기를 나타내는 절대값으로 구성하는 방식


- 1의 보수 표현(signed 1's complement)

- 양의 정수는 부호와 절대값 방식이 동일하나, 음의 정수의 경우에는 정수를 1의 보수로 변환하여 표현

- 1의 보수는 모든 2진 비트에 대해 0은 1로, 1은 0으로 바꾸어 주면된다.

- 장점

보수를 계산하기 쉽다.

- 단점

- 두 수의 합산 시 자리올림(carry)을 처리하는 과정이 필요하다.

그러므로 연산 속도가 2의 보수보다 느리게 된다.


- 2의 보수 표현(signed 2's complement)

- 양의 정수는 부호와 절대값 방식과 동일하나 음의 정수의 경우에는 2의 보수로 변환하여 표현한다.

- 2의 보수는 1의 보수에 1을 더한 값


=================================================================================

부동 소수점 방식(floating point method)

- 소수점이 포함된 실수를 표현하는 방식

- 종류

- 4바이트로 표현되는 단정도 실수형 표현 방식

- 8바이트로 표현되는 장정도 실수형 데이터 표현 방식


실수를 부동 소수점 방식으로 변경하는 절차

- 주어진 수를 16진수로 바꾼다

- 16진수로 바뀐 수를 지수 부분과 가수부분으로 분리한다(정규화한다).

- 계산된 지루 값을 기본 바이어스(bias) (40)16에 더한다.

결과값은 16진수로 변환하여 가수 부분에 기술한다.


Posted by 멜데스
자료구조/수업2017. 4. 24. 03:13

1. 자료구조의 개요

1-1. 자료와 정보와의 관계

자료(Data)

- 현실 세계로부터 단순한 관찰, 측정 등을 통하여 수집한 사실(facts)들 또는 값(values)

- 즉, 숫자로 표현되는 수치, 스트링(string)등의 정리되지 않은 자료를 의미


정보(infomation)

- 어떤 기준에 의해 처리되고 기록된 자료라는 의미

- 문자나 숫자 또는 이의 조합으로 이루어진 기호 등의 컴퓨터가 처리 하는 값

- 어떤 상황에 관한 의사결정(decision making)을 할 수 있게 하는 지식(knowledge)으로서 자료의 유효한 해석이나 자료 상호간의

관계를 말함

- 자료를 처리.가공한 결과

알고리즘

|

자료    ----------->     처리기      ------------>     정보

자료의 입력         특정한 상황에 필요한 정보의 산출


==================================================================================

자료구조의 정의

- 컴퓨터의 기억 장치 내에 자료의 표현 방법, 저장 방식, 한 집단을 구성하는 자료 항목(data item)간의 관계를 파악하여

여러 작업을 수행하기 위한 알고리즘(algorithm)을 연구하는 이론


자료구조를 선택할 때 프로그래머가 처하게 되는 문제점

- 처리 시간이 약간 늦더라도 적은 양의 기억 공간을 차지하는 프로그램을 작성할 것인가?

- 많은 양의 기억 공간을 차지하기는 하지만 처리 결과가 빠르게 나오는 프로그램을 작성할 것인가?


자료구조를 선택할 때 고려사항

- 포함된 자료의 양

- 자료의 사용빈도 및 방법

- 자료의 성질(자료가 동적인가, 정적인가)

- 구현에 필요한 기억 장소의 양

- 접근 시간(access time : 기억장치에서 데이터를 저장하거나 꺼내는데 걸리는 시간)

- 프로그램 작성의 용이성


자료구조의 정의

- 그래프의 정의

- 정점(vertex)이라고 불리는 원소들의 집합 V와 간선(edges)이라 불리는 V의 원소들의 비순서화된 쌍들의 집합 E로 구성

- V는 공집합이 아닌 정점들의 유한 집합

- E는 간선, 즉 연결선의 집합

- V(G)는 그래프의 정점의 집합

- E(G)는 그래프의 간선의 집합


탐색이란?

레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업

- 탐색의 종류

- 내부 탐색(internal search)

- 주 기억 공간 내에 저장된 파일로부터 필요한 자료를 찾아내는 것

- 외부 탐색(external search)

- 보조 기억 공간 내에 저장된 파일로부터 필요한 자료를 찾아내는 것

- 탐색의 방법

- 비교 탐색 방법(Comparison search method)

- 파일 내의 레코드의 키를 비교하여 특정한 자료를 찾는 방법

1. 순차탐색(Linear Search)

2. 제어탐색(control search) - a. 이진탐색 b. 피보나치 탐색 c. 보간 탐색

3. 블록탐색

4. 이진 트리 탐색

- 직접 탐색 방법

- 주어진 키 자체의 계수적 성질을 이용하여 파일로부터 특정한 자료를 찾는 방법

1. 해싱 방법


정렬이란?

- 일련의 자료들을 필요에 따라 자료 중에 포함된 몇 가지 항목을 우선 순서대로 지정하면 그 순서에 따라 모든 자료를

배열하는 방법


- 각 레코드의 특정한 항목을 정렬키(key)로 정하고, 키 값에 따라 오름차순, 내림차순으로 파일의 레코드를 재배열하는 것


정렬장소에 따른 구분

- 내부 정렬(internal sort)

- 파일의 크기, 처리해야 할 자료의 양이 적을 경우 자료 이동 속도가 빠른 주 기억장치 내에 로드하여 재배열을 완료시키는 것

- 외부 정렬(external sort)

- 정렬하는 파일의 크기가 주기억 장치의 크기만으로 감당하기 어려울 때 파일 전체를 기억 장소에 로드 할 수 없기 때문에 보조

기억 장치(auxiliary memory)를 이용하여 정렬하는 것


처리 순서에 따른 구분

- 오름차순 정렬(ascending sort)

- 지정된 정렬키를 작은 것에서부터 큰 것 순서로 정렬하는 것

- 사전식 정렬


- 내림차순 정렬(descending sort)

- 지정된 정렬키를 큰 것에서부터 작은 순서로 정렬하는 것


정렬 방식에 따른 구분(정렬 알고리즘에 따른 구분 방법)

- 비교식 정렬

- 비교하고자 하는 각 레코드의 키 값들을 한 번에 두 개씩 비교, 교환하여 정렬하는 방법

- insertion sort, bubble sort, shell sort, quick sort, 2-way, merge sort, heap sort


- 분산식 정렬(distributive sort)

- 레코드의 키 값을 기준으로 전체 레코드 집합을 다수의 부분 집합으로 분해하는데, 한 부분 집합에 속한 킷값은 다른 부분 집합에 속한

레코드의 키값과 다르게 만들어진다. 즉 내용들을 한 비트씩 검토함으로써 정렬하는 방법의 키값과 다르게 만든다. 즉, 내용들을 한

비트씩 검토함으로써 정렬하는 방법

- radix sort, radix exchange sort(=binary sort)


- 주소 계산 정렬(address calculation sort)

- 비교하고자 하는 키 값을 주소로 변환하여 정렬하는 방식


정렬방식 분류

- 삽입법 : insertion sort, shell sort

- 교환법 : bubble sort, quick sort, selection sort

- 선택법 : heap sort

- 병합법 : 2-way merge sort

- 분배법 : radix sort, radix exchange sort


정렬 알고리즘을 선택할 때 고려해야 할 사항

- 사용하는 컴퓨터의 특성

- 정렬할 데이터 양

- 초기 데이터의 배열 상태

- 키 값들의 분포 상태

- 소요 공간 및 작업 시간


문자열(string)이란?

- 서로 인접합 기억 장소에 존재하는 문자들의 집합


종류

- 널 스트링(null string)

- 한 개의 문자도 갖지 않는 길이가 0인 스트링


- 공백 스트링(blank string)

- 길이가 0이 아닌 공백 문자(blank character)를 갖는 스트링


- 서브 스트링(substring)

- 스트링을 구성하는 연속적인 부분의 일부를 뜻하는 스트링


리스트(List)란?

- 선형리스트(linear list)

- 기억장소에 각 원소들이 연속적으로 나타나며, 리스트 시작으로부터 상대적으로 위치를 계산할 수 있으므로

임의의 노드에 접근 가능한 구조


- 연결리스트(linked list)

- 리스트 내의 모든 노드가 다음 노드의 위치를 가리키기 위한 포인터 소유

- 노드의 구성


연결리스트의 장.단점

- 장점

- 노드의 삽입, 삭제가 용이

- 연속적인 기억공간이 없어도 저장 가능


- 단점

- 링크 필드를 위한 추가 공간이 필요

- 알고리즘 구현이 복잡

- 노드 검색시 무한 루프에 빠질 수 있다.


트리란?

- 트리의 정의

- 트리는 자료의 항목(node)들이 가지(edge)로 연결될 수 있게 자료가 조직되는 것

- 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 의미

- 조건1. T의 원소 중 들어오는 가지가 없는 단 하나의 노드 즉, 근 노드(root node)라 불리는 특정한 1개의 노드가 존재

- 조건2. 근 노드를 제외한 나무지 노드들은 서로 분리된 부분 집합 T1, T2.....Tn으로 나누어 질 수 있으며 T1, T2, T3...은

각각 트리가 될 수 있으며, 이것을 특별히 서브트리(subtree)라 한다.

- 각 노드들 간에 순환(cycle)을 허용하지 않는다.


파일(File)이란

- 어떤 목적을 위해서 수집한 데이터의 조직적인 그룹

- 수집한 데이터를 체계적으로 정리한 것

ex) 회사나 기관에서 사용하는 임금지불 전표나 장부

- 인사 파일 : 종업원의 인사 기록을 모은 파일

- 재고 파일 : 상품의 재고 현황을 정리한 파일

Posted by 멜데스
자료구조/수업2017. 4. 24. 02:47
  • 자료구조의 기본 개념 및 자료의 표현(수치데이터의 표현, 비수치데이터의 표현)방법에 대해 설명할 수 있다.
  • 포인터(pointer)자료와 문자열(string)의 데이터 표현방법에 대해 설명할 수 있다.
  • 스택(Stack), 큐(Queue), 트리(Tree) 및 그래프의 운행과 응용문제 해결방법에 대해 설명할 수 있다.
  • 자료구조와 알고리즘의 연관성에 대해 설명할 수 있다.
  • 배열과 집합, 큐(Queue)와 스택(Stack), 연결리스트(선형, 연결, 원형 연결, 다중연결), 트리(Tree), 그래프(Graph), 탐색(Search), 정렬(Sort), 파일(File) 등을 학습하고 설명할 수 있다.


Posted by 멜데스