정보처리기사 내 자료구조 내용

* 자료구조의 분류

- 선형 구조 : 선형 리스트(배열), 연결 리스트, 스택, 큐, 데크

- 비선형 구조 : 트리, 그래프

* 연결리스트

- 자료들을 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조

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

- 기억공간이 연속적이지 않아도 저장 가능

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

- 접근 속도가 느림

* 스택

- 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조

- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리한다

- TOP/Bottom/PUSH/POP

* 스택의 용도

- 부프로그램 호출 시 복귀주솔르 저장할 때

- 함수 호출의 순서 제어

- 인터럽트가 발생하여 복귀주소를 저장할 때

- 후위 표기법으로 표현된 산술식을 연산할 때

- 0 주소 지정방식 명령어의 자료 저장소

- 재귀 프로그램의 순서 제어

- 컴파일러를 이용한 언어 번역 시

* 큐

- 선형 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료구조

- 시작과 끝을 표시하는 두 개의 포인터 존재

- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO) 방식으로 처리

- Front 포인터 : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터, 삭제 작업을 할 때 사용

- Rear 포인터 : 가장 마지막에 삽입된 자료가 위치한 기억장소를 가리키는 포인터, 삽입 삭제를 할 때 사용

* 큐의 이용 예

- 서비스 순서를 기다리는 등의 대기 행렬의 처리에 사용

- 운영체제의 작업 스케줄링에 사용

* 데크

- 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조

- Double Ended Queue의 약자

- Stack과 Queue의 장점만 따서 구성한 것

- 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과 Scroll

   입력은 양쪽에서 일어나고 출력은 한쪽에서만 이루어지는 출력 제한이 있다 Shelf

* 트리

- 정점(노드)와 선분(가지)을 이용하여 사이클을 이루지 않도록 구성한 Graph의 특수한 형태

- 가족의 족보, 연산 수식, 회사 조직 구조도, 히프(Heap) 등을 표현하기 적합

* 이진트리의 운행법

- 전위 운행 Preorder : Root -> Left -> Right

- 중위 운행 Inorder : Left -> Root -> Right

- 후위 운행 Postorder : Left - >Right -> Root

* 수식의 표기법도 동일 : 전위 표기법, 중위 표기법, 후위 표기법

* 정렬

- 파일을 구성하는 각 레코드들을 특정 키 항목을 기준으로 오름차순 또는 내림차순으로 재배열하는 작업

* 내부 정렬

- 소량의 데이터를 주기억장치에만 기억시켜서 정렬하는 방식

ex) 히프 정렬, 삽입 정렬, 셀 정렬, 버블 정렬, 선택 정렬, 퀵 정렬, 2-Way Merge 정렬, 기수 정렬

* 외부 정렬

- 대량의 데이터를 보조기억장치에 기억시켜서 정렬하는 방식. 대부분 병합 정렬 기법으로 처리

ex) 밸런스 병합 정렬, 캐스케이드 병합 정렬, 폴리파즈 병합 정렬, 오실레이팅 병합 정렬

* 삽입 정렬

* 버블 정렬

* 선택 정렬

(따로 정리)

* 해싱 Hasing

- 해시 테이블이라는 기억공간을 할당하고, 해시 함수를 이용해 레코드 키에 대한 해시 테이블 내의 Home Address를 계산한 후 주어진 레코드를 해당 기억장소에 저장하거나 검색 작업을 수행하는 방식

- 여러 가지 검색 방식 중 검색 속도가 가장 빠름

- 삽입, 삭제 작업의 빈도가 많을 때 유리한 방식

* 해시 테이블

- 레코드를 1개 이상 보관할 수 있는 Home Bucket 들로 구성한 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억 장치에 구성할 수도 있다

* 순차 파일 = 순서 파일

- 입력되는 데이터들을 논리적인 순서에 따라 물리적 연속 공간에 순차적으로 기록하는 방식

- 주로 순차 접근이 가능한 자기 테이프에서 사용

* 순차 파일의 장점

- 기록 밀도가 높아 기억공간을 효율적으로 사용할 수 있음

- 레코드가 키 순서대로 편성되어 취급이 용이

- 매체 변환이 쉬워 어떠한 매체에도 적용할 수 있음

- 레코드를 기록할 때 사용한 키 순서대로 레코드를 처리하는 경우, 처리 속도가 빠름

* 순차 파일의 단점

- 파일에 새로운 레코드를 삽입, 삭제, 수정하는 경우 파일 전체를 복사해야 하므로 시간이 많이 소요

- 데이터 검색 시 처음부터 순차적으로 하기 때문에 검색 효율이 낮음

* 색인 순차 파일

- 순차 처리와 랜덤 처리가 모두 가능하도록 레코드들을 키 값 순으로 정렬시켜 기록하고,

   레코드의 키 항목만을 모은 색인을 구성하여 편성하는 방식

- 레코드를 참조할 때는 색인을 탐색한 후 색인이 가리키는 포인터(주소)를 사용하여 직접 참조 가능

* 색인 순차 파일의 구성

- 기본 구역 : 실제 레코드들을 기록하는 부분

- 색인 구역 : 기본 구역에 있는 레코드들의 위치를 찾아가는 색인이 기록되는 부분

- 오버플로 구역 : 기본 구역에 빈 공간이 없어 새로운 레코드의 삽입이 불가능할 때를 대비하여 예비적으로 확보한 부분

* 색인 순차 파일의 장점

- 순차 처리와 랜덤 처리가 모두 가능하므로, 목적에 따라 융통성 있게 처리할 수 있음

- 효율적인 검색이 가능하고 레코드의 삽입, 삭제, 갱신이 용이

* 색인 순차 파일의 단점

- 색인 구역과 오버플로우 구역을 구성하기 위한 추가 기억 공간이 필요

- 파일이 정렬되어 있어야 하므로 추가, 삭제가 많으면 효율이 떨어짐

출처 : 2014 시나공 정보처리기사 필기 핵심요약