DevGang

1. 순차 파일(Sequential file) 생성되는 순서에 따라 레코드를 순차적으로 저장, 저장 매체의 효율이 가장 높음 프로그래밍이 쉬우며, 대화식 처리보다 일괄 처리에 적합한 구조 여러 개의 기록 매체에 기록이 가능 필요한 레코드를 삽입, 삭제하는 경우 파일을 재구성해야 하므로 파일 전체를 복사해야 함 2. 직접 파일(Direct file) 특정 레코드에 접근하기 위해서 디스크의 물리적 주소로 변환할 수 있는 함수 해싱을 이용한 파일 구조 * 직접 접근 방식(DAM : Directed Access Method) 데이터의 입/출력이 빈번히 발생하는 곳에 응용 해싱 함수를 이용하여 레코드의 저장 위치를 결정 다른 레코드를 참조하지 않고 어떤 레코드를 접근할 수 있음 3. 인덱스 순차 파일(ISAM :..

1. 파일 조직 막대한 양의 자료를 각종 매체에 저장하는 기법 파일 편성 혹은 파일 구성 방법이라 함 2. 인덱스(Index) 검색을 빠르게 하기 위해 만든 보조적인 데이터 구조 INDEX SCAN : 자격이 있는 모든 테이블이 행을 검색(INDEX가 없을 때도 검색) INDEX SEEK : INDEX가 있는 테이블을 검색할때 사용 B트리, B+트리, 트라이 등의 자료구조를 사용하여 구현함 인덱스 파일 : 검색 수를 줄이기 위해 다단계 인덱스를 사용 3. 인덱스의 특징 인덱스는 하나 이상의 필드로 만들어도 됨 인덱스를 통해서 테이블의 레코드에 대한 엑세스를 빠르게 수행 4. 트라이 (trie) 검색을 위한 키값을 직접 표현하지 않고 키를 구성하는 문자나 숫자 자체의 순서로 키값을 구성하는 구조 트라이의 ..

1. 검색기법의 종류 선형 검색 (Linear Search) : 순차 검색으로 프로그램 작성이 쉬움 제어 검색 (Control Search) : 순서화된 파일이어야 검색 가능 2. 제어 검색 - 이진 검색(binary search) 일정한 순서로 배열된 레코드를 2개 부분으로 되풀이하여 나누어서, 한 부분은 버리고 남은 부분을 검색하는 방법 자료가 반드시 정렬되어 있어야 함 - 보간(Interpolation) 검색 찾고자 하는 키가 있음 직한 위치를 추정하여 검색 - 피보나치 검색 - 블록 검색 - 이진트리 검색 3. 해싱 (Hashing) 키 값으로부터 레코드가 저장되어 있는 주소를 직접 계산하여, 산출된 주소로 바로 접근하는 방법. 키-주소 변환 방법이라고도 함 검색 방법 중 속도는 가장 빠르지만 충..

1. 내부 정렬 기법 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법 속도는 빠르나, 정렬할 자료의 양이 많은 경우 부적합 2. 내부 정렬 기법 종류 히프 정렬(heap sort) 기수 정렬(radix sort) 선택 정렬(selection sort) 버블 정렬(bubble sort) 퀵 정렬(quick sort) 삽입 정렬(insertion sort) 쉘 정렬(shell sort) 3. 외부 정렬 기법 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에, 테이프나 디스크 내에서 각 서브 파일을 합병하는 방법 속도는 느리지만 정렬하고자 하는 자료의 양이 많을 경우 효과적(보조기억장치 많이 사용) 4. 외부 정렬 기법 종류 진동 병합 정렬(oscillating merge sort)..

1. 그래프의 정의 각각의 단위 정보를 링크로 연결하여 구조화시킨 자료 구조 정점(vertex) : 노드들의 집합 간선(edge) : 정점들 사이의 상호 연결의 집합, 임의의 점들의 쌍을 연결 2. 인접 행렬 (Adjacency Matrix) 3. 인접 리스트

1. 트리의 정의 Linked List로 표현할 때 가장 효율적임 계층형 구조(hierarchical structure)를 나타내기 편리함 2. 트리의 용어 정리 Node - Tree의 기본 구성요소 (A, B, C, D, E, F, G, H) 근 노드(Root Node) - 가장 상위에 위치한 노드 (A) 레벨(Level) - 근 노드를 기준으로 특정 노드까지의 경로 길이 (E의 레벨은 3) 조상 노드(Ancestors Node) - 특정 노드에서 루트에 이르는 경로상의 모든 노드 (D의 조상 노드 B, A) 자식 노드 - 특정 노드에 연결된 다음 레벨의 노드 (B의 자식 노드 D, E) 부모 노드 - 특정 노드에 연결된 이전 레벨의 노드 (F의 부모 노드 D) 형제 노드(Sibling) - 같은 부모..

1. 큐의 정의 rear라고 하는 리스트의 한쪽 끝에서 삽입이 일어나고 front라 부르는 반대쪽 끝에서 삭제가 일어나는 자료구조(FIFO 구조) 운영체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 자료구조 2. 데큐 (Deque, Double Ended Queue) 서로 다른 방향에서 입/출력이 가능한 구조 (삽입과 삭제가 양쪽 끝에서 일어남) 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과 입력은 양쪽에서 일어나고 출력은 한 곳에서만 이루어지는 출력 제한이 있음 양 끝에서 삽입과 삭제가 가능하게 하도록 큐를 일반화한 것

1. 스택의 정의 top이라고 하는 리스트의 한쪽 끝에서만 삽입과 삭제가 일어나는 자료구조 자료의 후입 선출(LIFO) 방법 2. 스택의 용도 인터럽트의 처리 수식의 계산 (산술식 표현) 서브루틴의 복귀 번지 저장 (함수 호출의 순서 제어) 3. 순환적 프로그램을 처리하기 위함 요소 스택 복귀 주소 순환에서 탈출하는 조건

1. 리스트의 종류 선형 리스트 : 연속적 -> Array(배열) 연결 리스트 : 비연속적 -> 포인터 2. 선형 리스트(Linear List) 연속적인 기억 장소에 저장된 리스트, 순차 리스트 또는 연결 리스트(Dense List)라고 함 형태 : 임의의 노드에 접근을 할 때는 인덱스를 사용하므로 포인터가 없음 3. 선형 리스트 장점 간단한 자료구조 저장 효율이 뛰어남 (기록밀도 : 1 ) 접근 속도(Access Time)가 빠름 4. 선형 리스트 단점 삽입과 삭제가 어려움, 삽입 및 삭제 시 삽입하거나 삭제할 위치 이후의 모든 자료의 이동이 필요 5. 연결 리스트(linked list) 자료들을 임의의 기억공간에 기억시키고, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료구..

1. 자료구조의 정의 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료간의 관계, 처리 방법 등 연구 분석 하는 것 자료의 표현과 그것과 관련된 연산 일련의 자료들을 조직하고 구조화하는 것 자료 구조에 따라 프로그램 실행시간이 달라진다 2. 자료구조의 분류