2과목 소프트웨어 개발 데이터 입/출력 구현 036 ~042

036. 자료 구조

- 효율적인 프로그램? :: 저장공간의 효율성 & 실행시간의 신속성.

- 자료구조 : 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리방법 등을 연구 분석하는 것.

- 일련의 자료들을 조직하고 구조화하는 것!

 

선형 구조(Linear Structure)	- 배열(Array) - 선형 리스트 (연속 리스트 & 연결 리스트) - 스택 - 큐 - 데크
비선형 구조 (Non-Linear Structure)	- 트리 - 그래프

 

1) 배열

: 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합.

- 정적인 자료구조로 기억장소의 추가가 어려움

- 데이터 삭제 시 그 기억장소는 빈 공간으로 남아있어 메모리의 낭비 발생.

- 반복적인 데이터 처리 작업에 적합

ex) a[n] >> n+1개의 기억장소

      b[n][n] >> (n+1) * (n+1) 개의 기억장소

 

2) 선형 리스트

: 일정한 순서에 의해 나열된 자료 구조(빈공간 없이 차례차례 데이터가 저장된다)

 

- 연속 리스트 (Contiguous List)

• 배열과 같이 연속되는 기억장소에 저장되는 자료 구조. 
• 연속적으로 기억장소를 배정받기에 기억장소 이용 효율은 밀도가 1로서 좋다. (빈 공간 없이 꽉 차게 사용한다는 의미)
• 중간에 데이터 삽입을 위해서는 연속된 빈 공간이 있어야 함.
• 삽입/삭제 시 자료의 이동이 필요함.

- 연결 리스트 (Linked List)

• 자료들을 반드시 연속적으로 배열시키지는 않고, 임의의 기억공간에 기억. + 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조. (포인터 : 현재 위치에서 다음 노드의 위치를 알려주는 요소)
• 노드의 삽입/삭제 작업 용이.
• 기억 공간이 연속적으로 놓여있지 않아도 저장 가능. 
• 순차 리스트에 비해 기억공간의 이용 효율이 좋지 않음. (연결을 위한 포인터 부분이 필요)
• 중간 노드 연결이 끊어지면 다음 노드 찾기 힘듦.

 

3) 스택 >> 컵 !!

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

- LIFO (Last In First Out) 후입 선출 방식.

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

- 스택이 꽉 채워져있는 상태에서 데이터 삽입 >> 오버플로우 발생 & 삭제할 데이터가 없는 상태에서 삭제 >> 언더플로우 발생.

• Top : 스택으로 할당된 기억 공간의 가장 마지막 삽입 자료가 기억된 위치를 가리키는 요소.  (스택 포인터)
• Bottom : 스택의 가장 밑바닥.
• M : 스택의 크기
• X : 스택의 이름

// 자료의 삽입 Push
Top = Top+1
If Top > M Then
	Overflow
Else
	X(Top) <- Item
    
// 자료의 삭제 Pop
If Top = 0 Then
	Underflow
Else 
	Item <- X(Top)
    Top = Top -1

 

4) 큐 (Queue) >> 빨대!!

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

- FIFO (First In First Out) 선입 선출 방식.

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

- 시작과 끝을 표시하는 두 개의 포인터가 있음.

• 프런트 포인터 (Front) : 가장 먼저 삽입된 자료의 기억공간을 가리키는 포인터. (삭제 작업 수행)
• 리어 포인터 (Rear) : 가장 마지막에 삽입된 자료가 위치한 기억 공간을 가리키는 포인터. (삽입 작업 수행)

 

5) 그래프

: 정점 V(Vertex)와 간선 E(Edge)의 두 집합으로 이루어짐. 

- 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분

- 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용

 

6) 트리

: 사이클이 없는 그래프.

 

 

037. 트리(Tree)

: 정점(Node)과 선분(Branch)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태. 

- 노드 : 하나의 기억 공간

- 링크 : 노드와 노드를 연결하는 선

- 가족의 계보, 조직도 등을 표현하기에 적합.

 

• 노드 : 트리의 기본 요소/ 자료 항목과 다른 항목에 대한 가지를 합친 것.
• 근 노드(Root Node) : 트리의 맨 위에 있는 노드
• 디그리 (Degree) : 각 노드에서 뻗어나온 가지 수 
• 단말 노드 (Terminal Node)/잎 노드(Leaf Node) : 자식이 하나도 없는 노드 (즉, 디그리가 0인 노드)
• 자식 노드 (Son Node) : 어떤 노드에 연결된 다음 레벨의 노드들
• 부모 노드 (Parent Node) : 어떤 노드에 연결된 이전 레벨의 노드들
• 형제 노드 (Brother Node) : 동일한 부모를 갖는 노드들
• 트리의 디그리 : 노드들의 디그리 중 가장 많은 수

 

-트리의 운행법 (Traversal)

: 트리를 구성하는 각 노드들을 찾아가는 방법 

1) Preorder 운행 : Root > Left > Right

2) Inorder 운행 : Left > Root > Right

3) Postorder 운행 : Left > Right > Root

 

1) A > B > D > H > I > E > C > F > G

2) H > D > I > B > E > A > F > C > G

3) H > I > D > E > B > F > G > C > A

 

 

 

 

 

 

 

 

- 수식의 표기법

: 산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진트리를 많이 사용함. 

1) 전위 표기법 (PreFix) : 연산자 > Left > Right         ex) +AB

2) 중위 표기법 (InFix) : Left > 연산자 > Right           ex) A+B

3) 후위 표기법 (PostFix) : Left > Right > 연산자      ex)AB+

 

- Infix 표기를 Postfix/Prefix로 바꾸기  

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

 

Prefix로 변환	- 연산 우선순위에 따라 괄호로 묶는다 (X = (((A/B) * (C+D))+E)) - 연산자를 해당 괄호 앞으로 옮긴다.  =(X + (*(/AB)+(CD))E)) - 필요없는 괄호 제거 =X+*/AB+CDE
Postfix로 변환	- 연산 우선순위에 따라 괄호로 묶는다. (X = (((A/B) * (C+D))+E)) - 연산자를 해당 괄호 뒤로 옮긴다. X((AB/)(CD+)*)E+)= - 필요없는 괄호 제거 XAB/CD+*E+=

 

- Postfix/Prefix를 Infix로 바꾸기

A B C - / D E F + * +

+ / A - B C * D + E F

Prefix	- 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다.  ((A (BC-) /) ( D (EF+) *) +) - 연산자를 해당 피연산자의 가운데로 이동시킨다.  ((A/(B-C)) + (D*(E+F))) - 필요없는 괄호 제거 A / (B-C) + D * (E+F)
Postfix	- 인접한 피연산자 두 개와 오른쪽의 연산자를 괄호로 묶는다.  (+ (/ A (-BC)) (*D(+EF))) - 연산자를 해당 피연산자의 가운데로 이동시킨다.  ((A/(B-C))+(D*(E+F))) - 필요없는 괄호 제거 A / (B-C) + D * (E+F)

 

038. 정렬(Sort)

1) 삽입 정렬

: 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬.

- 평균과 최악 모두 수행 시간 복잡도는 O(n^2)

초기상태 : 8 5 6 2 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) 쉘 정렬

: 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성, 각 서브파일을 Insertion 정렬 방식으로 순서 배열하는 과정을 반복. (즉, 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는 것을 반복!)

- 입력 파일이 부분적으로 정렬되어 있는 경우에 유리

- 평균 시간 복잡도 O(n^1.5) / 최악 시간복잡도 O(n^2)

 

3) 선택 정렬

: n개의 레코드 중에서 최소값을 찾아 첫번째 레코드 위치에 놓고, 나머지 (n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식 반복.

- 평균과 최악 모두 수행 시간 복잡도는 O(n^2)

초기상태 : 8 5 6 2 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

 

4) 버블 정렬

: 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식.

- 계속 정렬 여부를 플래그 비트(f)로 결정.

- 평균과 최악 모두 수행 시간 복잡도는 O(n^2)

초기상태 : 8 5 6 2 4

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 

4회전 : 2 4 5 6 8 

 

5) 퀵 정렬

: 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법.

- 키를 기준으로 작은 값을 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식

- 위치에 관계없이 임의의 키를 분할 원소로 사용 가능. 

- 스택이 필요.

- 분할과 정복을 통해 자료 정렬

• 분할 : 기준값인 피봇을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눔
• 정복 : 부분집합의 원소들 중 피봇보다 작은 원소들을 왼쪽, 피봇보다 큰 원소들을 오른쪽으로 정렬
• 부분집합의 크기가 더이상 나누어질 수 없을 때까지 > 분할/정복을 반복

- 평균 시간복잡도는 O(n log n) / 최악 시간복잡도 O(n^2)

 

6) 힙 정렬

: 전이진 트리(Complete Binary Tree)를 이용한 정렬 방식 

- 평균과 최악 모두 시간 복잡도는 O(n log n)

 

17, 14, 13, 15, 16, 19, 11, 18, 12를 힙 트리로 구성

- 전이진 트리의 노드의 역순으로 자식 노드와 부모 노드를 비교하여 큰 값을 위로 올린다.

 

7) 2-Way 합병 정렬 (Merge Sort)

: 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식. 

- 두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.

- 순서대로 정렬된 각 쌍의 키들을 합병하여 > 하나의 정렬된 서브리스트로 만든다. 

- 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복.

- 평균과 최악 모두 시간 복잡도는 O(n log n)

초기 상태 : 71, 2, 38, 5, 7, 61, 11, 26, 53, 42

1회전 : (71, 2) (38, 5) (7, 61) (11, 26) (53, 42) : 각각의 묶음 안에서 정렬 >> (2, 71) (5, 38) (7, 61) (11, 26) (42, 53)

2회전 : 묶여진 묶음을 두 개씩 묶은 후 ((2, 71) (5, 38))   ((7, 61) (11, 26))  (42, 53)

           각각의 묶음 안에서 정렬 >> (2, 5, 38, 71) (7, 11, 26, 61) (42, 53)

3회전 : ((2, 5, 38, 71) (7, 11, 26, 61))   (42, 53) 각각의 묶음 안에서 정렬 >>  (2, 5, 7, 11, 26, 38, 61, 71) (42, 53)

4회전 :  ((2, 5, 7, 11, 26, 38, 61, 71) (42, 53)) 각각의 묶음 안에서 정렬  >> (2, 5, 7, 11, 26, 38, 42, 53, 61, 71)

 

8) 기수 정렬 (Radix Sort/ Bucket Sort)

: Queue를 이용하여 자릿수별로 정렬하는 방식

- 레코드의 키 값을 분석하여 같은 수 또는 같은 문자끼리 그 순서에 맞는 버킷에 분배하였다가 > 버킷의 순서대로 레코드를 꺼내어 정렬.

- 평균과 최악 모두 시간 복잡도는 O(dn)

 

039. 검색 - 이분 검색/ 해싱

1) 이분 검색(이진 검색, Binary Search)

: 전체 파일을 두 개의 서브파일로 분리해가면서 Key 레코드를 검색하는 방식.

- 반드시 "순서화된" 파일이어야 검색 가능

- 찾고자 하는 Key 값을 파일의 중간 레코드 Key 값과 비교하면서 검색. 

- 비교 횟수를 거듭하면서 > 검색 대상의 데이터 수가 절반으로 줄어듦 > 탐색 효율이 좋고 시간이 적게 소요.

** 중간 레코드 번호 M = (Fisrt + Last) / 2

ex) 1~100에서 15를 찾는데 걸리는 횟수?

1회차 M = (1+100)/2 = 50.5 >> 50보다 작다

2회자 M = (1+49)/2 = 25 >> 25보다 작다

3회차 M = (1+24)/2 = 12.5 >> 12보다 크다

4회차 M = (13+24)/2 = 18.5 >> 18보다 작다

5회차 M = (13+17)/2 = 15 같다. 

answer == 5회

 

2) 해싱

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

- 해시 테이블 : 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간. 

• 버킷 : 하나의 주소를 갖는 파일의 한 구역. (버킷의 크기 =같은 주소에 포함될 수 있는 레코드 수)
• 슬롯 : 한 개의 레코드를 저장할 수 있는 공간. (n개의 슬롯 = 하나의 버킷)
• Collsion 충돌 현상 : 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상
• Synonym : 충돌로 인해 같은 홈 주소를 갖는 레코드들의 집합.
• Overflow : 계산된 홈주소의 버킷 내 저장할 기억공간이 없는 상태. (버킷을 구성하는 슬롯이 여러개일 때 충돌현상은 발생해도 오버플로우는 발생하지 않을 수도 있음)

- 해싱 함수 

• 제산법(Division) : 레코드 키를 해시표의 크기보다 큰 수 중에서 가장 작은 소수로 나눈 나머지를 홈 주소로 삼는 방식. (h(K) = K mod Prime)
• 제곱법 (Mid-Square) : 레코드 키 값을 제곱한 후 그 중간 부분의 값을 홈주소로 삼는 방식.
• 폴딩법 : 레코드 키 값을 여러 부분으로 나눈 후 각 부분의 값을 더하거나, XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식.
• 기수 변환법 (Radix) : 키 숫자의 진수를 다른 진수로 변환시켜 > 주소 크기를 초과한 높은 자릿수는 절단/ 다시 주소 범위에 맞게 조정
• 대수적 코딩법 (Algebraic Coding) : 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주 > 해시표의 크기에 의해 정의된 다항식으로 나누어 얻는 나머지 다항식의 계수를 홈 주소로 삼음
• 숫자 분석법 : 키 값을 이루는 숫자의 분포를 분석 > 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식
• 무작위법 : 난수를 발생시켜 나온 값을 홈주소로 삼음.

 

040. 데이터베이스 개요

- 데이터 저장소 : 데이터들의 논리적인 구조로 조직화하거나, 물리적인 공간에 구축한 것.

• 논리 데이터저장소 : 데이터 및 데이터 간의 연관성, 제약조건을 식별하여 논리적 구조로 조직화
• 물리 데이터저장소 : 논리 저장소에 저장된 데이터와 구조들을 소프트웨어가 운용될 환경의 물리적 특성을 고려하여 하드웨어적인 저장장치에 저장한 것.

- 데이터베이스 : 특정 조직의 업무를 수행하는데 필요한 상호 관련된 데이터들의 모임.

• 통합된 데이터
• 저장된 데이터
• 운영 데이터
• 공용 데이터

- DBMS : 사용자와 데이터베이스 사이에서 사용자 요구에 따라 정보를 생성해주고, 데이터베이스를 관리해주는 소프트웨어. 

• 정의 기능 (DDL) 
• 조작 기능 (DML)
• 제어 기능 (DCL)

장점	- 데이터의 논리적, 물리적 독립성 보장 - 데이터 중복 피할 수 있어 기억공간 절약 - 저장된 자료 공동으로 이용 가능 - 데이터의 일관성/ 무결성 유지  - 보안 유지 - 데이터 표준화 & 통합하여 관리 가능 - 항상 최신의 데이터 유지 - 데이터 실시간 처리 가능
단점	- 데이터베이스 전문가 부족 - 전산화 비용 증가 - 대용량 디스크로 집중적인 접근으로 과부하 발생 - 파일의 예비(backup)와 회복(recovery)가 어려움 - 시스템 복잡

 

- 스키마 

: 데이터베이스의 구조와 제약 조건에 관한 전반적인 명세를 기술한 메타데이터.

- 데이터베이스를 구성하는 데이터 개체(Entity), 속성(Attribute), 관계(Relationship) 및 데이터 조작 시 데이터 값들이 갖는 제약 조건 등.

- 외부 스키마 : 데이터 베이스의 논리적 구조 정의

- 개념 스키마 : 전체적 논리적 구조. 모든 사용자들이 필요로 하는 데이터를 종합한 조직 전체의 데이터베이스. (개체 간의 관계, 제약조건, 접근 권한, 보안 및 무결성 규칙)

- 내부 스키마 : 물리적 저장장치의 입장에서 본 데이터베이스 구조. (실제 저장될 레코드의 형식 정의, 항목 표현 방법, 내부 레코드의 물리적 순서 등)

 

 

041. 데이터 입/출력

: 데이터를 조작하는 모든 행위. SQL을 사용. 

- 데이터 접속(Data Mapping) : 데이터 입출력을 위해 개발 코드 내에 SQL 코드를 삽입하거나, 객체와 데이터를 연결하는 것.

- 트랜잭션 : 데이터베이스 조작할 때 하나의 논리적 기능을 수행하기 위한 작업의 단위/ 한꺼번에 수행되어야 할 일련의 연산들. 

 

- SQL(Structured Query Language)

: 관계대수/ 관계해석을 기초로 한 혼합 데이터 언어.

• DDL 데이터 정의어 : SCHEMA, DOMAIN, TABLE, VIEW, INDEX를 정의하거나 변경/삭제 할 때 사용
• DML 데이터 조작어 : 저장된 데이터를 실질적으로 처리하는데 사용
• DCL 데이터 제어어 : 보안, 무결성, 회복, 병행 수행 제어 등 정의하는데 사용.

- 데이터 접속 (Data Mapping)

• SQL Mapping: 코드 내에 직접 SQL을 입력하여 DBMS의 데이터에 접속 (JDBC, ODBC, MyBatis 등)
• ORM (Object-Relational Mapping) : 객체지향 프로그래밍의 객체와 관계형 데이터베이스의 데이터를 연결하는 기술. (JPA, Hibernate, Django 등)

- 트랜잭션

• TCL(Transaction Control Language) 
• COMMIT : 트랜잭션 처리가 정상적으로 종료되어 트랜잭션이 수행한 변경 내용을 데이터베이스에 반영하는 명령어
• ROLLBACK : 하나의 트랜잭션 처리가 비정상으로 종료되어 데이터베이스의 일관성이 깨졌을 때 트랜잭션이 행한 모든 변경 작업을 취소하고 이전 상태로 되돌리는 연산
• SAVEPOINT(=CHECKPOINT) : 트랜잭션 내에 ROLLBACK할 위치인 저장점을 지정하는 명령어

 

042. 절차형 SQL

: C, JAVA 등의 프로그래밍 언어와 같이 연속적인 실행이나 분기, 반복 등의 제어가 가능한 SQL. 

- 단일 SQL문장으로 처리하기 어려운 연속적인 작업들을 처리하는데 적합.

- 다양한 기능을 수행하는 저장 모듈 생성 가능. 

- DBMS 엔진에서 직접 실행되기 때문에 입출력 패킷이 적은 편

- BEGIN ~ END 형식으로 작성되는 블록 구조로 되어 있기 때문에 기능별 모듈화가 가능. 

• 프로시저 : 특정 기능을 수행하는 일종의 트랜잭션 언어. 호출을 통해 실행되어 미리 저장해 놓은 SQL 작업을 수행. 
• 트리거 : 데이터베이스 시스템에서 데이터의 입력, 갱신, 삭제 등의 이벤트가 발생할 때마다 관련 작업이 자동으로 수행. 
• 사용자 점의 함수 : 프로시저와 유사하게 SQL을 사용하여 일련의 작업을 연속적으로 처리. 종료시 예약어 Return을 사용하여 처리 결과를 단일값으로 반환. 

- 테스트와 디버깅

: 디버깅을 통해 기능의 적합성 여부를 검증.  실행을 통해 결과를 확인하는 테스트 과정을 수행. 

-  구문 오류나 참조 오류의 존재 여부 확인. 

 

- 쿼리 성능 최적화

: 데이터 입출력 애플리케이션의 성능 향상을 위해 SQL 코드를 최적화하는 것. 

- APM(Application Performance Management/Monitoring 성능 측정 도구)을 사용하여 최적화할 쿼리 선정. 

- 최적화 할 쿼리에 대해 옵티마이저가 수립한 실행계획 검토, sql 코드와 인덱스 재구성.