1. 데이터 입 출력 구현

자료구조

가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성.

분류

선형구조: 배열, 선형 리스트(continuous list, linked list), 스택, 큐, 디큐 

비선형구조: 트리, 그래프 

연속리스트 - 중간에 데이터를 추가 하거나 삭제하려면 해당 위치 이후의 모든 자료의 이동이 필요하다. 기억장소의 효율은 밀도가 1로서 가장 좋다.

연결리스트(Linked List) - 노드의 삽입 삭제 작업이 용이. 연결을 위한 포인터 필요부분이 필요하기 때문에, 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다. 포인터 찾는 시간 때문에 선형에 비해 접근 속도가 느림.

스택 (Stack) - 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어짐. LIFO 방식으로 자료 처리. 재귀 호출, 후위(postfix), 표기법, 깊이 우선 탐색 과 같이 왔던 길을 되돌아가는 경우에 사용. 삽입은 스택에 자료를 입력하는 명령이고, 삭제는 스택에서 자료를 출력하는 명령이다.

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

스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로우가 발생. 더이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로가 발생한다. 

큐 (Queue) - 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조. FIFO 방식으로 처리. 헤드와 테일의 2개의 포인터를 갖고 있다. 응용분야로는 운영체제의 작업 스케줄링. 

디큐 (Deque) - 삽입과 삭제가 리스트의 양쪽 끝에서 모두 가능한 자료 구조. 입력은 한쪽에만 발생하고 출력은 양쪽에서 일어날 수 있는 입력 제한과, 입력은 양쪽에서 출력은 한쪽에서만 이루어지는 출력 제한이 있다. 

그래프  - 정점과 간선의 두집합으로 이루어지고 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분됨. 통신망, 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용. 

방향/무방향 그래프의 최대 간선수 - n개의 정점으로 구성된 무방향 그래프에서 최대 간선수는 n(n-1)/2 이고, 방향 그래프에서 최대 간선수는 n(n-1) 이다. 

---

트리(Tree) 

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

수식 표기법 (infix -> postfix) - infix로 표기된 수식에서 연산자를 해당 피연산자 두개의 뒤에 오도록 이동하면 postfix가 된다.

예시) X = A/B * (C+D) + E -> XAB/CD+*E+=

(A+B)*C+(D+E) -> AB+C*DE++ 

---

정렬(Sort) 

삽입정렬 - 가장 간단한 정렬방식으로, 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬. n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식. 

예시) 8 - 5 - 6 - 2 - 4 을 삽입정렬로 정렬하시오. 

5 - 8 - 6 - 2 - 4 (8 vs. 5) 

5 - 6 - 8 - 2 - 4 (5 vs. 8 vs. 6)

2 - 5 - 6 - 8 - 4 (5 vs. 6 vs. 8 vs. 2)

2 - 4 - 5 - 6 - 8 (2 vs. 5 vs. 6 vs. 8 vs. 4) 

쉘 정렬 - 삽입 정렬을 확장한 개념이다. 입력 파일을 어떤 매개변수(h)의 값으로 서브파일을 구성하고, 각 서브파일을 삽입 정렬 방식으로 순서 배열하는 과정을 반복하는 정렬 방식. 임의의 레코드 키와 h값만큼 떨어진 곳의 레코드 키를 비교하여 순서화되어 있지 않으면 서로 교환하는것을 반복하는 방식. 입력 파일이 부분적으로 정렬되어 있는 경우에 유리하다. 평균수행 시간 복잡도는 O(n^1.5) 최악의 수행 시간 복잡도는 O(n^2) 이다.

선택 정렬 - n개의 레코드 중에서 최소값을 찾아 첫번재 레코드 위치에 놓고, 나머지(n-1)개 중에서 다시 최소값을 찾아 두번째 레코드 위치에 놓는 방식을 반복하여 정렬하는 방식. 평균과 최악 모두 수행 시간 복잡도는 O(n^2) 

예시) 8 - 5 - 6 - 2 - 4 를 선택 정렬로 정렬하시오. 

1회전: 5 - 8 - 6 - 2 - 4 (8 vs. 5) -> 5 - 8 - 6 - 2 - 4 (5 vs. 6) -> 2 - 8 - 6 - 5 - 4 (5 vs. 2) -> 2 - 8 - 6 - 5 - 4 (2 vs. 4) 

2회전: 2 - 6 - 8 - 5 - 4 (8 vs. 6) -> 2 - 5 - 8 - 6 - 4 (6 vs. 5) -> 2 - 5 - 8 - 6 - 4 (5 vs. 6) -> 2 - 4 - 8 - 6 - 5 (5 vs. 4) 

3회전: 2 - 4 - 6 - 8 - 5 (8 vs. 6) -> 2 - 4 - 5 - 8 - 6 (6 vs. 5)  

4회전: 2 - 4 - 5 - 6 - 8 (8 vs. 6) 

 

버블 정렬 - 주어진 파일에서 인접한 두개의 레코드 키 값을 비교하여 그 크기에 다라 레코드 위치를 서로 교환하는 정렬 방식. 계속 정렬 여부를 플래그 비트(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 - 6 - 2 - 4 - 8 -> 5 - 2 - 6 - 4 - 8 -> 5 - 2 - 4 - 6 - 8 -> 5 - 2 - 4 - 6 - 8 

3회전: 2 - 5 - 4 - 6 - 8 -> 2 - 4 - 5 - 6 - 8 

4회전: 2 - 4 - 5 - 6 - 8 

 

퀵 정렬 - 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법. 키를 기준으로 작은 값은 왼쪽에 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬.  피봇을 사용하며 최악의 경우 n(n-1)/2 회의 비교를 수행 한다. 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있고, 정렬 방식 중에서 가장 빠른 방식. 프로그램에서 되부름 이용하기 때문에 스택이 필요. 분할과정복(Divide and Conquer)을 통해 자료를 정렬한다. 

분할: 기준값이 피봇을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눈다. 

정복: 부분집합의 원소들 중 피봇보다 작은 원소들은 왼쪽, 피봇보다 큰 원소들은 오른쪽 부분집합으로 정렬한다. 부분집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복수행하며, 평균 시간 복잡도는 O(nlogn), 최악의 수행 시간 복잡도는 O(n^2) 이다. 

 

힙 정렬 - 전이진 트리(Complete Binary Tree) 를 이용한 정렬 방식. 평균과 최악 시간 복잡도 모두 O(nlogn). 1 주어진 파일의 레코들을 전이진 트리로 구성한다음. 2. 전이진 트리의 노드의 역순으로 자식노드와 부모 노드를 비교하여 큰 값을 위로 올린다. 3. 교환된 노드들을 다시 검토하여 위의 과정을 반복한다. 정렬할 입력 레코드를로 힙을 구성하고 가장 큰 키 값을 갖는 루트 노드를 제거하는 과정을 바복하여 정렬하는 기법. 

 

2-Way 합병 정렬(Merge Sort)

이미 정렬되어 있는 두개의 파일을 한개의 파일로 합병하는 정렬 방식. 두개의 키들을 한 쌍으로 하여 각쌍에 대하여 순서를 정한다. 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다. 위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다. 평균과 최악 모두 시간 복잡도는 O(nlongn)

예제) 71, 2, 38, 5, 7, 61, 11, 26, 53, 42 를 2-Way 합병 정렬 하시오. 

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)

---

검색-이분검색/해싱

이분검색 - 반드시 순서화(정렬)된 파일이어야 검색 가능하다.

비교 횟수를 거듭할 때마다 검색 대상의 데이터 수가 절반으로 줄어든다. 

탐색 효율이 좋고 탐색 시간이 적게 소요된다. 

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

해시 테이블 - 레코드를 한 개 이상 보관할 수 있는 버킷들로 구성된 기억공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수 도 있다. 

 

해싱함수 종류: 

제산법(Division) - 키를 해시표의 크기보다 큰 수중 가장 작은 소수로 나눈 나머지를 홈 주소로 

제곱법(Mid Squre)  - 키 값을 제곱한 후 그 중간 부분의 값을 홈 주소로 

폴딩법(Folding) - 레코드 키를 여러부분으로 나누고, 나눈 부분의 각 숫자를 더하거나 XOR한 값을 홈 주소로 사용하는 방식

기수 변환법 (Radix) - 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고 이를 다시 주소 범위에 맞게 조정하는 방법 

대수적 코딩법(Algebraic Coding) - 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계수로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식 

숫자 분석법/계수 분석법(Digit analysis) - 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식

무작위법(Random) - 랜덤 넘버를 발생시켜서 나온 값 

 

충돌현상 해결방법:

Chaining - Linked List에 삽입하여 문제를 해결하는 기법. 해시 함수가 서로 다른 키에 대해 같은 주소값을 반환해서 충돌이 발생하면 각 데이터를 해당 주소에 있는 링크 리스트에 삽입하여 문제를 해결하는 기법. 

개방 주소법 - 순차적으로 그 다음 빈 버킷을 찾아 데이터를 저장하는 방법 

재해싱 - 새로운 해싱 함수로 새로운 홈 주소를 구하는 방법 

---

데이터베이스 

소프트웨어 개발 과정에서 다루어야 할 데이터들을 논리적인 구조로 조직화하거나, 물리적인 공간에 구축한 것.

통합된 데이터(Intergrated Data) - 자료의 중복을 배제한 데이터의 모임

저장된 데이터(Stored Data) - 컴퓨터가 접근할 수 있는 저장 매체에 저장된 자료

운영데이터(Operational Data) - 조직의 고유한 업무를 수행하는데 존재 가치가 확시하고 없어서는 안될 반드시 필요한

공용 데이터(Shared Data) - 여러 응용 시스템들이 공동으로 소유하고 유지하는 자료 

 

데이터베이스 관리시스템

기존의 파일시스템이 갖는 데이터의 종속성과 중복성의 문제를 해결 하기 위해 제안된 시스템으로, 모든 응용 프로그램들이 데이터베이스를 고용할 수 있도록 관리. 데이터베이스의 구성, 접근 방법, 유지관리에 대한 모든 책임을 지고 필수 기능에는 정의, 조작, 제어 기능이 있다.

정의 기능: 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기 위해 데이터베이스에 저장될 데이터의 형과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능 

조작 기능(Manipulation) - 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 데이터베이스 사이의 인터페이스 수단을 제공하는 기능 

제어 기능(Control) - 데이터베이스를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어하는 기능. 제어 기능의 핵심은 무결성, 보안, 권한, 병행 제어. 

 

데이터베이스 관리시스템 장/단점 

장점:

데이터의 논리적*, 물리적* 독립성이 보장된다.

중복을 피할 수 있어 기억 공간이 절약된다. 

저장된 자료를 공동으로 이용할 수 있다.

일관성, 무결성, 보안을 유지 할 수 있다. 

데이터 표준화가 가능하고 데이터를 통합하여 관리 할 수 있다. 

항상 최신의 데이터를 유지하고 데이터의 실시간 처리가 가능하다.

단점: 

데이터베이스의 전문가가 부족하고 전산화 비용이 증가한다.

대용량 디스크로의 집중적인 Access 로 과부하가 발생한다. 

파일의 예비(bakcup)와 회복(reveory)이 어렵고 시스템이 복잡하다. 

 

논리적 독립성 - 데이터의 논리적 구조를 변경시키더라도 응용 프로그램은 변경 되지 않음. 

물리적 독립성 - 응용 프로그램과 보조기억장치 같은 물리적 장치를 독립. 시스템 향상을 위해 새로운 디스크를 도입하더라도 응용 프로그램에 영향을 주지 않음. 

 

스키마

스키마는 데이터베이스의 구조와 제약 조건에 관한 전반적인 명세(Specificatin)를 기술(Description) 한 메타데이터의 집합이다. 데이터 개체(엔티티), 속성(에트리뷰트), 관계 및 데이터 조작시 데이터 값들이 갖는 제양ㄱ 조건 등에 관해 전반적으로 정의. 사용자 관점에 따라 외부, 개념, 내부 스키마로 나뉜다.

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

개념 스키마 - 데이터베이스의 전체적인 논리적 구조로서 개체 간의 관계와 제약 조건을 나타내고, 데이터베이스의 접근 권한, 보안 및 무결성 규칙에 관한 명세를 정의함. 데이터베이스 전체를 정희한것. 

내부 스키마 - 물리적 저장장치의 입장에서 본 데이터베이스 구조로서, 실제로 데이터베이스에 저장될 레코드의 형식을 정의하고 저장 데이터 항목의 표현방법, 내부 레코드의 물리적 순서 등을 나타냄 

 

---

절차형 SQL 

프로시저 - 특정기능을 수행하는 일종의 트랜잭션 언어로, 호출을 통해 실행되어 미리 저장해 놓은 SQL 작업을 수행한다. 처리 결과를 반환하지 않거나, 핸 개 이상의 값을 반환한다. 

트리거 - 데이터베이스 시스템에서 데이터의 입력, 갱신, 삭제 등의 이벤트가 발생할 때마다 관련 작업이 자동으로 수행된다. 

사용자 정의 함수 - 프로시저와 유사하게 SQL을 사용하여 일련의 작업을 연속적으로 처리하며, 종료시 예약어 return을 사용하여 처리 결과를 단일값으로 반환한다. 

테스트와 디버깅의 목적 - 테스트를 통해 오류를 발견한 후 디버깅을 통해 오류가 발생한 소스 코드를 추적하며 수정한다.

최적화까지의 과정 - 절차형 SQL을 생성 할 때 오류가 발생했다면 SHOW 명령을 통해 오류 내용을 확인하다. 절차형 SQL을 실행하기 전에 디버깅을 통해 로직을 검증하고 디버깅할때에는 데이터베이스의 데이터들이 변경되지 않도록 관련코드를 주석으로 처리한다. 절차형 SQL의 성능이 느리다면, 성능 측정 도구인 APM을 사용하여 각 쿼리의 성능을 확인한후 성능이 덜어지는 쿼리를 대상으로 최적화를 실행 할 수 있다. 

---