2-1강. 데이터 입출력 구현-논리 데이터저장소 확인(1)

[ 목차 ]

1. 소프트웨어 개발 절차

2. 자료 구조 정의

3. 논리적 구조와 물리적 구조

4. 자료 구조 분류

5. 검색

6. 선형구조 - 선형 리스트 liner list

7 선형구조 - 연결 리스트 linked list

8. 선형구조 - 스택 리스트 stack list

9. 선형구조 - 큐 queue

10. 선형구조 - 데크 deque, double ended queue

11. 비선형구조 - 트리

12. 이진트리

13. 이진트리 특징

14. 그래프

15. 그래프 특징

16. 완전그래프

17. 그래프 용어

 

1. 소프트웨어 개발 절차

1) 요구 사항 확인 -> 설계 -> 구현(개발) -> 테스트(시험) -> 유지보수

2) 요구 사항 확인 : 무엇을 만들지 확인

3) 설계 : 요구 사항 분석 결과를 가지고구체적인 기능과 구조를 체계화

4) 개발(구현) : 프로그램 언어를 선정, 설계 명세서를 컴퓨터가 이해할 수 있게 표현

5) 테스트 : 요구 사항에 맞게 작동하는지 확인

6) 유지보수 : 버전 업데이트, 새로운 기능 추가

 

2. 자료 구조 정의

1) 자료를 저장하는 논리적인 방법

2) 컴퓨터 상에 자료를 저장하기 위해서 만들어진 논리적인 틀

3) 논리 데이터저장소 : 논리적인 자료구조로 만들어진 데이터 저장소(논리적 설계에서 만들어진 데이터를 저장)

레코드
1) 파일을 액세스할 때 실제로 읽고 쓰는 단위로서 사용되는 데이터 단위
2) 현실 세계에서의 개체
3) 레코드가 모여 파일을 이룸

필드
1) = 속성

파일
1) = 테이블
2) 같은 타입의 레코드들이 집합일 이뤄 구성

3. 논리적 구조와 물리적 구조

1) 사용자의 생각

2) 관계형 db에서 테이블은 사람이 이해하기 위한 논리적 구조이지만 실제 저장은 하드 디스크 기준으로 섹터라는 물리적 공간에 저장

 

4. 자료 구조 분류

1) 파일의 레코드를 물리적 저장 장치에 저장시키기 위한 배치 방법으로서 데이터베이스의 물리적 저장 방법이 사용

2) 선형구조 : 순서대로 저장

3) 비선형구조 : 트리, 그래프처럼 특정 모양을 가지며 연결

4) 기본적으로 저장된 레코드들이 어떻게 접근(접근, 검색방법)할 수 있게 하느냐에 따라 순차방법, 인덱스방법, 해싱방법으로 구분

 

5. 검색

1) 원하는 데이터를 찾는 것

2) 선형검색(순차검색, full scan) : 모든 레코드를 대상으로 순차적 검색하며 자료 정렬이 없을 때 처리 속도 느림

3) 이분검색(이진검색, binary) : 자료가 정렬된 조건에서 중간 값을 비교 검색하는 것으로 많은 레코드 검색 시 효율적

4) 인덱스검색

  1] 테이블 검색 속도를 향상시킬 수 있는 확실한 수단

  2] 저장공간을 차지하며 항상 정렬 상태를 유지하기 위해 튜플이 추가, 삭제되면 재정렬 되어야 하기 때문에 인덱스 수가 많다고 좋은 것이 아님

5) 해싱검색

  1] 해싱함수를 이용해 자료를 검색하는 방법

  2] 해시 테이블이라는 배열에 저장하고 해싱 함수를 이용해 데이터의 위치를 찾기 때문에 신속하게 자료를 검색할 수 있는 키-주소 변환 방법

  3] 특징

      - DAM(직접 접근)파일을 구성할 때 사용

      - 삽입, 삭제 작업의 빈도가 많을 때 유리

      - 검색은 가장 빠르지만 기억공간 낭비 발생

  4] 해싱함수 : 해시 테이블의 주소를 생성해내는 함수

  5] 해시 테이블 : 해싱함수에 의해 참조되는 테이블

  6] 버킷 : 하나의 주소를 갖는 파일(해시 테이블)의 한 구역

  7] 슬롯 : N개의 슬롯이 모여 하나의 버킷을 형성

버킷 : 열, 슬롯 : 칸

  8] 충돌 collision : 서로 다른 2개 이상의 레코드가 같은 주소를 갖는 현상

  9] 시노임 : 같은 주소를 갖는 레코드의 집합(위 테이블의 0)

  10] 오버플로 : 버킷 내에 기억 공간이 없는 현상 

 

6. 선형구조 - 선형 리스트 liner list

1) 배열과 같이 연속되는 기억장소에 저장되는 리스트(연속적)

2) 대표적 구조 : 배열

3) 가장 간단한 자료구조이며 접근 속도가 빠름

4) 중간에 자료를 삽입하기 위해 연속된 빈 공간이 존재해야 함

5) 자료의 삽입, 삭제 시 자료의 이동이 필요해 번거로움

 

7. 선형구조 - 연결 리스트 linked list

1) 자료를 임의의 기억 공간에 기억 시키되 각 노드의 포인터를 이용해 서로 연결한 자료구조(비연속적)

2) 노드의 삾입, 삭제 작업이 용이

3) 기억공간이 연속적으로 놓어있지 않아 저장이 가능

4) 연결을 위한 포인터가 추가로 필요해서 기억공간이 더 필요

5) 연결을 위한 포인터를 찾는 시간이 필요해 순차리스트에 비해 느림

6) 희소 행렬을 링크드 리스트로 표현하면 기억장소가 절약

7) 희소행렬 : 많은 항들이 0으로 구성된 행렬로, 희소행렬의 조건은 정확히 정의되기보다 직감적인 개념

 

8. 선형구조 - 스택 리스트 stack list

1) 한 쪽 끝에서만 자료를 넣고 뺄 수 있는 LIFO(last in first out)형식의 구조

2) top point : 가장 최근에 삽입된 자료 또는 가장 먼저 삭제될 자료를 가리키는 스택 포인터로 삽입시 top값 증가, 삭제시 감소

3) 서브 프로그램 호출 시 복귀 주소 저장에 활용

4) 인터럽트 수행 시 복귀 주소 저장에 활용

5) 수식 연산에 활용(수식은 연산자의 위치에 따라 전위, 중위, 후위로 표기하며 이중 연산자가 마지막에 있는 후위 표기법과 연관이 있음)

인터럽트
1) 어떤 특수한 상태(예기치 않은 일, 응급사태)가 발생하면 그것이 원인이 되어 현재 실행하고 있는 프로그램이 중단되고 그 특수한 상태를 처리하는 프로그램으로 옮겨져 처리한 후 다시 원래의 프로그램을 처리하는 현상

9. 선형구조 - 큐 queue

1) 스택과 달리 리스트의 한 끝에서는 삽입 작업이, 반대에서는 삭제 작업이 이루어져 삽입된 순서대로 삭제되는 구조

2) 삽입선출(FIFO) 구조

3) front pointer는 삭제 작업, rear pointer는 삽입 작업을 할 때 사용

 

10. 선형구조 - 데크 deque, double ended queue

1) 큐를 응용한 것으로 양쪽 끝에서 삽입과 삭제가 모두 가능한 자료 구조

2) 두개의 포인터를 사용해 양쪽에서 삭제와 삽입 발생 가능

3) 큐 + 스택

 

11. 비선형구조 - 트리

1) 트리

  1] 데이터들을 계층화 시킨 자료 구조(ex. 탐색지)

  2] 인덱스를 조직하는 방법으로 가장 많이 사용

  3] 노드들과 노드들을 연결하는 링크(간선)들로 구성

  4] 사이클이 없으며 부모자식 관계

2) 용어

  1] 루트노드 : 부모가 없는 최상위 노드로 트리에서 딱 하나

  2] 단말노드 : 자식이 없는 최하위 노드

  3] 내부노드 : 루트, 단말 이외의 노드

  4] 링크 : 노드를 연결하는 선으로 edge, branch, 간선으로도 지칭

  5] 형제 sibling : 같은 부모를 가지는 노드

  6] 노드크기 : 자신을 포함한 모든 자손 노드의 개수

  7] 깊이, 높이 : 트리에서 노드가 가질 수 있는 최대 레벨

  8] 노드의 레벨 : 트리의 특정 깊이를 가지는 노드의 집합

  9] 노드의 차수 : 노드가 가진 하위 트리 개수 혹은 간선의 수

  10] 트리의 차수 : 트리의 최대 차수 = 노드의 차수 값 중 최대값

3) 기본 성질

  1] 노드가 n개인 트리는 항승 n-1개의 링크를 가짐

  2] 루트에서 어떤노드로 가는 경로는 유일하며, 임의의 두 노드 간의 경로도 유일함

  3] 2번 성질을 위배하는 것은 사이클, 순환을 가지는 그래프를 의미

4) 이진트리의 순행방법 : 차수가 2 이하로 구성된 트리

  1] preorder 전위 : root -> left -> right

  2] inorder 중위 : left -> root -> right

  3] postorder 후위 : left -> right -> root

5) 트리 순회방법을 이용한 수식표현변

  1] 전위 표현법(prefix) 

     - 연산자, 변수, 변수의 순서로 수식을 표현

  2] 중위 표기법 infix

     - 변수, 연산자, 변수

  4] 후위 표기법 postfix

     - 변수, 변수, 연산자

 

12. 이진트리

1) 각 노드는 최대 2개의 자식노드를 지님

2) 각가의 자식 노드는 자신이 부모의 왼쪽 자식인지 오른쪽 자식인지 지정됨

3) 포화 이진트리 (full, 정이진트리) : 모든 레벨에서 노드들이 모두 채워져 있는 트리

4) 완전 이진트리(complete,. 전이진트리) : 마지막 레벨을 제외하고 노드가 모두 채워져 있는 트리

5) 편향 이진트리(skewed) : 노드가 왼쪽이나 오른쪽의 한족으로만 있는 이진트리

 

13. 이진트리 특징

1) 높이가 h인 포화 이진트리는 2의 h승-1개의 노드를 지님

2) 노드가 n개인 포화, 완전 이진 트리의 높이는 O(logN)

3) 노드가 n개인 이진트리의 높이는 최악의 경우O(N) = 평향 이진트리(사향 이진트리)

 

14. 그래프

1) 단순히 노드와 그 노드를 연견하는 간선을 하나로 모아 놓은 자료 구조

2) 연결되어 있는 객체 간의 관계를 표현할 수 있는 자료 구저

3) 노드와 간선으로 구성되어 있으며사이클이 존재

4) 인접행렬 : 그래프의 구조를 표현하기 위해 정점 수만큼의 열과 행을 가진 행렬을 이용하는 방법

5) G = (V,E) 로, V는 정점, E는 간선을 의미

6) 방향이 있는 그래프의 간선은 <X, Y>로 표시

 

15. 그래프 특징

1) 네트워크 모델

2) 루트 노드, 부모-자식 관계라는 개념이 없음

3) 2개 이상의 경로가 가능

4) 자기 자신을 향하는 간선은 없음

5) 중복 간선 허용X

 

16. 완전그래프

1) 그래프에서 간선의 수가 최대인 그래프

2) 무방향 그래프 경우 N개의 정점이 있는 경우 간선의 수는 N(N-1)/2개

3) 무방향 그래프 경우 N개의 정점이 있는 경우 간선의 수는 N(N-1)개

 

17. 그래프 용어

1) 인접 adjacent 무방향 그래프에서 정점 a,b에 대해 간선(a,b)가 있으면 정점 a는 정점b에 인접

2) 부속 incident : 무방향 그래프에서 정점 a,b에 대해 간섬(a,b)가 있으면 간섬(a,b)는 정점 a, b의 부속

3) 부분그래프 subgraph 그래프의 일부분인 그래프를 의미

4) 경로 : 정점 a에서 b로 가는 경로

5) 경로의 길이 : 경로상에 있는 간선의 수

6) 단순 경로 : 처음과 마지막을 제외하고 정점이 모두 다른 경로, 즉 경로상의 정점이 중복되지 않는 것

7) 사이클 : 처음과 마지막 정점이 단순경로로 다시 원점에 도달하는 경우로 방향성 그래프에서는 방향성 사이클이라 지칭

8) 연결됨 connected : 점점 a와 b가 연결되어 있는 것은 a에서 b로 가는 경로가 있다는 것을 의미