1장 - 데이터 입・출력 구현 핵심 요약

2024년도 시나공 필기 책 내용 정리

---

섹션1. 자료구조

 

1. 자료 구조의 분류

 

• 선형 구조 : 배열(Array), 선형 리스트(Linear List), 스택(Stack), 큐(Queue), 데크(Deque)
• 비선형 구조 : 트리(Tree), 그래프(Graph)

2. 연결 리스트(Linked List)

 

• 노드의 삽입,삭제 작업이 용이함
• 연결을 위한 링크(포인터)부분이 필요함
• 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느림
• 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘듦

3. 스택(Stack)

 

• 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조
• 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식으로 자료를 처리
• 재귀호출, 후위(Postfix)표기법, 깊이우선탐색과 같이 왔던 길을 되돌아가는 경우에 사용

4. 스택의 응용 분야

 

• 함수 호출의 순서 제어
• 인터럽트의 처리
• 수식 계산 및 수식 표기법
• 컴파일러를 이용한 언어 번역
• 부 프로그램 호출 시 복귀 주소 저장
• 서브루틴 호출 및 복귀 주소 저장

5. 스택의 삽입(Push)과 삭제(Pop)

 

• Push는 스택에 자료를 입력하는 명령이고, Pop은 스택에서 자료를 출력하는 명령
• A, B, C, D의 입력 자료 -> B, C, D, A 순으로 출력하는 과정 나열
  
  
  • PUSH A -> PUSH B -> POP B -> PUSH C -> POP C -> PUSH D -> POP D -> POP A
• A, B, C, D로 정해진 입력자료를 PUSH -> PUSH-> POP -> PUSH -> PUSH -> POP -> POP -> POP 연산했을 때 출력 결과 작성
  
  
  • B -> D -> C -> A

6. 큐(Quere)

 

• 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조
• 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO)방식으로 처리함

7. 데크(Deque)

 

• 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료구조
• 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 있는 입력제한과 입력은 양쪽에서 발생하고 출력은 한곳에서만 이루어지는 출력 제한이 있음

8. 방향/무방향 그래프의 최대 간선 수

 

• n개의 정점으로 구성된 무방향 그래프에서 최대 간선 수 : n(n-1)/2
• n개의 정점으로 구성된 방향그래프에서 최대 간선 수 : n(n-1)
• 정점이 4인 방향 그래프가 가질 수 있는 최대 간선 수 계산 : 12개

---

섹션2. 트리(Tree)

 

1. 트리의 개요

 

A - 근노드

 

• 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태
• 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
• 단말 노드(Terminal Node) : 자식이 하나도 없는 노드(디그리가 0인 노드)

2. 트리의 운행법

Preorder 운행법의 방문 순서

 

• Preorder는 Root -> Left -> Right 이므로 A13이 됨
• 1은 B2E -> AB2E3
• 2는 DHI -> ABDHIE3
• 3은 CFG -> ABDHIECFG(최종 방문 순서)

Inorder 운행법의 방문 순서

 

• Inorder는 Left  -> Root  -> Right 이므로 1A3이 됨
• 1은 2BE -> 2BEA3
• 2는 HDI-> HDIBEA3
• 3은 FCG-> HDIBEAFCG(최종 방문 순서)

Postorder 운행법의 방문 순서

 

• Postorder는 Left  -> Right  -> Root  이므로 13A이 됨
• 1은 2EB -> 2EB3A
• 2는 HID-> HIDEB3A
• 3은 FGC -> HIDEBFGCA(최종 방문 순서)

3. 수식의 표기법(Infix -> Postfix)

 

• Infix로 표기된 수식에서 연산자를 해당 피연산자 두 개의 뒤(오른쪽)에 오도록 이동하면 Postfix가 됨

X = A / B * (C + D) + E -> X A B / C D + E * + =

 

• (X = ((A / B) * (C + D)) + E))
• X A B / C D + E * + =

 

다음 트리의 차수(Degree)와 단말 노드(Terminal Node)의 수를 계산

• 트리의 차수 - 2 (가장 차수가 많은 노드의 차수)
• 단말 노드 - 5 (자식이 하나도 없는 노드의 수)

 

다음 트리를 Preorder 운행법으로 운행할 경우 다섯 번 째로 탐색되는 것을 작성

 

• A -> B -> D -> C -> E 
• 답 : E

다음 중위 표기법(Infix)의 수식을 후위 표기법(Postfix)로 표기

 

• (A+B) * C + (D+E)
• (((A+B) * C) + (D+E))
• A B + C * D E + +

---

섹션3. 정렬(Sort)

 

1. 삽입 정렬(Insertion Sort)

 

• 8, 5, 6, 2, 4를 삽입 정렬로 정렬
• 최종: 4회전

1회전	5	8	6	2	4
2회전	5	6	8	2	4
3회전	2	5	6	8	4
4회전	2	4	5	6	8

 

2.선택 정렬(Selection Sort)

 

• n개의 레코드 중에서 최소값을 찾아 첫 번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬
• 8, 5, 6, 2, 4를 선택 정렬로 정렬
• 최종: 4회전

1회전	5	8	6	2	4
	2	8	6	5	4
2회전	2	6	8	5	4
	2	5	8	6	4
	2	4	8	6	5
3회전	2	4	6	8	5
	2	4	5	8	6
4회전	2	4	5	6	8

 

3. 버블 정렬(Bubble Sort)

 

• 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환
• 8, 5, 6, 2, 4를 버블 정렬로 정렬
• 최종: 3회전

1회전	5	8	6	2	4
	5	6	8	2	4
	5	6	2	8	4
	5	6	2	4	8
2회전	5	2	6	4	8
	5	2	4	6	8
3회전	2	5	4	6	8
	2	4	5	6	8
4회전	2	4	5	6	8

 

4. 퀵 정렬(Quick Sort)

 

• 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬
• 분할(Divide)과 정복(Conquer)을 통해 자료를 정렬
• 피봇(Pivot)을 사용하며, 최악의 경우 n(n-1)/2회의 비교를 수행함

5. 힙 정렬(HeaP Sort)

 

• 전이진 트리를 이용한 정렬 방식
• 평균과 최악 모두 시간 복잡도는 O(nlog2n)

다음 자료에 대해 삽입(Insertion)정렬을 이용하여 오름차순 정렬할 경우 1회전 후의 결과를 작성

 

• 5, 4, 3, 2, 1
• 1회전: 4, 5, 3, 2, 1

다음 자료에 대하여 선택(Selection)정렬을 이용하여 오름차순 정렬할 경우 1회전 후의 결과를 작성

 

• 8, 3, 4, 9, 7
• 1회전 : 3, 8, 4, 9, 7

다음 자료에 대해 버블(Bubble)정렬을 이용하여 오름 차순 정렬할 경우 1회전 후의 결과를 작성

 

• 9, 4, 5, 1, 3
• 1회전 : 4, 5, 1, 3, 9

이진 트리의 레코드 R = (88, 74, 63, 55, 37, 25, 33, 19, 26, 14, 9)에 대하여 힙(Heap)으로 구성했을 때, 37의 왼쪽과 오른쪽의 자노드(Child Node)의 값을 작성

 

• 14, 9

---

섹션4. 검색 - 이분 검색 / 해싱

 

1. 이분 검색(이진 검색)

 

• 반드시 순서화(정렬)된 파일이 있어야 검색할 수 있음
• 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦
• 탐색 효율이 좋고 탐색 시간이 적게 소요됨
• 중간 레코드 번호(M) : F + L / 2 (단, F: 첫 번째 레코드 번호, L:마지막 레코드 번호)

2. 주요 해싱 함수

 

• 제산법(Division) : 레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식
• 제곱법(Mid - Square) : 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식
• 폴딩법(Folding) : 레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식
• 숫자 분석법(Digit Analysis) : 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

3. 체이닝(Chaining)

 

• Collision이 발생하면 버킷에 할당된 연결 리스트(Linked List)에 데이터를 저장하여 문제를 해결하는 방법

다음과 같이 레코드가 구성되어 있을 때, 이진 검색 방법으로 10을 찾을 경우 비교되는 횟수를 계산

 

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

1회 비교	2회 비교	3회 비교
8	12	10

---

섹션5. 데이터베이스 개요

 

1. DBMS의 필수 기능

 

• 정의 기능(Definition) : 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기 위해 데이터베이스에 저장될 데이터의 형(Type)과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능
• 조작 기능(Manipulation) : 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 데이터베이스 사이의 인터페이스 수단을 제공하는 기능
• 제어 기능(Control) : 데이터베이스를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터 무결성이 유지되도록 제어하는 기능

2. 스키마 3계층

 

• 외부 스키마 : 사용자나 응용 프로그래머가 각 개인의 입장에서 필요로 하는 데이터베이스의 논리적 구조를 정의한 것
• 개념 스키마 : 데이터베이스의 전체적인 논리적 구조로서, 개체 간의 관계와 제약 조건을 나타내고, 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의함
• 내부 스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조로서 실제로 데이터베이스에 저장될 레코드의 형식을 정의하고 저장 데이터 항목의 표현 방법, 내부 레코드의 물리적 순서 등을 나타냄

---

섹션6. 절차형 SQL

 

1. 테스트와 디버깅의 목적

 

• 테스트(Test)를 통해 오류를 발견한 후 디버깅(Debugging)을 통해 오류가 발생한 소스 코드를 추적하며 수정