2과목 -1 (필기 개념 정리)

 

1. 자료 구조의 분류

(1)선형 구조 (Linear Structure)

- 배열

- 선형리스트 -> 연속 리스트, 연결 리스트

- 스택

- 큐

- 데크

 

(2) 비선형 구조 (Non-Linear Structure)

- 트리

- 그래프

 

 

 

2. 선형 리스트(Linear List)

(1) 연속 리스트(Contiguous List)

 

 

(2) 연결 리스트(Linked List)

- 자료들을 반드시 연속적으로 배열시키 지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결 시킨 자료 구조이다.

- 노드의 삽입·삭제 작업이 용이하다.

- 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.

- 연결을 위한 링크(포인터) 부분이 필요 하기 때문에 순차 리스트에 비해 기억 공간의 이용 효 율이 좋지 않다.

- 연결을 위한 포인터를 찾는 시간이 필요 하기 때문에 접근 속도가 느리다.

- 중간 노드 연결이 끊어지면 그 다음 노 드를 찾기 힘들다

 

---

 

2. 방향/무방향 그래프의 최대 간선 수

(1) n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수 는 n(n-1)/2이고, 방향 그래프에서 최대 간선 수는 n(n- 1)이다. 

 

 

 

3. 트리의 개요

(1) 노드(Node) : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지(Branch)를 합친 것

(2) 근 노드(Root Node) : 트리의 맨 위에 있는 노드 

(3) 디그리(Degree, 차수) : 각 노드에서 뻗어 나온 가지의 수

(4) 단말 노드(Terminal Node) = 잎 노드(Leaf Node) : 자식 이 하나도 없는 노드, 즉 디그리가 0인 노드

 

 

 

---

 

1. 트리의 운행법

 

 

(1) Preorder 운행 : Root → Left → Right 순으로 운행. A, B, C
(2) Inorder 운행 : Left → Root → Right 순으로 운행. B, A, C
(3) Postorder 운행 : Left → Right → Root 순으로 운행. B, C, A

 

 

 

 

 

2. 수식의 표기법 

 

(1) 전위 표기법(PreFix) : 연산자 → Left → Right, +AB
(2) 중위 표기법(InFix) : Left → 연산자 → Right, A+B
(3) 후위 표기법(PostFix) : Left → Right → 연산자, AB+

 

 

 

---

 

 

1. 퀵 정렬(Quick Sort)

(1) 레코드의 많은 자료 이동을 없애고 하나의 파일 을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기 준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분 해시키는 방식으로 정렬한다.

(2) 분할(Divide)과 정복(Conquer)을 통해 자료를 정렬한다

(3) 평균 수행 시간 복잡도는 O(nlog2n)이고, 최악의 수행 시간 복잡도는 O(n2)이다.

 

 

 

 

2. 힙 정렬(Heap Sort)

(1) 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식이다.

(2) 구성된 전이진 트리를 Heap Tree로 변환하여 정렬한다.
(3) 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.

 

 

 

3. 2-Way 합병 정렬

(1) 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다. 

(2) 평균과 최악 모두 시간 복잡도는 O(nlog2n)이다.

 

 

 

4. 이분 검색

(1) 이진 검색, Binary Search)은 전체 파일을 두 개의 서브파일로 분리해 가면서 Key 레코드를 검색하는 방식이다.

(2) 이분 검색은 반드시 순서화된 파일이어야 검색할 수 있다.

(3) 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색한다.

(4) 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간 이 적게 소요된다

 

---

 

1. 해싱 함수 (Hashing Function)

(1) 제산법(Division) : 레코드 키(K)를 해시표(Hash Table) 의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, 즉 h(K) = K mod Q임

(2) 제곱법(Mid-Square) : 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식

 

(3) 폴딩법(Folding) : 레코드 키 값(K)을 여러 부분으로 나 눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식

 

(4) 기수 변환법(Radix) : 키 숫자의 진수를 다른 진수로 변 환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시

주소 범위에 맞게 조정하는 방법

 

(5) 대수적 코딩법(Algebraic Coding) : 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나 누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식

 

(6) 숫자 분석법(Digit Analysis, 계수 분석법) : 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만 큼 택해서 홈 주소로 삼는 방식

 

(7) 무작위법(Random)

 

 

 

 

2. DBMS(DataBase Management System; 데이터베이스 관리 시스템)

(1) DBMS의 필수 기능

- 정의 기능

 

- 조작 기능

 

- 제어 기능

 

 

 

 

3. 스키마

(1) 데이터베이스의 구조와 제약 조건에 관한 전반적인 명세(Specification)를 기술(Description) 한 메타데이터(Meta-Data)의 집합이다.

 

(2) 외부 스키마 : 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것

 

(3) 개념 스키마 : 데이터베이스의 전체적인 논리적 구조로서, 모든 응용 프 로그램이나 사용자들이 필요로 하는 데이터를 종합한 조 직 전체의 데이터베이스로 하나만 존재함

 

(4) 내부 스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조로서, 실제로 데이터베이스에 저장될 레코드의 형식을 정의하 고 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타냄