정보처리기사 실기 요약 - 2장. 데이터 입출력 구현

01. 데이터 전환

- 기존 정보 시스템에 축적되어 잇는 데이터를 추출하여 변환한 후, 적재하는 일련의 과정(ETL)

 

02. 데이터 검증

- 원천 시스템의 데이터를 목적 시스템의 데이터로 전환하는 과정이 정상적으로 수행되었는지 확인하는 과정

- 방법: 로그 검증, 기본 항목 검증, 응용 프로그램 검증, 응용 데이터 검증, 값 검증

 

03. 오류 데이터 측정 및 정제

- 고품질의 데이터를 운영 및 관리하기 위해 수행

- 데이터 품질 분석 → 오류 데이터 측정 → 오류 데이터 정제

 

04. 데이터베이스 개요

1) 데이터 저장소: 데이터들을 논리적인 구조로 조직화하거나 물리적인 공간에 구축한 것

 

2) 데이터베이스(Database): 공동으로 사용될 데이터의 중복을 배제하여 통합하고 저장장치에 저장하여 항상 사용할 수 있도록 운영하는 데이터

 

3) DBMS(DataBase Management System, 데이터베이스 관리 시스템): 사용자의 요구에 따라 정보를 생성해주고 데이터베이스를 관리해주는 소프트웨어

- 필수 기능: 정의(Definition), 조작(Manipulation), 제어(Control)

 

4) 데이터의 독립성

- 논리적 독립성: 응용 프로그램과 데이터베이스를 독립

- 물리적 독립성: 응용 프로그램과 보조기억장치 같은 물리적 장치를 독립

 

5) 스키마(Schema): 데이터베이스의 구조와 제약조건에 관한 전반적인 명세를 기술한 것

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

- 개념 스키마: 데이터베이스의 전체적인 논리 구조

- 내부 스키마: 물리적 저장장치의 입장에서 본 데이터베이스 구조

 

05. 데이터베이스 설계

 

1) 고려사항

- 무결성: 정해진 제약조건을 항상 만족해야 함.

- 일관성: 처음부터 끝까지 변함없이 일정해야 함.

- 회복: 시스템 장애가 발생했을 때 장애 발생 직전의 상태로 복구할 수 있어야 함.

- 보안: 불법적인 데이터의 노출 또는 변경이나 손실로부터 보호할 수 있어야 함.

- 효율성: 응답시간의 단축, 시스템의 생산성, 저장 공간의 최적화 등이 가능해야 함.

- 데이터베이스 확장: 지속적으로 추가할 수 있어야 함.

 

2) 설계 순서

① 요구 조건 분석: 데이터베이스를 사용할 사람들로부터 필요한 용도를 파악하는 것

② 개념적 설계(정보 모델링): 현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정

③ 논리적 설계(데이터 모델링): 현실 세계에서 발생하는 자료를 특정 DBMS가 지원하는 논리적 자료 구조로 변환시키는 과정

④ 물리적 설계(데이터 구조화): 논리적 구조로 표현된 데이터를 물리적 구조의 데이터로 변환하는 과정

⑤ 구현: 논리적 설계와 물리적 설계에서 도출된 데이터베이스 스키마를 파일로 생성하는 과정

* 요개논물

 

06. 데이터 모델의 개념

- 현실 세계의 정보들을 단순화, 추상화하여 체계적으로 표현한 개념적 모형

 

1) 구성요소

- 개체(Entity): 개념이나 정보 단위 같은 현실 세계의 대상체

- 속성(Attribute): 데이터베이스를 구성하는 가장 작은 논리적 단위

     - 기본키 속성: 개체를 유일하게 식별할 수 있는 속성

     - 외래키 속성: 다른 개체와의 관계에서 포함된 속성

     - 디그리(Degree): 속성의 수

- 관계(Relationship): 개체와 개체 사이의 논리적인 연결

 

2) 표시할 요소

- 구조, 연산, 제약조건

 

3) 데이터 모델 종류

- 개념적 데이터 모델: 현실 세계에 대한 인간의 이해를 돕기 위해 현실 세계에 대한 인식을 추상적 개념으로 표현하는 과정

- 논리적 데이터 모델: 개념적 구조를 컴퓨터 세게의 환경에 맞도록 변환하는 과정 

- 물리적 데이터 모델: 실제 컴퓨터에 데이터가 저장되는 방법을 정의하는 물리 데이터베이스 설계 과정

 

07. 식별자(Identifier)

- 하나의 개체 내에서 인스턴스를 유일하게 구분할 수 있는 구분자

- 후보 식별자: 개체에서 각 인스턴스를 유일하게 식별할 수 있는 속성 또는 속성 집합

 

08. E-R(개체-관계) 모델

- 개체와 개체 간의 관계를 기본 요소로 이용하여 현실 세계의 무질서한 데이터를 개념적인 논리 데이터로 표현하기 위한 방법

- 개체, 관계, 속성으로 표시

 

09. 관계형 데이터베이스의 구조 / 관계형 데이터 모델

 

1) 관계형 데이터 베이스

- 2차원적인 표를 이용해서 데이터 상호 관계를 정의하는 데이터베이스

 

2) 관계형 데이터베이스의 릴레이션 구조

3) 튜플(Tuple)

- 릴레이션을 구성하는 각각의 행

- 카디널리티(Cardinality): 튜플의 수

 

4) 속성(Attribute)

- 데이터베이스를 구성하는 가장 작은 논리적 단위

- 디그리(Degree): 속성의 수

 

5) 도메인(Domain)

- 하나의 애트리뷰트가 취할 수 있는 같은 타입의 원자 값들의 집합

 

6) 관계형 데이터 모델

- 2차원적인 표를 이용해서 데이터 상호 관계를 정의하는 DB 구조

 

10. 관계형 데이터베이스의 제약 조건 - 키(Key)

 

1) 키(Key): 조건에 만족하는 튜플을 찾거나 순서대로 정렬할 때 기준이 되는 속성

 

2) 후보키(Candidate Key): 속성들 중에서 튜플을 유일하게 식별하기 위해 사용되는 속성들의 부분 집합

- 유일성, 최소성을 모두 만족시켜야 함

 

3) 기본키(Primary Key): 후보키 중에서 특별히 선정된 주키

 

4) 대체키(Alternate Key): 후보키가 둘 이상일 때 기본키를 제외한 나머지 후보키

 

5) 슈퍼키(Super Key): 속성들의 집합으로 구성된 키

- 유일성은 만족하지만 최소성은 만족하지 못함.

 

6) 외래키(Foreign Key)

- 다른 릴레이션의 기본키를 참조하는 속성 또는 속성들의 집합

 

11. 관계형 데이터베이스의 제약 조건 - 무결성(Integrity)

- 데이터베이스에 저장된 데이터 값과 현실 세계의 실제값이 일치하는 정확성

 

1) 무결성의 종류

- 개체 무결성: 기본 테이블의 기본키를 구성하는 어떤 속성도 NULL 값이나 중복값을 가질 수 없다는 규정

- 참조 무결성: 외래키 값은 NULL이거나 참조 릴레이션의 기본키 값과 동일해야 함

- 도메인 무결성: 주어진 속성값이 정의된 도메인에 속한 값이어야 한다는 규정

- 사용자 정의 무결성: 속성값들이 사용자가 정의한 제약조건에 만족되어야 한다는 규정

- NULL 무결성: 릴레이션의 특정 속성 값이 NULL이 될 수 없도록 하는 규정

- 고유 무결성: 릴레이션의 특정 속성에 대해 각 튜플이 갖는 속성값들이 서로 달라야 한다는 규정

- 키 무결성: 하나의 릴레이션에는 적어도 하나의 키가 존재해야 한다는 규정

- 관계 무결성: 릴레이션에 어느 한 튜플의 삽입 가능 여부 또는 한 릴레이션과 다른 릴레이션의 튜플들 사이의 관계에 대한 적절성 여부를 지정한 규정.

 

12. 관계 대수 및 관계 해석

 

1) 관계 대수: 원하는 정보와 그 정보를 검색하기 위해서 어떻게 유도하는 가를 기술하는 절차적인 언어

 

2) 순수 관계 연산자

- Select: 선택 조건을 만족하는 튜플의 부분집합을 구하여 새로운 릴레이션을 만드는 연산

- Project: 속성 리스트에 제시된 속성값만 추출하여 새로운 릴레이션을 만드는 연산

- Join: 공통 속성을중심으로 두 개의 릴레이션을 하나로 합쳐서 새로운 릴레이션을 만듦

- Division: R의 속성이 S의 속성값을 모두 가진 튜플에서 S가 가진 속성을 제외한 속성 만을 구하는 연산

 

3) 일반 집합 연산자

- 수학적 집합 이론에서 사용하는 연산자

- 합집합, 교집합, 차집합, 교차곱

 

4) 관계 해석

- 관계 데이터의 연산을 표현하는 방법

- 원하는 정보가 무엇이라는 것만 정의하는 비절차적 특성

 

13. 이상 / 함수적 종속

 

1) 이상(Anomaly): 테이블에서 데이터의 중복이 발생하고, 이 중복으로 인해 문제가 발생하는 현상

- 삽입 이상(Insertion Anomaly): 테이블에 데이터를 삽입할 때 의도와는 상관없이 원하지 않는 값들로 인해 삽입할 수 없게 되는 현상

- 삭제 이상(Deletion Anomaly): 테이블에서 한 튜플을 삭제할 때 의도와는 상관없이 원하지 않은 값들로 인해 삽입할 수 없게 되는 현상

- 갱신 이상(Update Anomaly): 테이블에서 튜플에 있는 속성값을 갱신할 때 일부 튜플의 정보만 갱신되어 불일치성이 생기는 현상

 

2) 함수적 종속: 학번, 이름, 학년, 학과라는 속성을 가지는 테이블에서 학번으로는 이름을 찾을 수 있지만 이름으로는 학번을 찾을 수 없음(동명이인이 있을 수 있기 때문)

- 완전 함수적 종속: X와 Y가 모두 결정자이고, Z가 종속자인 경우에 X, Y → Z

- 부분 함수적 종속: X와 Y가 모두 결정자이지만 X만으로도 Z를 결정할 수 있을 때 X → Z

 

 

14. 정규화(Nomalization)

 

1) 정규화(Nomalization): 테이블의 속성들이 상호 종속적인 관계(함수적 종속)를 갖는 특성을 이용하여 테이블을 무손실 분해하는 과정

- 가능한 한 중복을 제거하여 삽입, 삭제, 갱신 이상의 발생 가능성을 줄이는 것이 목적

 

2) 제 1정규형: 모든 속성의 도메인이 원자값만으로 되어 있는 정규형

 

3) 제 2정규형: 제 1정규형을 만족하면서 기본키가 아닌 모든 속성이 기본키에 대해 완전 함수적 종속을 만족하는 정규형

 

4) 제 3정규형: 제 2정규형을 만족하면서 기본키가 아닌 모든 속성이 기본키에 대해 이행적 함수 종속을 만족하지 않는 정규형

- 이행적 함수 종속: A → B이고 B→C 일 때 A →C를 만족하는 관계

5) BCNF 정규형: 모든 결정자가 후보키인 정규형

 

6) 제 4정규형: 다중 값 종속 A → B가 존재할 경우 해당 테이블의 모든 속성이 A에 함수적 종속 관계를 만족하는 정규형

- 다중 값 종속: A, B, C 3개의 속성을 가진 테이블에서 어떤 복합 속성에 대응하는 B값의 집합이 A값에만 종속되고 C값에는 무관한 경우

 

7) 제 5정규형: 테이블의 모든 조인 종속이 해당 테이블의 후보키를 통해서만 성립되는 정규형

* 도부이결다조

 

15. 반정규화(Denormalization)

 

1) 반정규화: 정규화된 데이터 모델을 의도적으로 통합, 중복, 분리하여 정규화 원칙을 위배하는 행위

 

2) 테이블 통합: 두 개의 테이블이 조인되어 사용되는 경우가 많을 경우 성능 향상을 위해 아에 하나의 테이블로 만들어 사용

 

3) 테이블 분할: 테이블을 수직 또는 수평으로 분할하는 것

 

4) 중복 테이블 추가: 작업의 효율성을 향상시키기 위해 테이블을 추가하는 것

- 집계 테이블의 추가: 집계데이터를 위한 테이블을 생성하고, 각 원본 테이블에 트리거를 설정하여 사용

- 진행 테이블의 추가: 이력 관리등의 목적으로 추가하는 테이블

- 특정 부분만을 포함하는 테이블의 추가: 데이터가 많은 테이블의 특정 부분만을 사용하는 경우, 해당 부분만으로 새로운테이블을 생성

 

5) 조인 속성추가: 조인해서 데이터를 처리할 때 데이터를 조회하는 경로를 단축하기 위해 자주 사용하는 속성을 하나 더 추가하는 것.

 

16. 시스템 카탈로그

 

1) 시스템 카탈로그: 다양한 객체에 관한 정보를 포함하는 시스템 데이터베이스

- 카탈로그들이 생성되면 데이터 사전에 저장되기 때문에 좁은 의미로는 데이터 사전이라고도 함.

 

2) 메타 데이터: 시스템 카탈로그에 저장된 정보

 

3) 데이터 디렉터리: 데이터 사전에 수록된 데이터에 접근하는 데 필요한 정보를 관리 유지하는 시스템

 

17. 데이터베이스 저장 공간 설계

 

1) 데이터베이스 저장 공간설계

- 테이블: 데이터베이스의 가장 기본적인 객체

- 컬럼: 테이블의 열을 구성하는 요소

- 테이블 스페이스: 테이블이 저장되는 논리저인 영역

 

18. 트랜잭션 분석 / CRUD 분석

 

1) 트랜잭션: 논리적 기능을 수행하기 위한 작업의 단위 또는 한꺼번에 모두 수행되어야 할 일련의 연산들

- Atomicity(원자성): 트랜잭션의 연산은 데이터에 모두 반영되도록 완료되든지 아니면 전혀 반영되지 않도록 복구되어야 함.

- Consistency(일관성): 트랜잭션이 그 실행을 성공적으로 완료하면 언제나 일관성 있는 데이터베이스 상태로 변환함.

- Isolation(독립성, 격리성): 둘 이상의 트랜잭션이 동시에 병행 실행되는 경우 어느 하나의 트랜잭션 실행 중에 다른 트랜잭션의 연산이 끼어들 수 없음

- Durability(영속성, 지속성): 성공적으로 완료된 트랜잭션의 결과는 시스템이 고장나더라도 영구적으로 반영되어야 함.

 

2) CRUD 분석: 프로세서와 테이블 간에 CRUD 매트릭스를 만들어서 트랜잭션을 분석하는 것

- CRUD 매트릭스: 2차원 형태의 표로서, 행에는 프로세스를, 열에는 테이블을, 행과 열이 만나는 위치에는 프로세스가 테이블에 발생시키는 변화를 표시하여 프로세스와 데이터 간의 관계를 분석하는 분석표

 

3) 트랜잭션 분석: CRUD 매트릭스 기반으로 테이블에 발생하는 트랜잭션 양을 분석하여 테이블에 저장하는 데이터의 양을 유추하고, 이를 근거로 DB의 용량 산정 및 구조의 최적화를 목적으로 함.

 

19. 인덱스

 

1) 인덱스(Index): 데이터 레코드를 빠르게 접근하기 위해 <키 값, 포인트> 쌍으로 구성되는데이터 구조

- 트리 기반 인덱스: 인덱스를 저장하는 블록들이 트리 구조를 이루고 있는 것

- 비트맵 인덱스: 인덱스 컬럼에 특정 함수나 수식을 적용하여 산출된 값을 사용하는 것

- 함수 기반 인덱스: 컬럼의 값 대신 컬럼에 특정 함수나 수식을 적용하여 산출된 값을 사용하는 것

- 비트맵 조인 인덱스: 다수의 조인된 객체로 구성된 인덱스

- 도메인 인덱스: 개발자가 필요한 인덱스를 직접 만들어서 사용하는 것

 

2) 클러스터드 인덱스 / 넌클러스터드 인덱스: 실제 데이터가 정렬되었냐 안되었냐의 차이

- 클러스터드 인덱스: 인덱스 키의 순서에 따라 데이터가 정렬되어 저장되는 방식

- 넌클러스터드 인덱스: 인덱스의 키 값만 정렬되어 실제 데이터는 정렬되지 않는 방식

 

20. 뷰 /클러스터

 

1) 뷰(View): 하나 이상의 기본 테이블로부터 유도된 가상 테이블

- 논리적 데이터 독립성을 제공하지만 독립적인 인덱스를 가질 수는 없음

 

2) 클러스터(Cluster): 데이터 액세스 효율을 향상시키기 위해 동일한 성격의 데이터를 동일한 데이터 블록에 저장하는 물리적 저장 방법

 

21. 파티션

 

1) 파티션(Partition): 대용량의 테이블이나 인덱스를 작은 논리적 단위인 파티션으로 나누는 것

- 범위 분할(Range Partitioning): 지정한 열의 값을 기준으로 분할함

- 해시 분할(Hash Partitioning): 해시 함수를 적용한 결과 값에 따라 데이터를 분할함

- 조합 분할(Composite Partitioning): 범위 분할로 분할한 다음 해시 함수를 적용하여 다시 분할하는 방식

 

22. 분산 데이터베이스 설계

 

1) 데이터베이스 용량 설계: 데이터가 저장될 공간을 정의하는 것

 

2) 분산 데이터베이스 설계: 논리적으로는 하나의 시스템에 속하지만 물리적으로는 네트워크를 통해 연결된 여러 개의 사이트에 분산된 데이터베이스

- 위치 투명성: 엑세스하려는 데이터베이스의 실제 위치를 알 필요 없이 단지 데이터베이스의 논리적인 명칭만으로 엑세스할 수 있음.

- 중복 투명성: 동일 데이터가 여러 곳에 중복되어 있더라도 사용자는 마치 하나의 데이터가 존재하는 것처럼 사용하고, 시스템은 자동으로 여러 자료에 대한 작업을 수행함.

- 병행 투명성: 분산 데이터베이스와 관련된 다수의 트랜잭션들이 동시에 실현되더라도 그 트랜잭션의 결과는 영향을 받지 않음. (일관성 유지)

- 장애 투명성: 트랜잭션, DBMS, 네트워크, 컴퓨터 장애에도 불구하고 트랜잭션을 정확하게 처리(무결성 보장)

 

23. 데이터베이스 이중화 / 서버 클러스터링

 

1) 데이터베이스 이중화: 동일한 데이터베이스를 복제하여 관리하는 것

- 활동 - 대기 방법: 한 DB가 활성 상태로 서비스하고 있으면 다른 DB는 대기하다가 장애 발생하면 대신 수행

- 활동 - 활동 방법: 두 개의 DB가 서로 다른 서비스를 제공하다가 둘 중 하나가 문제면 나머지가 대신 수행

 

2) 클러스터링: 두 대 이상의 서버를 하나의 서버처럼 운영하는 기술

- 고가용성 클러스터링: 하나의 서버에 장애가 발생하면 다른 노드(서버)가 받아 처리하여 서비스 중단을 방지

- 병렬 처리 클러스터링: 하나의 작업을 여러 개의 서버에 분산하여 처리하는 방식

 

3) RTO / RPO

- RTO (Recovery Time Objective, 목표 복구 시간): 비상사태 또는 업무 중단 시점으로부터 복구되어 가동될 때까지의 소요 시간

- RPO (Recovery Point Objective, 목표 복구 시점): 비상사태 또는 업무 중단 시점으로부터 데이터를 복구할 수 있는 기준점

 

24. 데이터베이스 보안

 

1) 데이터베이스 보안: 권한이 없는 사용자가 액세스하는 것을 금지하기 위해 사용되는 기술

 

2) 암호화: 평문을 암호문으로 변환하는 것

- 개인키 암호화 기법(대칭키 / 단일키 암호화 기법): 동일한 키로 데이터를 암호화하고 복호화함. 

- 공개키 암호화 방식(비대칭키 암호화 기법): 서로 다른 키로 데이터를 암호화하고 복호화함. 데이터를 암호화할 떄는 공개키로 하고 복호화할 때는 비밀키로 함.

 

3) 접근 통제: 데이터가 저장된 객체와 이를 사용하려는 주체 사이의 정보 흐름을 제한하는 것

- 접근 통제 3요소: 접근통제 정책, 접근통제 매커니즘, 접근통제 보안모델

- 임의 접근 통제(DAC, Discretionary Acess Control): 데이터에 접근하는 사용자의 신원에 따라 접근 권한을 부여하는 방식

- 강제 접근 통제(MAC, Mandatory Access Control): 주체와 객체의 등급을 비교하여 접근 권한을 부여하는 방식

- 역할 기반 접근 통제(RBAC, Role Based Access Control): 사용자의 역할에 따라 접근 권한을 부여하는 방식

 

4) 접근 통제 정책: 어떤 주체가 언제, 어디서, 어떤 객체에게, 어떤 행위에 대한 허용 여부를 정의하는 것

 

5) 접근 통제 종류

- 신분 기반 정책: 주체나 그룹의 신분에 근거하여 객체의 접근을 제한하는 방법

- 규칙 기반 정책: 주체가 갖는 권한에 근거하여 객체의 접근을 제한하는 방법

- 역할 기반 정책: 주체의 신분이 아니라 주체가 맡은 역할에 근거하여 객체의 접근을 제한하는 방법

 

6) 접근 통제 매커니즘: 정의된 접근통제 정책을 구현하는 기술적인 방법

 

7) 접근 통제 보안 모델: 보안 정책을 구현하기 위한 정형화된 모델

- 기밀성 모델: 군사적인 목적으로 개발된 최초의 수학적 모델

- 무결성 모델: 기밀성 모델에서 발생하는 불법적인 정보 변경을 방지하기 위해 무결성을 기반으로 개발된 모델

- 접근 통제 모델: 접근 통제 매커니즘을 보안 모델로 발전시킨 모델

 

8) 접근 통제 조건: 접근 통제 매커니즘의 취약점을 보완하기 위해 접근 통제 정책에 부가하여 적용할 수 있는 조건

- 값 종속 통제: 객체에 저장된 값에 따라 다르게

- 다중 사용자 통제: 다수의 사용자가 접근을 요구하는 경우

 

9) 감사 추적: 사용자나 애플리케이션이 데이터베이스에 접근하여 수행한 모든 활동을 기록하는 기능

 

25. 데이터베이스 백업

 

1) 데이터베이스 백업: 데이터베이스에 저장된 데이터를 보호하고 복구하기 위한 작업

 

2) 로그 파일: 데이터베이스의 상태 변화를 시간의 흐름에 따라 모두 기록한 파일

 

3) 데이터베이스 복구 알고리즘

- NO-UNDO / REDO: 데이터베이스 버퍼의 내용을 비동기적으로 갱신한 경우 복구 알고리즘

- UNDO / NO-REDO: 데이터베이스 버퍼의 내용을 동기적으로 갱신한 경우의 복구 알고리즘

- UNDO/REDO: 데이터베이스 버퍼의 내용을 동기/비동기적으로 갱신한 경우의 복구 알고리즘

- NO-UNDO / NO-REDO: 데이터베이스 버퍼의 내용을 동기적으로 저장 매체에 기록하지만 데이터베이스와는 다른 영역에 기록한 경우의 복구 알고리즘

 

4) 백업 종류

- 물리 백업: 데이터베이스  파일을 백업

- 논리 백업: DB 내의 논리적 객체들을 백업하는 방법

 

26. 스토리지

 

1) 스토리지(Storage): 대용량의 데이터를 저장하기 위해 서버와 저장장치를 연결하는 기술

- DAS(Direct Attached Stroage): 서버와 저장장치를 전용 케이블로 직접 연결하는 방식(외장하드)

- NAS(Network Attached Storage): 서버와 저장장치를 네트워크를 통해 연결하는 방식

- SAN(Storage Area Network): 서버와 저장장치를 연결하는 전용 네트워크를 별도로 구성하는 방식

 

27. 자료구조

- 자료를 기억장치의 공간 내에 저장하는 방법과 자료 간의 관계, 처리 방법 등을 연구 분석하는 것

 

1) 선형구조(Linear Structure)

- 배열(Array): 크기와 형(Type)이 동일한 자료들이 순서대로 나열된 자료의 집합

- 연속 리스트: 연속되는 기억장소에 저장되는 자료 구조

- 연결 리스트: 자료들을 임의의 기억 공간에 기억시키되, 노드의 포인터 부분을 이용하여 서로를 연결시킨 구조

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

- 큐: 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 실제 작업이 이루어지는 구조(FIFO)

- 데크: 양쪽에서 삽입, 삭제 가능

 

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

- 그래프: 정점와 간선의 두 집합으로 이루어지는 자료 구조

     - 사이클이 없는 그래프: 트리

     - 방향 그래프의 최대 간선 수 = n(n-1)

     - 무방향 그래프의 최대 간선 수 = n(n-1)/2

- 트리: 정점과 branch를 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태

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

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

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

     - 단말 노드(Leaf): 자식이 하나도 없는 노드, Degree가 0인 노드

     - 비단말 노드: 자식이 하나라도 있는 노드

     - 조상 노드: 임의의 노드에서 근 노드에 이르는 경로상에 있는 노드들

     - 자식 노드: 어떤 노드에 연결된 다음 레벨의 노드들

     - 부모 노드: 어떤 노드에 연결된 이전 레벨의 노드들

     - 형제 노드: 동일한 부모를 갖는 노드들

     - Level

          - 깊이: Tree에서 노드가 가질 수 있는 최대의 레벨

          - 숲: 여러 개의 트리가 모여 있는 것

          - 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수

          - 이진 트리: 차수(Degree)가 2이하의 노드들로 구성된 트리

          - Preorder: Root → Left → Right (+AB)

          - Inorder: Left → Root → Right (A+B)

          - Postorder: Left → Right → Root  (AB+)

 

28. 정렬(Sort)

 

1) 삽입 정렬(Insertion Sort): 이미 순서화된 파일에 새로운 하나의 레코드르르 순서에 맞게 삽입시켜 정렬하는 방식

 

2) 선택 정렬(Selection Sort): 최솟값을 찾아 첫번째 레코드 위치에 놓고, 다시 최솟값을 찾아 두번째 레코드 위치에 놓는 방식을 반복

 

3) 버블 정렬(Bubble Sort): 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식

 

4) 쉘 정렬(Shell Sort): 매개변수의 값으로 서브 파일을 구성하고, 각 서브 파일을 Insertion 정렬 방식으로 순서 배열

 

5) 퀵 정렬(Quick Sort): 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽 서브 파일에 분해시키는 정렬 방식

 

6) 힙 정렬(Heap Sort): 전이진 트리를 이용한 정렬 방식

 

7) 2-Way 합병 정렬(Merge Sort): 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식

 

8) 기수 정렬(Bucket Sort): 큐를 이용하여 자릿수별로 정렬하는 방식