정보처리기사 - 제2과목 소프트웨어 개발 / 데이터 입출력 구현(1)

 제2과목 데이터 입출력 구현 

▷ 데이터 입출력 구현 A, B

> 자료구조

- 자료구조 정의 : 자료의 표현, 자료간의 연산, 자료 조직 구조화, 모든 연산 처리, 실행 시간이 달라짐

- 자료구조의 분류 :  선형구조(리스트, 스택, 큐, 데큐) vs 비선형구조(트리, 그래프) 

- 선형구조

1) 리스트(Linear List)

  배열(Array) : 선형리스트, 빈공간 없이 연속된 기억공간에 저장, 삽입과 삭제가 힘듦(자료의 이동이 많음), 기억공간의 밀도가 좋음, 데이터가 연속된 공간에 존재, 1,2,3차원 배열 / 연결리스트 : 삽입,삭제 용이, 희소행렬표시, 원형연결리스트, 이중연결리스트, 이중원형연결리스트

2) 스택(Stack) : LIFO(FILO)구조, 삽입삭제가 한쪽에서만 이루어지는 구조, pop, push, top, bottom / 산술식구조, 함수, 인터럽트 복귀주소에서 사용

3) 큐(Queue) : 입력(Rear), 출력(Front)이 지정됨, LILO(FIFO)구조, ex. 작업스케줄, 버퍼관리

4) 데큐(구조 : 양끝에서 입출력이 되는 구조, 스크롤(삽입제한), 셀프(출력제한)

 

- 비선형구조

1) 트리(Tree) : A(root), M(리프노드, 단말노드) 차수, 레벨(깊이), 단말노드(차수0), 부모노드, 자식노드, 형제노드, 조상노드

이진트리 : 정이진트리, 전이진트리, 사향이진트리

 

- 트리의 순회 방법 (2진트리)

 

중위 순회 : 왼쪽 서브트리 -> 중간노드 -> 오른쪽 서브트리 : 2-1-3 / 1-2-4-5-7-6-8-9

전위 순회 : 중간노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 : 1-2-3 / 5-2-1-4-8-6-7-9

후위 순회 : 왼쪽 서브트리 -> 오른쪽 서브트리 -> 중간노드 : 2-3-1 / 1-4-2-7-6-9-8-5

 

정이진트리

깊이 K(3) / 깊이 L(3)

총노드 2^K -1 / 해당 노드 갯수 2^(L-1) -1

 

전이진트리

 

 

2) 그래프 : loop 

- 그래프 개념 : 객체 간의 관계를 표현할 수 있는 자료구조

- 그래프 표현 방법

- 그래프 종류 : 무방향 그래프(선에 방향이 없음, 간선갯수 = 노드갯수(n*(n-1))/2), 방향 그래프(선에 방향이 있음, 간선갯수 = 노드갯수 n*(n-1))

- 그래프 특징 : 네트워크 모델, 2개 이상의 경로 가능, 자신을 향하는 간선은 없음, 중복된 간선 비허용

 

 

최소비용 신장트리 : 그래프에서 나올 수 있는 트리, 간선의 수 = (노드위 갯수n-1)개

 

> 파일 : 많은 양의 데이터를 저장하는 기법

- 순차파일 : 입력되는 순서대로 저장, 효율↑, 검색 불편, 삽입삭제 이동시간 소요, 일관처리에 적합

- 직접 파일 : 임의의 저장공간에 저장, 접근시간이 빠름, 비교적 삽입삭제 용이, 입출력이 잦을때 적합

- 색인 순차 파일 : 순차처리, 랜덤처리 가능, 효율검색, 오버플로우영역이 추가로 필요함, 액세스시간 느림

  기본영역(데이터), 색인영역(트랙, 실린더, 마스터)(레코드위치), 오버플로우 영역(빈공간이 없을 때 여분)