34. 자료구조
(1) 자료 구조
1️⃣ 자료 구조의 분류
2️⃣ 자료 구조의 활용
| 구분 | 설명 |
| 정렬 | 집합된 데이터 레코드를 일정 기준으로 재배열 |
| 검색 | 원하는 값을 빠르게 찾는 것 |
| 인덱스 (Index) ⭐️ | DB에서 데이터를 빠르게 검색 할 수 있게 구성한 순서 데이터 |
| 파일 편성 | 파일에서레코드의 물리적인 배열 방법 |
(2) 선형 자료 구조
1️⃣ 리스트
❶ 선형 리스트 : 배열처럼 연속된 리스트
❷ 연결 리스트 : 노드의 포인터를 연결시킨 리스트
2️⃣ 스택
❶ 리스트의 한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료 구조
❷ 후입 선출 LIFO(Last In First Out) 방식
❸ 마지막에 삽입된 자료 Top, 가장 먼저 삽입된 자료 Bottom
❹ 스택 가드 : 메모리상에서 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장해두었다가
그 값이 변경 되었을 경우 오퍼플로우 상태로 가정하여 프로그램 실행을 중단
❺ 스택 응용 분야 : 인터럽트 처리, 수식의 계산, 0-주소 지정 방식 /
재귀 호출, 후위 표현의 연산, 깊이 우선 탐색
스택 삽입 알고리즘
if TOP >= n then call Stack-Full;
else TOP = TOP + 1;
Stack(TOP) = Data;
end Insert
스택의 삭제 알고리즘
if TOP = 0
then Underflow
Else
Remove S(TOP)
TOP = TOP - 1
스택의 오버플로 알고리즘
TOP <- TOP + 1
if TOP > n then goto AA
else Stack(TOP) <- item
3️⃣ 큐(QUEUE)
❶ 삽입 작업은 선형 리스트의 한쪽 끝(Rear)에서, 제거 작업은 다른 쪽 끝(Front)에서 수행
❷ 가장 먼저 삽입된 자료가 가장 먼저 삭제 , 선입 선출 (FIFO, First In First Out) 방식
4️⃣ 데크(Deque)
❶ 자료의 삽입과 삭제가 리스트의 양쪽 끝에서 이루어짐
❷ 스택과 큐를 합한 형태
❸ 입력 제한 데크를 Scroll, 출력 제한 데크를 Shelf
[관련 기출 문제]
35. 비선형 구조
(1) 트리
1️⃣ 트리
트리의 정의
: 그래프의 특수한 형태로, 노드와 가지를 이용하여 사이클을 이루지 않도록 구성한 자료
트리 관련 용어
| 노드 | 트리의 기본 구성 요소 | |
| 근노드 | Root Node | 가장 상위에 위치한 노드 |
| 레벨 | Level | 근노드 기준으로 특정 노드 까지 길이 |
| 조상 노드 | Ancestors Node | 특정 노드까지 이르는 경로 상 모든 노드 |
| 부모 노드 | Parent Node | 특정 노드에 연결 된 이전 레벨의 노드 |
| 자식 노드 | Child Node | 어떤 노드에 연결된 다음 레벨의 노드 |
| 형제 노드 | Brother Node | 같은 부모를 가진 노트 |
| 깊이 | Depth | 트리의 최대 레벨 |
| 차수 | Degree | 어떤 노드에 연결된 자식 노드의 수 |
| 단말 노드 | Terminal Node | 트리의 제일 마지막에 위치한 노드 |
| 트리의 차수 | Degree | 트리 노드 중 가장 큰 차수 |
2️⃣ 이진 트리
: 차수가 2 이하인 노드로 구성된 트리 (자식이 2이하)
이진 트리의 구조
이진 트리의 운행법 ⭐️
| 전위 운행 Preorder | Root - Left - Right |
| 중위 운행 Inorder | Left - Root - Right |
| 후위 운행 Postorder | Left - Right - Root |
수식의 표기법
| 전위 표기법 | 연산자 - 피연산자 - 피연산자 | + A B |
| 중위 표기법 | 피연산자 - 연산자 - 피연산자 | A + B |
| 후위 표기법 | 피연산자 - 피연산자 - 연산자 | A B + |
(2) 그래프(Graph)
1️⃣ 그래프 Graph
: 정점(Vertex)와 간선(Edge)의 집합으로 이루어진 자료 구조
최대 간선 수 계산하기 : n(n-1)/2개
[관련 기출 문제]
36. 정렬
(1) 정렬
❶ 내부 정렬 : 주 기억 장치에서 정렬
❷ 외부 정렬 : 보조 기억 장치에서 정렬
(2) 내부 정렬
| 구분 | 설명 |
| 삽입 정렬 | ❶ 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬 ❷ 정렬할 대상을 키 값으로 올려 삽입 |
| 버블 정렬 | ❶ 인접한 데이터를 비교하면서 크기에 따라 데이터 위치를 바꾸어 정렬 ❷ 회전 할 때마다, 큰 값이 뒤로 가서 정렬이 이루어짐 |
| 선택 정렬 | ❶ 최대, 최소, 평균 시간 복잡도 : O(𝑛²) ❷ 값이 많아질 수록 시간이 오래 걸림 ❸ 회전 할 때마다, 작은 값이 앞으로 와서 정렬이 이루어짐 |
| 병합(합병) 정렬 | ❶ 최대, 최소, 평균 시간 복잡도 O(𝑛log₂𝑛) ❷ 값이 많아질 수록 시간이 오래 걸림 |
| 퀵 정렬 | 최대, 최소, 평균 시간 복잡도 O(𝑛log₂𝑛) 최악일 때, O(𝑛²) |
| 힙 정렬 | 전이진 트리를이용하여 정렬하는 방법 최대, 최소, 평균 시간 복잡도 O(𝑛log₂𝑛) 최악일 때, O(log₂𝑛²) |
| 시간 복잡도 ⭐️ | 정렬 |
| O(𝑛log₂𝑛) | 힙, 퀵, 삽입 정렬 |
| O(𝑛²) | 버블, 선택, 삽입 정렬 |
[관련 기출 문제]
37. 검색과 해싱
(1) 검색
1️⃣ 검색 방식의 종류 ⭐️
| 종류 | 설명 |
| 이분 (이진) 검색 | 자료가 순차적으로 정렬되어 있어야 함 |
| 선형(순차) 검색 | 첫 번째 레코드부터 순차적으로 비교 |
| 피보나치 검색 | 비교 대상 기준을 피보나치 수열로 결정 |
| 블록 검색 | 블로긍로 분리한 후 키 값을 순서대로 비교 |
| 이진 트리 검색 | 레코드를 2진 트리로 구성하여 검색 |
(2) 해싱
1️⃣ 해싱
해싱의 정의
❶ 인덱싱하여 빠르게 데이터를 찾을 때 사용
❷ 충돌 시 오버플로 해결이 어려움
해싱 함수의 종류
❶ 제산 방법 Division
❷ 중간 제곱방법 Mid-Square
❸ 중첩 방법 Folding
❹ 기수 변환 방법 Redix Conversion Method
❺ 계수 분석 방법 Digit Analysis Method
(3) 해싱 관련 용어
| 용어 | 설명 | |
| 동의어 | Synonym | 해싱에서 동일한 홈주소로 인해 충돌이 일어난 레코드 |
| 슬롯 | Slot | 한 개의 레코드를 저장할 수 있는 공간 |
| 충돌 | Collision | 레코드 삽입시 2개의 상이한 레코드가 똑같은 버킷으로 해싱되는 것 - 항상 오버플로우 발생 버킷이 여러 슬롯으로 구성될 땐, 충돌이 발생해도 오버플로우 발생 하지 않을 수 있음 |
[관련 기출 문제]
38. 인덱스 구조와 파일 편성
(1) 인덱스
❶ 인덱스를 통해 레코드에 빠르게 접근 가능
❷ DB의 물리적 구조와 밀접한 관계
❸ 레코드 삽입/삭제가 자주 발생 시 인덱스 갯수 최소화
(2) 인덱스 구성방법
| 구분 |
| B 트리 |
| B+ 트리 |
| 트라이 색인 |
(3) 파일 편성 방법
1️⃣ 색인 순차 파일 (ISAM)
| 기본 영역 | 데이터 레코드를 지정하는 부분 | |
| 색인 영역 | 기본 영역에 인덱스가 저장되는 부분 | |
| 구성 | 트랙 인덱스 | |
| 실린더 인덱스 | ||
| 마스터 인덱스 | ||
| 오버플로 영역 ⭐️ | 레코드가 모든 영역을 차지하여 추가 레코드를 입력할 수 없을 때, 블록을 할당 받아 연결 | |
VSAM 파일
❶ 동적 인덱스 방법을 이용한 색인 순차 파일
❷ 기본 영역과 오버플로 영역을 구분하지 않는다
직접 파일
: 해싱 함수를 계산하여 물리적 주소에 직접 접근하는 방식
역파일
: 특정 파일을 여러 개 색인으로 만들고 항목별 특성에 맞게 작업하도록 구성
(4) 정적 인덱싱과 동적 인덱싱
| 구분 | 설명 | 예시 |
| 정적 인덱싱 | 인덱스 내용이 변할 때, 인덱스 구조는 변하지 않음 | 색인 순차 파일 |
| 동적 인덱싱 | ❶ 삽입될 레코드를 위해 빈 공간을 미리 준비 ❷ 레코드가 블록에 차면 동적으로 분열 ❸ 인덱스 부분과데이터 부분을 별개의 파일로 구성 |
가상 기억 접근 방식 |
[관련 기출 문제]
39. 데이터베이스의 개념과 DBMS
(1) 자료 처리
1️⃣ 데이터베이스의 정의
❶ 통합된 데이터 : 각 사용자의 데이터를 한 곳에 모아 통합한 데이터
❷ 저장된 데이터 : 컴퓨터 하드웨어 저장장치에 저장된 데이터
❸ 운영 데이터 : 데이터베이스는 조직의 고유 기능을 수행하기 위해 필요한 데이터
❹ 공용 데이터 : 여러 사용자가 공동/소유/관리 활용하는 데이터
데이터베이스의 특성
❶ 실시간 접근성
❷ 내용에 의한 참조
❸ 동시 공유
❹ 계속적 변화
데이터베이스 시스템의 구성
❶ DBMS
❷ 스키마
❸ 데이터베이스 언어
❹ 데이터베이스 사용자
2️⃣ 데이터 웨어하우스
❶ 기간 업무 시스템에서 추출되어 새로 생성된 데이터베이스
❷ OLAP : 대용량 데이터를 고속으로 처리하며 다양한 관점에서 추출, 분석 하는 데이터 분석 기술
❸ OLAP 연산 종류 : Roll-Up, Drill-Down, Dicing, Slicing
3️⃣ 데이터베이스 용어
| 구분 | 설명 |
| 빅데이터 | 데이터의 생성 양, 주기, 형식 등이 매우 큰 데이터 |
| 데이터 마이닝 | 데이터웨어하우징에서 수집되고 분석된 자료를 분류 및 가공 하는 요소 기술 |
| Hadoop | ❶ 일반 컴퓨터로 가상화된 대형 스토리지를 구현 ❷ 빅데이터 분산 처리를 돕는 자바 소프트웨어 오픈 소스 프레임워크 |
[관련 기출 문제]
40. 데이터베이스의 구성, 모델
(1) 데이터베이스의 구성
1️⃣ 스키마
: 데이터 베이스의 구조(개체, 속성, 관계)에 대한 정의
스키마 3계층
| 구분 | 설명 | |
| 외부 스키마 | External Schema | 사용자나 응용 프로그래머가 접근할 수 있는 정의 |
| 개념 스키마 ⭐️ | Concept Schema | 내부 데이터베이스를 어떻게 조직화 할 것인지 정의 |
| 내부 스키마 | Internal Schema | 데이터를 실제로 하드디스크에 어떻게 저장할 것인지 정의 |
2️⃣ 데이터베이스 언어
| 구분 | 설명 | |
| 데이터 정의어 | DDL, Data Definition Language | 데이터 스키마를 정의하고 변경하고 삭제할 수 있는 기능 |
| 데이터 조작어 | DML, Manipulation | 데이터 안의 레코드를 CRUD 할 때 |
| 데이터 제어어 | DCL, Controll | ❶ 데이터를 보호 ❷ 무결성 유지 ❸ 데이터 회복 및 병행 제어 수행 |
(2) 데이터베이스 모델의 종류
1️⃣ 데이터 모델의 구성요소 ⭐️
| 구분 | 설명 | |
| 데이터 구조 | Structure | 데이터 구조 및 정적 성질 표현 |
| 연산 | Operation | 인스턴스에 적용가능한 연산 명세와 조작 기법 표현 |
| 제약조건 | Constraints | 데이터의 논리적 제한 명시 및 조작 규칙 |
2️⃣ 데이터 모델의 구분
3️⃣ E-R 다이어그램
4️⃣ 논리적 모델
| 관계형 데이터 모델 | DB를 테이블의 집합으로 표현 |
| 계층형 데이터 모델 | DB를 트리구조로 표현 |
| 네트워크형 데이터 모델 | DB를 그래프 구조로 표현 |
[관련 기출 문제]
41. 관계형 데이터베이스 모델
(1) 관계형 데이터베이스 모델의 개요
1️⃣ 관계형 데이터베이스 모델 구조
❶ 튜플 : 테이블의 행(가로)에 해당하며 파일 구조의 레코드와 같은 의미
카디널리티 (Cardinality) : 튜플 수 (기수)
❷ 속성 : 테이블의 열(세로)에 해당하며 파일 구조의 항목, 필드와 같은 의미
차수(Degree) : 속성의 수
❸ 도메인 : 하나의 속성이 가질 수 있는 원자 값들의 집합
2️⃣ 릴레이션의 특징
| 구분 | 설명 |
| 튜플의 유일성 | 모든 튜플은 서로 다른 값을 갖는다 |
| 튜플의 무순서성 | 하나의 릴레이션에서 튜플의 순서는 없다 |
| 속성의 원자성 | 속성값은 원자 값을 갖는다 |
| 속성의 무순서성 | 각 속성은 릴레이션에서 유일한 값을 가지며 순서는 큰 의미가 없다 |
(2) 키의 종류와 무결성
1️⃣ 무결성 ⭐️
| 무결성 종류 | 설명 |
| 개체 무결성 | 기본키의 값은 널 값이나 중복 값을 가질 수 없다 |
| 참조 무결성 | 참조할 수 없는 외래키는 가질 수 없다 |
| 도메인 무결성 | 하나의 속성은 반드시 원자 값이어야 한다 |
[관련 기출 문제]
[참고 영상]
[정보처리기사 필기 절대족보] 핵심이론 3과목(데이터베이스 구축)