정처기 3과목: 자료 구조
1. 자료 구조
1) 분류
- 선형구조: 리스트(선형/연결), 스택, 큐, 데크
- 비선형 구조: 트리, 그래프
2) 활용
- 정렬, 검색, 인덱스, 파일 편성
- 인덱스: 인덱스 생성 시 CREATE, 삭제 시 DROP 문을 사용
2. 선형 자료 구조
1) 리스트
- 선형 리스트: 데이터 항목을 추가/삭제하는 것이 불편, 연속적인 기억 공간
- 연결 리스트: 노드 포인터로 연결하여 삽입/삭제 용이, 연속적이지 않아도 됨, 기억 공간 많이 소요
2) 스택
- 한쪽 끝에서만 삽입/삭제, 후입선출(LIFO, Last In First Out)
- 스택 가드: 메모리상에서 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장해 두었다가 그 값이 변경되었을 경우 오버플로우 상태로 가정하여 프로그램 실행을 중단하는 기술
- 응용 분야: 인터럽트 처리, 수식의 계산, 0-주소 지정 방식, 재귀호출, 후위 표현의 연산, 깊이 우선 탐색
3) 큐
- 한쪽 끝에서 삽입, 다른 쪽 끝에서 삭제
- 선입선출(FIFO, First In First Out)
- 응용 분야: 운영체제의 작업 스케줄링 등
4) 데크
- 양쪽 끝에서 삽입/삭제, 두 개의 포인터 사용, 스택+큐 형태
- 입력 제한 데크를 Scroll, 출력 제한 데크를 Shelf라고 함
3. 트리
- 그래프의 특수한 형태로써 노드와 가지를 이용하여 사이클을 이루지 않도록 구성한 자료 구조
1) 이진 트리의 구조
- 이진 트리: 차수(degree)가 2 이하인 노드들로만 구성된 트리
- 차수: 어떤 노드에 연결된 자식 노드의 수
- 정이진 트리(Full Binary Tree): 모두 2개씩 채워짐
- 완전 이진 트리(Complete Binary Tree): 정이진 트리에서 마지막 레벨에서 왼쪽 부터 단말 노드를 채우는 트리
- 사향 이진 트리(Skewed Binary Tree): 근노드로부터 한쪽 방향으로 기울어진 트리
2) 이진 트리의 운행법
- 전위(Preorder) 운행: Root - Left - Right
- 중위(Inorder) 운행: Left - Root - Right
- 후위(Postorder) 운행: Left - Right - Root
3) 수식의 표기법
- 전위(Prefix) 표기법: + A B
- 중위(Infix) 표기법: A + B
- 후위(Postfix) 표기법: A B +
4. 그래프
- 정점(Vertex)과 간선(Edge)의 집합으로 이루어지는 자료구조
- 표현 방법: 인접 행렬(Adjacency Matrix)
- n개 노드 무방향 그래프 최대 간선 수: n(n-1)/2
- 제어 흐름 그래프에서 순환 복잡도: V(G) = E(화살표 수) - N(노드 수) + 2
5. 내부 정렬
1) 삽입 정렬(Insertion Sort)
- 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬
2) 버블 정렬(Bubble Sort)
- 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법
3) 선택 정렬(Selection Sort)
- n개의 레코드 중에서 최소값(또는 최대값)을 찾아 1st 레코드 위치에 놓고, 나머지 (n-1) 개의 레코드 중에서 최소값(또는 최대값)을 찾아 2nd 레코드 위치에 놓는 방법을 반복하여 정렬하는 방법
4) 병합(합병) 정렬(2-Way Merge Sort)
- 두 개의 키들을 한 쌍으로 하여 각 쌍에 대해 순서를 정함
5) 퀵 정렬(Quick Sort)
- 분할 정복에 기반한 알고리즘
- 레코드드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법
- 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽에 모이도록 서로 교환시키는 부분 교환 정렬법
6) 힙 정렬(Heap Sort)
- 완전이진 트리 이용
- 정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법
6. 검색
1) 이분 검색(Binary Search, 이진 검색)
- 자료가 순차적으로 정렬되어 있어야 함
- 탐색 효율이 좋고 시간이 적게 소요
- 비료를 거듭할 때마다 데이터 수가 절반으로 줄어듦
2) 선형 검색(Linear Search)
- 첫번째 레코드부터 순차적으로 비교하는 가장 간단한 방법, 데이터 정렬 필요 없음
- n개의 입력 자료에 대해 평균적으로 (n+1)/2번 비교해야 하므로 비효율적
3) 피보나치 검색(Fibonacci Search)
- 이진 검색과 비슷, 비교 대상 기준을 피보나치 수열로 결정
4) 그 외: 블록 검색(Block Search), 이진 트리 검색(Binary Tree Search)
7. 해싱
1) 정의
- 해싱 함수 이용, 해시 테이블 내의 홈주소를 계산하여 주어진 레코드에 접근
- 직접 접근 파일 구성 시 사용
- 속도 가장 빠르나 충돌 시 오버플로 부담 가중, 많은 기억 공간 요함
2) 종류
- 제산 방법(Division Method): 키값을 양의 정수인 소수로 나누어 나머지를 홈주소로 취함
- 중간 제곱 방법(Mid-Square Method): 키값을 제곱하고 그 중간 부분의 값을 주소로 계산
- 중첩 방법(Folding Method): 키를 여러 부분으로 나누고 각 부분의 값을 더하거나 배타적 논리합(XOR) 연산을 통하여 나온 결과
- 기수 변환 방법(Radix Conversion Method): 어떤 진법으로 표현된 주어진 레코드 키값을 다른 진법으로 간주하고 키값을 변환
- 계수 분석 방법(Digit Analysis Method): 키를 구성하는 자릿수들의 분포를 조사하여 비교적 고른 분포를 보이는 자릿수들을 필요한 만큼 택함
3) 오버플로 해결 방법
- 선형 개방 주소법(Linear Open Addressing): 저장 데이터 적을 떄 유리
- 폐쇄 주소 방법(Closed Addressing): 버킷 내에
연결리스트 할당
- 재해싱: 새로운 해시 함수 적용
4) 관련 용어
- 동의어(Synonym): 동일한 홈주소로 인하여 충돌이 일어난 레코드들의 집합
- 슬롯(Slot): 한 개의 레코드를 저장할 수 있는 공간, 슬롯이 모여 버킷 형성
- 충돌(Collision): 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것
8. 인덱스 구조와 파일 편성
1) 인덱스
- 데이터 베이스의 물리적 구조와 밀접한 관계
- 구성 방법: B 트리(Balanced Tree), B+ 트리, 트라이(Trie 색인)
2) 파일 편성 방법
- 순차 파일(Sequential File)
- 색인 순차 파일(ISAM: Indexed Sequential Access Method): 기본 영역, 색인 영역(트랙/실린더/마스터 인덱스), 오버플로 영역
- VSAM 파일(Virtual Storage Access Method File)
- 직접 파일(Direct File)
- 역파일(Inverted File)
3) 정적 인덱싱과 동적 인덱싱
- 정적 인덱싱: 색인 순차 파일 방식이 대표적, 인덱스 구조가 정적으로 변하지 않음
- 동적 인덱싱: 가상 기억 접근 방식이 대표적, 미리 빈 공간 준비, 레코드가 가득 차면 동적으로 분열