정보처리기사 2과목 소프트웨어 개발 1장 데이터 입·출력 구현 요점 정리

Section34 자료 구조

 

1. 자료 구조의 정의

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

 

- 자료 구조는 자료의 표현과 그것과 관련된 연산이다.

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

- 어떠한 자료 구조에서도 필요한 모든 연산들을 처리할 수 있다.

- 자료 구조에 따라 프로그램 실행시간이 달라진다.

 

2. 자료 구조의 분류

선형 구조 : 배열, 선형 리스트(연속, 연결리스트), 스택, 큐, 데크

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

 

3. 배열

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

- 배열은 정적인 자료구조로 기억장소의 추가가 어렵고, 데이터 삭제 시 데이터가 저장되어 있던 기억장소는 빈 공간으로 남아있어 메모리의 낭비가 심하다.

- 배열은 점자를 이요하여 데이터에 접근한다.

- 배열은 반복적인 데이터 처리 작업에 적합한 구조이다.

- 배열은 데이터마다 동일한 이름의 변수를 사용하여 처리가 간편하다.

- 배열은 사용한 첨자의 개수에 따라 n차원 배열이라고 부른다.

 

4. 선형 리스트

- 일정한 순서에 의해 나열된 자료 구조이다.

- 선형 리스트는 배열을 이용하는 연속 리스트와 포인터를 이용하는 연결 리스트로 구분된다.

연속 리스트

- 배열과 같이 연속되는 기억장소에 저장되는 자료 구조이다.

- 기억장소를 연속적으로 배정받기 때문에 기억장소 이용 효율은 밀도가 1로서 가장 좋다.

- 중간에 데이터를 삽입하기 위해서는 연속된 빈 공간이 있어야 하며, 삽입•삭제 시 자료의 이동이 필요하다.

 

연결리스트

- 자료들을 반드시 연속적으로 배열시키지는 않고 임의의 기억공간에 기억시키되, 자료 항목의 순서에 따라 노드의 포인터 부분을 이용하여 서로 연결시킨 자료 구조이다.

- 노드의 삽입•삭제 작업이 용이하다.

- 기억 공간이 연속적으로 놓여 있지 않아도 저장할 수 있다.

- 연결 리스트는 연결을 위한 링크 부분이 필요하기 때문에 순차 리스트에 비해 기억 공간의 이용 효율이 좋지 않다.

- 연결 리스트는 연결을 위한 포인터를 찾는 시간이 필요하기 때문에 접근 속도가 느리다.

- 연결 리스트는 중간 노드 연결이 끊어지면 그 다음 노드를 찾기 힘들다.

 

5. 스택

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

- 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO: Last In First Out)방식으로 자료를 처리한다.

- 모든 기억 공간이 꽉 채워져 있는 상태에서 데이터가 삽입되면 오버플로(Overflow)가 발생하며, 더 이상 삭제할 데이터가 없는 상태에서 데이터를 삭제하면 언더플로(Underflow)가 발생한다.

 

6. 큐

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

- 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(First In First Out)방식으로 처리한다.

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

- 프런트(F, Front) 포인터: 가장 먼저 삽입된 자료의 기억 공간을 가리키는 포인터로, 삭제 작업을 할 때 사용한다.

- 리어(R, Rear) 포인터: 가장 마지막에 삽입된 자료의 기억 공간을 가리키는 포인터로, 삽입 작업을 할 때 사용한다.

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

 

7. 트리

- 정점(Node, 노드)와 선분(Branch, 가지)을 이용하여 사이클을 이루지 않도록 구성한 그래프의 특수한 형태이다.

- 트리는 하나의 기억 공간을 노드라고 하ㅕ, 노드와 노드를 연결하는 선을 링크라고 한다.

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

트리 관련 용어

- 노드 : 트리의 기본 요소로서 자료 항목과 다른 항목에 대한 가지를 합친 것

- 근 노드(Root Node) : 트리의 맨 위에 있는 노드

- 디그리(Degree, 차수): 각 노드에서 뻗어 나온 가지의 수

- 단말 노드(Terminal Node) :자식이 하나도 ㅇ벗는 녿, 즉 디그리가 0인 노드

- 자식 노드(Son Node): 어떤 노드에 연결된 다음 레벨의 노드들

- 부모 노드(Parent Node): 어떤 노드에 연결된 이전 레벨의 노드들

- 형제 노드(Brother Node, Sibling): 동일한 부모를 갖는 노드들

- 트리의 디그리: 노드들의 디그리 중에서 가장 많은 수

 

Section 35 데이터저장소/ 데이터베이스 / DBMS

1. 데이터저장소

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

- 데이터저장소는 논리 데이터저장소와 물리 데이터저장소로 구분된다.

- 논리 데이터저장소는 데이터 및 데이터 간의 연관성, 제약조건을 식별하여 논리적인 구조로 조직화한 것을 의미한다.

- 물리 데이터저장소는 논리 데이터저장소에 저장된 데이터와 구조들을 소프트웨어가 운용될 환경의 물리적 특성을 고려하여 하드웨어적인 저장장치에 저장한 것을 의미한다.

- 논리 데이터저장소를 거쳐 물리 데이터저장소를 구축하는 과정은 데이터베이스를 구축하는 과정과 동일하다.

 

2. 데이터베이스

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

통합된 데이터(Integrated Data): 자료의 중복을 배제한 데이터의 모임이다.

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

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

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

 

3. DBMS(Database Management System; 데이터베이스 관리 시스템)

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

- DBMS는 기존의 파일 시스템이 갖는 데이터의 종속성과 중복성의 문제를 해결하기 위해 제안된 시스템으로, 모든 응용 프로그램들이 데이터베이스를 공용할 수 있도록 관리해 준다.

- DBMS는 데이터베이스의 구성, 접근 방법, 유지관리에 대한 모든 책임을 진다.

- DBMS의 필수 기능에는 정의(Definition), 조작(Manipulation), 제어(Control) 기능이 있다.

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

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

제어 기능: 데이터베이스를 접근하는 갱신, 삽입, 삭제 작업이 정확하게 수행되어 데이터의 무결성이 유지되도록 제어해야 한다.

- 정당한 사용자가 허가된 데이터만 접근할 수 있도록 보안을 유지하고 권한을 검사할 수 있어야 한다.

- 여러 사용자가 데이터베이스를 동시에 접근하여 데이터를 처리할 때 처리결과가 항상 정확성을 유지하도록 병행 제어를 할 수 있어야 한다.

 

4. DBMS의 장•단점

장점

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

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

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

- 데이터의 일관성을 유지할 수 있다.

- 데이터의 무결성을 유지할 수 있다.

- 보안을 유지할 수 있다.

- 데이터를 표준화 할 수 있다.

- 데이터를 통합하여 관리할 수 있다.

- 항상 최신 데이터를 유지한다.

- 데이터의 실시간 처리가 가능하다.

 

단점

- 데이터베이스 전문가가 부족하다.

- 전산화 비용이 증가한다.

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

- 파일의 예비와 회복이 어렵다.

- 시스템이 복잡하다.

 

※ 데이터의 독립성

- 종속성에 대비되는 말로 DBMS의 궁극적 목표이기도 하다. 데이터 독립성에는 논리적 독립성과 물리적 독립성이 있다.

논리적 독립성 : 응용 프로그램과 데이터베이스를 독립시킴으로써, 데이터의 논리적 구조를 변경시키더라도 응용 프로그램은 변경되지 않는다.

 

물리적 독립성 : 응용 프로그램과 보조기억장치 같은 물리적 장치를 독립시킴으로써, 데이터베이스 시스템의 성능 향상을 위해 새로운 디스크를 도입하더라도 응용 프로그램에는 영향을 주지 않고 데이터의 물리적 구조만을 변경한다.