소프트웨어 개발 1장 데이터 입출력 구현

Updated: February 25, 2024

자료 구조

자료 구조의 정의

　효율적인 프로그램을 작성할 때 가장 우선적인 고려사항은 저장 공간의 효율성과 실행시간의 신속성이다. 자료 구조는 프로그램에서 사용하기 위한 자료를 기억장치의 공간 내에 저장하는 방법과 저장된 그룹 내에 존재하는 자료 간의 관계, 처리 방법 등을 연구 분석하는 것을 말한다.

선형 구조(Linear Structure): 배열(Array), 선형 리스트(Linear List), 연속 리스트(Contiguous List), 연결 리스트(Linked List), 스택(Stack), 큐(Queue), 텍(Deque)
비선형 구조(Non-Linear Structure): 트리(Tree), 그래프(Graph)

배열(Array)

　배열은 동일한 자료형의 데이터들이 같은 크기로 나열되어 순서를 갖고 있는 집합이다. 배열은 정적인 자료 구조로 기억 장소의 추가가 어렵고, 데이터 삭제 시 데이터기 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 발생한다. 배열은 첨자를 이용해 데이터에 접근하고 반복적인 데이터 처리 작업에 적합한 구조이다. 배열은 데이터마다 동일한 이름의 변수를 사용하여 처리하 간편하고 사용한 첨자의 개수에 따라 n차원 배열이라고 부른다.

선형 리스트(Linear List)

　선형 리스트는 일정한 순서에 의해 나열된 자료 구조이다. 선형 리스트는 배열을 이용하는 연속 리스트(Contiguous List)와 포인터를 이용하는 연결 리스트(Linked List)로 구분된다.

연속 리스트(Contiguous List)
- 연속 리스트는 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.
- 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1ㅇ로서 가장 좋다.
- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입•삭제 시 자료의 이동이 필요하다.
연결 리스트(Linked List)
- 연결 리스트는 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항복의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.
- 노드의 삽입•삭제 작업이 용이하다.
- 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.
- 연결을 위한 링크(포인터) 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.
- 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.
- 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

스택(Stack)

　스택은 리스트의 한쪽 끝으로만 자료의 삽입, 삭제 작업이 이루어지는 자료 구조이다. 스택은 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO; Last-In First-Out) 방식으로 자료를 처리한다. 함수 호출의 순서 제어, 인터럽트의 처리, 수식 계산 및 수식 표기법, 컴파일러를 이용한 언어 번역, 부 프로그램 호출 시 복귀 주소 저장, 서브루틴 호출 및 복귀 주소 저장에 사용된다.
　스택의 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.

TOP: 스택으로 할당된 기억 공간에 가장 마지막으로 삽입된 자료가 기억된 위치를 가리키는 요소이다.
Bottom: 스택의 가장 밑바닥이다.
Push: 자료의 삽입
Pop: 자료의 삭제

큐(Queue)

　큐는 리스트의 한쪽에서는 삽입 작업이 이루어지고 다른 한쪽에서는 삭제 작업이 이루어지도록 구성한 자료 구조이다. 큐는 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO; First-In First-Out) 방식으로 처리한다. 큐는 시작과 끝을 표시하는 두 개의 포인터가 있다. 큐는 운영체제의 작업 스케줄링에 사용한다.

프런트(F, Front) 포인터: 가장 먼저 삽입된 자료의 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.
리어(R, Rear) 포인터: 가장 마지막에 삽입된 자료가 위치한 공간을 가리키는 포인터로, 삽입 작업을 할 때 사용한다.

덱(Deque)

　덱(Deque; Double Ended Queue)은 삽입과 삭제가 리스트의 양쪽 끝에서 모두 발생할 수 있는 자료 구조이다. Stack과 Queue의 장점만 따서 구성한 것이다. 입력이 한쪽에서만 발생하고 출력은 양쪽에서 일어날 수 잇는 입력 제한과, 입력은 양쪽에서 일어나고 출력은 한 곳에서만 이루어지는 출력 제한이 있다.

입력 제한 덱: Scroll
출력 제한 덱: Shelf

그래프

　그래프 G는 정점 V(Vertex)와 간선 E(Edeg)의 두 집합으로 이루어진다. 간선의 방향성 유무에 따라 방향 그래프와 무방향 그래프로 구분된다. 통신망(Network), 교통망, 이항관계, 연립방정식, 유기화학 구조식, 무향선분 해법 등에 응용된다. 트리(Tree)는 사이클이 없는 그래프(Graph)이다.

트리(Tree)

트리의 개요

　트리는 정점(Node, 노드)와 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프(Graph)의 특수한 형태이다. 트리는 하나의 기억 공간을 노드(Node)라고 하며, 노드와 노드를 연결하는 선을 링크(Link)라고 한다. 가족의 계보(족보), 조직도 등을 표현하기에 적합하다.

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

트리의 운행법

　트리를 구성하는 각 노드들을 찾아가는 방법을 운행법(Traversal)이라 한다. 이진 트리를 운행하는 방법은 산술식의 표기법과 연관성을 갖는다. 이진 트리의 운행법은 다음 세 가지가 있다.

Preorder 운행: Root, Left, Right 순으로 운행한다. A, B, C
Inorder 운행: Left, Root, Right 순으로 운행한다. B, A, C
Postorder 운행: Left, Right, Root 순으로 운행한다. B, C, A

수식의 표기법

　산술식을 계산하기 위해 기억공간에 기억시키는 방법으로 이진 트리를 많이 사용한다. 이진 트리로 만들어진 수식을 인오더, 프리오더, 포스트오더로 운행하면 각각 중위(Infix), 전위(Prefix), 후위(Postfix) 표기법이 된다.

전위 표기법(PreFix): 연산자, Left, Right, +AB
중위 표기법(InFix): Left, 연산자, Right, A+B
후위 표기법(PostFix): Left, Right, 연산자, AB+

정렬(Sort)

삽입 정렬(Insertion Sort)

　삽입 정렬은 가장 간단한 정렬 방식으로 이미 순서화된 파일에 새로운 하나의 레코드를 순서에 맞게 삽입시켜 정렬한다. 두 번째 키와 첫 번째 키를 비교해 순서대로 나열하고, 이어서 세 번째 키를 첫 번째, 두 번째 키와 비교해 순서대로 나열하고, 계속해서 n번째 키를 앞의 n-1개의 키와 비교하여 알맞은 순서에 삽입하여 정렬하는 방식이다. 평균과 최악 모두 수행 시간 복잡도는 O($n^2$)이다.

쉘 정렬(Shell Sort)

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

선택 정렬(Selection Sort)

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

버블 정렬(Bubble Sort)

　버블 정렬은 주어진 파일에서 인접한 두 개의 레코드 키 값을 비교하여 그 크기에 따라 레코드 위치를 서로 교환하는 정렬 방식이다. 계속 정렬 여부를 플래그 비트(f)로 결정한다. 평균과 최악 모두 수행 시간 복잡도는 O($n^2$)이다.

큌 정렬(Quick Sort)

　퀵 정렬은 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어 가면서 정렬하는 방법으로 키를 기준으로 작은 값은 왼쪽에, 큰 값은 오른쪽 서브파일로 분해시키는 방식으로 정렬한다. 위치에 관계없이 임의의 키를 분할 원소로 사용할 수 있고 정렬 방식 중에서 가장 빠른 방식이다. 프로그램에서 되부름을 이용하기 때문에 스택이 필요하다. 분할과 정복을 통해 자료를 정렬한다. 평균 수행 시간 복잡도는 O(nlogn)이고, 최악의 수행 시간 복잡도는 O($n^2$)이다.

분할(Divide): 기준값인 비봇(Pivot)을 중심으로 정렬할 자료들을 2개의 부분집합으로 나눈다.
정복(Conquer): 부분집합의 원소들 중 피봇(Pivot)보다 작은 원소들은 왼쪽, 피봇보다 큰 원소들은 오른쪽 부분집합으로 정렬한다.
부분 집합의 크기가 더 이상 나누어질 수 없을 때까지 분할과 정복을 반복 수행한다.

힙 정렬(Heap Sort)

　힙 정렬은 완전 이진 트리(Complete Binary Tree)를 이용한 정렬 방식이다. 구성된 완전 이진 트리를 Heap Tree로 변환하여 정렬한다. 평균과 최악 모두 시간 복잡도는 O(nlogn)이다.

2-Way 합병 정렬(Merge Sort)

　2-Way Merge Sort는 이미 정렬되어 있는 두 개의 파일을 한 개의 파일로 합병하는 정렬 방식이다. 평균과 최악 모두 시간 복잡도는 O(nlogn)이다.

두 개의 키들을 한 쌍으로 하여 각 쌍에 대하여 순서를 정한다.
순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브리스트로 만든다.
위 과정에서 정렬된 서브리스트들을 하나의 정렬된 파일이 될 때까지 반복한다.

기수 정렬(Radix Sort), Bucket Sort

　기수 정렬은 Queue를 이용하여 자릿수(Digit)별로 정렬하는 방식이다. 레코드의 키 값을 분석하여 같은 수 또는 같은 문자까리 그 순서에 맞는 버킷에 분배 하였다가 버킷의 순서대로 레코드를 꺼내어 정렬한다. 평균과 최악 모두 시간 복잡도는 O(dn)이다.

검색-이분 검색/해싱

이분 검색

　이분 검색(이진 검색, Binary Search)은 전체 파일을 두 개의 서브 파일로 분리해가면서 Key 레코드를 검색하는 방식으로 반드시 순서화된 파일이어야 검색할 수 있다. 찾고자 하는 Key 값을 파일의 중간 레토드 Key 값과 비교하면서 검색한다. 비교 횟수를 거듭할 때마다 검색 대상이 되는 데이터의 수가 절반으로 줄어듦으로 탐색 효율이 좋고 탐색 시간이 적게 소요된다. 중간 레코드 번호 $M = \frac{(F + L)}{2}$ 이다.

해싱

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

해시 테이블(Hash Table): 레코드를 한 개 이상 보관할 수 있는 버킥들로 구성된 기억 공간으로, 보조기억장치에 구성할 수도 있고 주기억장치에 구성할 수도 있다.
- 버킷(Bucket)
  - 하나의 주소를 갖는 파일의 한 구역을 의미한다.
  - 버킷의 크기는 같은 주소에 포함될 수 있는 레코드 수를 의미한다.
- 슬롯(Slot)
  - 한 개의 레코드를 저장할 수 있는 공간으로 n개의 슬롯이 모여 하나의 버킷을 형성한다.
- 충돌 현상(Collision)
  - 서로 다른 두 개 이상의 레코드가 같은 주소를 갖는 현상이다. 해결 방법은 다음과 같다.
  - 체이닝(Chaining): Collision이 발생하면 버킷에 할당된 연결 리스트(Linked List)에 데이터를 저장하는 방법
  - 개방 주소법(Open Addressing): Collision이 발생하면 순차적으로 그 다음 빈 버킷을 찾아 데이터를 저장하는 방법
  - 재해싱(Rehashing): Collision이 발생하면 새로운 해싱 함수로 홈 주소를 구현하는 방법
- Synonym:
  - 충돌로 인해 같은 Home Address를 갖는 레코드들의 집합이다.
- Overflow
  - 계산된 Home Address의 Bucket 내에 저장할 기억공간이 없는 상태로, Bucket을 구성하는 Slot이 여러 개일 때 Collision은 발생하고 Overflow는 발생하지 않을 수 있다.
해시 함수(Hash Function)
- 제산법(Division)
  - 레코드 키(K)를 해시표(Hash Table)의 크기보다 큰 수 중에서 가장 작은 소수(Prime, Q)로 나눈 나머지를 홈 주소로 삼는 방식, 즉 h(K) = k mod Q이다.
- 제곱법(Mid-Square)
  - 레코드 키 값(K)을 제곱한 후 그 중간 부분의 값을 홈 주소로 삼는 방식이다.
- 폴딩법(Folding)
  - 레코드 키 값(K)을 여러 부분으로 나눈 후 각 부분의 값을 더하거나 XOR(배타적 논리합)한 값을 홈 주소로 삼는 방식이다
- 기수 변환법(Radix)
  - 키 숫자의 진수를 다른 진수로 변환시켜 주소 크기를 초과한 높은 자릿수는 절단하고, 이를 다시 주소 범위에 맞게 조정하는 방법이다.
- 대수적 코딩법(Algebraic Coding)
  - 키 값을 이루고 있는 각 자리의 비트 수를 한 다항식의 계구로 간주하고, 이 다항식을 해시표의 크기에 의해 정의된 다항식으로 나누어 얻은 나머지 다항식의 계수를 홈 주소로 삼는 방식이다.
- 숫자 분석법(Digit Analysis, 계수 분석법)
  - 키 값을 이루는 숫자의 분포를 분석하여 비교적 고른 자리를 필요한 만큼 택해서 홈 주소로 삼는 방식이다.
- 무작위법(Random)
  - 난수(Random Number)를 발생시켜 나온 값을 홈 주소로 삼는 방식이다.

데이터베이스 개요

데이터저장소

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

데이터저장소는 논리 데이터저장소와 물리 데이터저장소로 구분된다.
논리 데이터저장소는 데이터 및 데이터 간의 연관성, 제약조건을 식별하여 논리적인 구조로 조직화한 것을 의미한다.
물리 데이터저장소는 논리 데이터저장소에 저장된 데이터와 구조들을 소프트웨어가 운용될 환경의 물리적 특성을 고려하여 하드웨어적인 저장장치에 저장한 것을 의미한다.
논리 데이터저장소를 거쳐 물리 데이터저장소를 구축하는 과정은 데이터베이스를 구축하는 과정과 동일한다.

데이터베이스

　데이터베이스는 특정 조직의 업무를 수행하는 데 필요한 상호 관련된 데이터들의 모임으로 다음과 같이 정의할 수 있다.

통합된 데이터(Integrated Data): 자료의 중복을 배제한 데이터의 모임이다.
저장된 데이터(Stored Data): 컴퓨터가 접근할 수 있는 저장 매체에 저장된 자료이다.
운영 데이터(Operational Data): 조직의 고유한 업무를 수행하는 데 존재 가치가 확실하고 없어서는 안 될 반드시 필요한 자료이다.
공용 데이터(Shared Data): 여러 응용 시스템들이 공동으로 소유하고 유지하는 자료이다.

DBMS(DataBase Management System; 데이터베이스 관리 시스템)

　DBMS란 사용자와 데이터베이스 사이에서 사용자의 요구에 따라 정보를 생성해주고, 데이터베이스를 관리해 주는 소프트웨어이다. DBMS는 기존의 파일 시스템이 갖는 데이터의 종속성과 중복성의 문제를 해결하기 위해 제안된 시스템으로, 모든 응용 프로그램들이 데이터베이스를 공용할 수 있도록 관리해준다. DBMS는 데이터베이스의 구성, 접근 방법, 유지관리에 대한 모든 책임을 진다.
　DBMS의 필수 기능은 다음과 같다.

정의(Definition) 기능
- 모든 응용 프로그램들이 요구하는 데이터 구조를 지원하기 위해 데이터베이스에 저장될 데이터의 형(Type)과 구조에 대한 정의, 이용 방식, 제약 조건 등을 명시하는 기능이다.
조작(Manipulation) 기능
- 데이터 검색, 갱신, 삽입, 삭제 등을 체계적으로 처리하기 위해 사용자와 데이터베이스 사이의 인터페이스 수단을 제공하는 기능이다.
제어(Control) 기능
- 데이터베이스를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어해야 한다.
- 정당한 사용자가 허가된 데이터만 접근할 수 있도록 보안(Security)을 유지하고 권한(Authority)을 검사할 수 있어야 한다.
- 여러 사용자가 데이터베이스를 동시에 접근하여 데이터를 처리할 때 처리 결과가 항상 정확성을 유지하도록 병행 제어(Concurrency Control)를 할 수 있어야 한다.

DBMS의 장단점

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

스키마

　스키마(Schema)는 데이터베이스의 구조와 제약 조건에 관한 전반적인 명세(Specification)를 기숭(Description)한 메타데이터(Meta-Data)의 집합이다. 스키마는 데이터베이스를 구성하는 데이터 개체(Entity), 속성(Attribute), 관계(Relationship) 및 데이터 조작 시 데이터 값들이 갖는 제약 조건 등에 관해 전반적으로 정의한다. 스키마의 종류는 다음과 같다.

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

절차형 SQL

절차형 SQL의 개요

　절차형 SQL은 C, JAVA 등의 프로그래밍 언어와 같이 연속적인 실행이나 분기, 반복 등의 제어가 가능한 SQL을 의미한다. 일반적인 프로그래밍 언어에 비해 효율은 떨어지지만 단일 SQL 문장으로 처리하기 어려운 연속적인 작업들을 처리하는데 적합하고 다양한 기능을 수행하는 저장 모듈을 생성할 수 있다. 정절차형 SQL은 DBMS 엔진에서 직접 실행되기 때문에 입출력 패킷이 적은 편이다. BEGIN ~ END 형식으로 작성되는 블록(Block) 구조로 되어 있기 때문에 기능별 모듈화가 가능하다. 　절차형 SQL의 종류는 다음과 같다.

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

절차형 SQL의 테스트와 디버깅

　절차형 SQL은 디버깅을 통해 기능의 접합성 여부를 검증하고, 실행으로 통해 결과를 확인하는 테스트 과정을 수행한다.

절차형 SQL은 테스트 전에 생성을 통해 구문 오류(Syntax Error)나 참조 오류의 존재 여부를 확인한다.
많은 코드로 구성된 절차형 SQL의 특성상 오류 및 경고 메시지가 상세히 출력되지 않으므로 SHOW 명령어를 통해 내용을 확인하고 문제를 수정한다.
정상적으로 생성된 절차형 SQL은 디버깅을 통해 로직을 검증하고, 결과를 통해 최종적으로 확인한다.
절차형 SQL의 디버깅은 실제로 데이터베이스에 변화를 줄 수 있는 삽입 및 변경 관련 SQL문을 주석으로 처리하고, 출력문을 이용하여 화면에 츨력하여 확인한다.

쿼리 성능 최적화

　쿼리 성능 최적화는 데이터 입출력 애플리케이션의 성능을 위해 SQL 코드를 최적화하는 것이다. 쿼리 성능을 최적화하기 전에 성능 측정 도구인 APM을 사용하여 최적화 할 쿼리를 선정해야 한다. 최적화 할 쿼리에 대해 옵티마이저가 수립한 실행 계획을 검토하고 SQL 코드와 인덱스를 재구성한다.

Twitter Facebook LinkedIn

MyeongWoo