진리 블로그

검색이란?
  : 컴퓨터를 이용하여 기억공간에 보관중이 특정 레코드를 찾아내는 작업

검색의 종류
  1. 선형 검색(Linear Search)
     - 순차적으로 검색하는 방식으로 순차검색(Sequenrial Search)이라고도 한다.
     - 프로그램 작성이 가장 쉽다
  2. 제어 검색(Control Search)
     - 반드시 순서화된 파일이어야 검색할 수 있다.
     - 제어검색의 종류
        · 이분검색(이진검색, Binary Search)
           : 반드시 자료가 정렬되어 있어야 한다.
             전체 파일을 두 개의 서브 파일로 분리해 가면서 키 레코드를 검색하는 방식
             중앙 레코드 번호 M = ( F + L ) / 2  [단, F = 첫번째 레코드 번호, L = 마지막 레코드 번호]
        · 피보나치 검색(Fibonacci Search)
        · 보간 검색(Interpolation Search)
           : 찾고자 하는 레코드키가 있음직한 위치를 추정하여 검색하는 방법
        · 블록 검색(Block Search)
        · 이진 트리 검색(Binary Tree Search)

정렬(Sort)이란?
  : 파일을 구성하는 각 레코드를 특정 키 항목을 기준으로 오름차순/내림차순으로 재배열하는 작업을 말한다


정렬기법

  1. 내부정렬기법
     - 정의 : 데이터량이 적을 때 주기억장치 내에서 정렬하는 방법
     - 특징 : 속도는 빠르나 정렬할 자료의 양이 많을 경우 부적합하다.
     - 내부정렬의 종류
        · 삽입 정렬(Insertion Sort)
           : 이미 순서화된 파일에 새로운 레코드를 추가하여 순서에 맞게 배치 (2번째 값부터 시작한다)
        · 쉘 정렬(Shell Sort) 
        · 선택 정렬(Select Sort)
           : 레코드의 최소값을 찾아 첫번째 위치에 놓고 다음 최소값을 찾아 두번째 위치에 놓는 방법을 반복하여 정렬
        · 버블 정렬(Bubble Sort)
           : 인접한 값과 비교하여 정렬하는 방식. 끝에 값부터 정해진다.
        · 퀵 정렬(Quick Sort)
        · 힙 정렬(Heap Sort)
        · 2-Way 합병 정렬(Merge Sort)
           : 값들을 2개씩 묶어가면서 비교하여 정렬
        · 기수 정렬(Radix Sort) = Bucket Sort

  2. 외부정렬기법
     - 정의 : 대용량의 데이터를 몇 개의 서브 파일로 나누어 각각 내부 정렬을 한 후에
                 테이프나 디스크 내에서 각 서브파일을 합병하는 방법
     - 특징 : 속도는 느리지만 자료의 양이 많은 경우 효과적이다.
     - 외부정렬의 종류
        · 진동 병합 정렬(Oscillating Merge Sort)
        · 캐스케이드 병합 정렬(Cascade Merge Sort)
        · 폴리파즈 병합 정렬(Polyphase Merge Sort)
        · 균형 병합 정렬(Balance Merge Sort)


정렬 알고리즘의 선택시 고려사항
   1. 키값들의 분포 상태
   2. 소요공간 및 작업시간
   3. 정렬에 필요한 기억공간의 크기
   4. 데이터의 양
   5. 초기 데이터의 배열상태
   6. 사용 컴퓨터 시스템의 특성

그래프(Graph) 특징
  : 쉽게말해 트리구조에서 순환이 허용된 구조이다.
    링크로 연결하여 구조화시킨 자료 구조이다.

  - 정점 : 노드들의 집합
  - 간선 : 정점들사이의 상호 연결의 집합

예제.

          ⓐ ─ ⓑ               
          │ ＼ │                         ⓐ=ⓑ-ⓒ⊃
          ⓒ ─ ⓓ

 각각의 그래프를 메트릭스행열로 표현 하면 다음과 같다.

       a  b  c  d                            a  b  c
    a  0  1  1  1                         a  0  1  0
    b  1  0  0  1                         b  1  0  1
    c  1  0  0  1                         c  0  1  1
    d  1  1  1  0

트리(Tree)
  - Linked List로 표현할 때 가장 효과적이다
  - 계층형 구조(부모 자식구조, 족보구조)
 
트리 구조의 용어
  - 근노드(root node) : 최상위 노드
  - 노드(node) : 트리의 기본요소로 하나의 값
  - 단노드(Terminal node, leaf nod) : 자식이 없는 노드
  - 레벨(Level) : 근 노드의 Level을 1로 가정한 후 어떤 Level이 L이면 자식노드는 L+1
  - 깊이(Depth, Height) : Tree에서 노드가 가질 수 있는 최대의 레벨
  - 디그리(Degree, 차수) : 각 노드에서 뻗어나온 가지의 수
  - 트리의 디그리 : 노드들의 디그리 중에서 가장 많은 수

트리의 운행법
 
     찾아가는방식       표현방식                       운행법
        Preorder            prefix            Root(연산자) → Left → Right
         Inorder              Infix             Left → Root(연산자) → Right
       Postorder           Postfix           Left → Right → Root(연산자)



이진트리(Binary Tree)
  : Degree가 2이하인 노드들로 구성된. 다시말해 자식이 둘 이하인 노드들로만 구성된 트리를 말한다.

이진트리의 주요 특성
  - 깊이가 n인 이진트리의 최대 노드수 = 2ⁿ-1

이진트리의 종류
  - 정이진 트리(Full Binary Tree)
      : 깊이가 n일 때 전체 노드 수가 2ⁿ-1개의 노드이다.
  - 전이진 트리(Complete Binary Tree)
      : 노드의 수가 n개일때, 정이진 트리의 각 노드에 붙인 1~n의 일련번호와 1:1대응되는 트리
        중간에 빈 부분이 있으면 전이진 트리가 될 수 없다
  - 사향이진 트리(Skewed Binary Tree)
      : 왼쪽 또는 오른쪽으로만 기울어진 트리, 즉 왼쪽 또는 오른쪽 자식이 없는 노드들로만 구성된 트리
        사향이진 트리는 공간 낭비가 심하다.


B-트리
  : 한노드 안에 있는 키 값은 오름차순을 유지시켜 많은 데이터를 빠르게 검색할 수 있게 한 트리

신장트리
  : 그래프에서 간선들이 사이클이 되지 않도록 만든 트리

스택(Stack)
  - 한쪽 끝으로만 자료의 삽입, 삭제가 가능한 자료 구조이다.
  - LIFO(Last In First Out)방식이다.
    * 입력명령어 : Push   출력명령어 : Pop

스택의 용도
  - 인터럽트 처리
  - 서브루틴의 복귀번지 저장
  - 수신의 계산(산술식 표현)



큐(Queue)
  - 한쪽으로 입력하면 다른 한쪽으로 출력되는 자료 구조이다.
  - FIFO(First In First Out)방식이다.
   * F : 프런트 포인터    R : 리어 포인터
  - 운영 체제의 작업 스케줄링 등에 응용되는 것으로 가장 적합한 구조



데크(Deque; Double Ended Queue)
  - 입출력이 양쪽 방향으로 가능한 구조이다.
  - 입력제한데크(Scroll) : 한쪽의 입력을 제한
  - 출력제한데크(Shelf) : 한쪽의 출력을 제한

선형 구조의 List는 선형리스트(Linear List)와 연결 리스트(Linked List)로 나뉜다.


선형 리스트란?
  : 배열과 같이 연속되는 기억장소에 저장되는 리스트를 말한다.

선형 리스트의 장점
  - 저장 효율이 뛰어나다
  - 접근속도가 빠르다
  - 간단한 자료구조이다

선형 리스트의 단점
  - 삽입, 삭제가 어렵다(끝에값은 쉽지만 중간값을 삽입, 삭제시 그 이후 값을 전부 복사 후 처리해야 한다)



연결 리스트란?
  : 자료들이 반드시 연속적으로 배열되어있지 않아도 노드 포인터 부분을 이용하여 서로 연결되어진 구조
   * 선형 리스트와는 달리 노드 부분에 다음노드를 가리키는 노드 포인트가 포함되어 있다.

연결 리스트의 장점
  - 삽입, 삭제가 용이하다

연결 리스트의 단점
  - 접근속도(Access Time)이 느리다.
  - 기억장소 이용 효율이 안좋다(노드 포인트 정보를 추가해야 하기 때문에)

자료 구조의 정의
  : 효율적으로 자료를 저장하기 위해 효율성과 신속성을 고려하여 자료간의 관계, 처리방법 등을 분석하는 것


자료 구조의 분류
                                             
  - 선형 구조  -  리스트(List)  -  선형 리스트(Linear List)
                                             비선형 리스트(Linked List)
                    -  스택(Stack)
                    -  큐(Queue)
                    -  데크(Deque)

  - 비선형 구조  -  트리(Tree)
                          그래프(Graph)



자료 구조의 이용
  - 정렬(Sort) : 기억장치 내의 자료를 일정한 순서에 의해 나열하는 것
  - 검색(Search) : 기억장치 내의 자료를 찾는 것
  - 파일 편성 : 자료를 기억 매체에 저장할 때의 파일 구조
  - 인덱스 : 파일에서 특정 자료를 빠르게 찾기 위한 색인표

분산환경에서 구성원들을 연결하고 구성원들 간의 차이를 극복하도록 범용으로 개발된 소프트웨어
쉽게말해 서로다른 데이터베이스 시스템이 데이터를 공유하기 위해서 변환작업이 필요한대
중간에서 그 역할을 하는 소프트웨어이다.

데이터베이스 미들웨어에는 ODBC가 있다.

로킹(Locking)이란?
  : 하나의 트랜잭션이 데이터를 사용(액세스)하는 동안 다른 트랜잭션이 그 데이터를
    사용(액세스)할 수 없도록 하는 방법
    쉽게말해 한 곳에서 트랜잭션 수행이 시작되면 잠궈(Lock)놓고 사용이 끝나면 다른
    트랜잭션을 수행할 수 있다고 풀어(Unlock)준다는 뜻이다.