🔽

자료구조

• 자료 구조의 분류

  

• 자료 구조의 활용

  • 정렬(Sort)
    • 집합된 데이터 레코드를 일정 기준으로 재배령ㄹ하는 것을 말한다.
    • 오름차순, 내림차순
  • 검색(Search)
    • 저장된 데이터 레코드 중 원하는 값을 빠르게 찾는 것을 말한다.
  • 인덱스(Index)
    • 데이터베이스 성능에 많은 영향을 주는 DBMS의 구성 요소로 테이블과 클러스터에 연관되어 독립적인 자료 공간을 보유하며, 데이터 베이스에 저장된 자료를 더욱 빠르게 조회하기 위하여 별도로 구성한 순서 데이터를 말한다.
    • B-트리 인덱스는 분기를 목적으로하는 Branch Block을 가지고 있다.
    • BETWEEN 등 범위 검색에 사용될 수 있다.
  • 파일 편성
    • 파일에서 레코드의 물리적인 배열 방법이다.

• 선형 자료구조 : 일렬로 나열된 자료를 의미

  • 리스트

    • 선형 리스트(Linear List)
      • 배열과 같이 연속되는 기억 장소에 저장되는 리스트이다.
      • 가장 간단한 데이터 구주 중하나로 데이터 항목을 추가/삭제하는 것이 불편하다.
    • 연결 리스트(Linked List)
      • 노드의 포인터 부분을 서로 연결시킨 리스트로 연속적인 기억 공간이 없어도 저장이 가능하다.
      • 노드의 삽입/삭제가 용이하며 포인터를 위한 추가 공간이 필요하므로 기억 공간이 많이 소요된다.

  • 스택

    • 리스트의 한쪽 끝에서만 자료의 삽입과 삭제가 이루어지는 자료 구조이다.

    • 가장 나중에 삽입된 자료가 가장 먼저 삭제되는 후입선출(LIFO) 방식이다.

    • 마지막 삽입된 자료의 위치를 Top, 가장 먼저 삽입된 자료 위치를 Bottom

    • 스택 가드 : 메모리상에서 프로그램의 복귀 주소와 변수 사이에 특정 값을 저장해 두었다가 그 값이 변경되었을 경우 오버플로우 상태로 가정하여 실행을 중단

    • 스택의 응용 분야

      • 인터럽트 처리 , 수식의 계산, 0-주소 지정 방식
      • 재귀 호출, 후위 표현 연산, 깊이 우선 탐색

    • 스택의 삽입 알고리즘 (Push)

      if TOP ≥ n then call Stack-Full else TOP ← TOP + 1 Stack(TOP) ← Data end Insert

    • 스택의 삭제 알고리즘 (Pop)

      if TOP = 0 then call Underflow else remove Stack(TOP) TOP <- TOP -1

    • 스택의 오버플로 알고리즘

      TOP = TOP +1 If TOP > n Then goto AA else Stack(TOP) <- item

  • 큐(Queue)

    • 자료의 삽입 작업은 선형 리스트의 한쪽 끝에서, 삭제 작업은 다른 족 끝에서 수행되는 자료 구조이다.
    • 가장 먼저 삽입된 자료가 가장 먼저 삭제되는 선입선출(FIFO) 방식이다.
    • 큐의 응용 분야
      • 운영체제의 작업 스케줄링

  • 데크 (Deque)

    • 자료의 삽입과 삭제가 리스트 양끝에서 이루어지므로 두 개의 포인터를 사용하는 자료 구조이다.
    • 스택과 큐를 복합한 형태
    • 입력 제한 데크 : Scroll , 출력 제한 데크 : Shelf

• 비선형 구조
  • 트리(Tree)
    • 그래프의 특수한 형태로 Node + Branch 의 형태
    • 사이클을 이루지 않아야 한다.
  • 트리 용어
    • 노드 : 트리의 기본 구성 요소
    • 근 노드(Root Node) , 부모 노드, 자식 노드
    • 형제 노드 : 같은 부모를 가진 노드
    • 조상 노드 : 어떤 노드에서 근 노드에 이르는 경로상의 모든 노드
    • 단말 노드 (Terminal Node) : 트리의 제일 마지막에 위치한 노드
    • 차수(Degree) : 연결된 자식 노드의 수
    • 깊이(Depth) : 트리의 최대 레벨
  • 이진 트리 (Binary Tree)
    • 차수가 2 이하인 노드들로만 구성된 트리이다
    • 이진 트리의 레벨 K에서 최대 노드의 수 : 2^K -1
  • 이진 트리의 구조
    • 정이진 트리 (Full Binary Tree) : 모든 레벨가지 모두 2개씩 노드가 채워진 트리
    • 완전 이진 트리 (Complete Binary Tree) : 정이진 트리에서 마지막 레벨에서 왼쪽부터 단말 노드를 채우는 트리
    • 사향 이진 트리 (Skewed Binary Tree) : 근노드로부터 한쪽 방향으로만 기울어진 트리
  • 이진 트리의 운행법 (Traversal)
    • 전위 운행 (Preorder) : Root → Left → Right
    • 중위 운행 (Inorder) : Left → Root → Right
    • 후위 운행 (Postorder) : Left → Right → Root
• 수식 표기법
  • 전위 (Prefix) 표기법 : 연산자 → 피연산자 → 피연산자 // +AB
  • 중위 (Infix) 표기법 : 피연산자 → 연산자 → 피연산자 // A+B
  • 후위 (Postfix) 표기법 : 피연산자 → 피연산자 → 연산자 // AB+
  • 연산자 우선순위대로 ( ) 로 묶은 뒤에
• 그래프
  • 정점(Vertex)와 간선(Edge)의 집합으로 이루어지는 자료구조이다.
  • 표현 방법 : 인접 행렬(Adjacency Matrix)
  • 신장 트리(Spanning Tree) : 간선들이 사이클을 이루지 않도록 정점들을 연결시킨 그래프이다.
  • 종류 : 방향, 무방향, 완전, 부 그래프
    • n개의 노드로 구성된 무방향 그래프의 최대 간선 개수는 n(n-1)/2 개이다.
  • 제어흐름 그래프에서 순환 복잡도
    • V(G) = E(화살표 수) - N(노드 수) +2
• 인접 행렬(Adjacency Matrix)
  • 방향 그래프에서 ViVj 관계를 나타내는 행렬의 원소 : Aij - 간선이 존재하면 1 없으면 0
  • 무방향 그래프에서 Vi 와 Vj가 서로 인접하면 Aij = 1 , 서로 인접하지 않으면 Aij = 0

정렬

• 정렬 알고리즘 선택 시 고려사항 : 데이터의 양, 초기 데이터의 배열 상태, 키 값들의 분포 상태, 컴퓨터 시스템 특성
• 종류 : 내부 정렬(주 기억장치), 외부 정렬(보조 기억 장치)
• 내부 정렬

  • 삽입 정렬(Insertion Sort)

    • 정렬된 파일에 새로운 하나의 레코드를 순서에 따라 삽입시켜 정렬하는 방법이다.

    • 최상 : $O(n)$ , 최악 : $O(n^2)$ , 평균 : $O(n^2)$

      

  • 버블 정렬(Bubble Sort)

    • 인접한 데이터를 비교하면서 그 크기에 따라 데이터의 위치를 바꾸어 정렬하는 방법

    • 한번 PASS 마다 젤 큰 값이 뒤로감

    • 최상 : $O(n^2)$ , 최악 : $O(n^2)$ , 평균 : $O(n^2)$

      

  • 선택 정렬 (Selection Sort)

    • n 개의 레코드 중에서 최소값을 찾아 1st 레코드에 놓고 나머지 n-1 개의 레코드 중에서 최소값을 찾아 2nd 자리에 둔다.

    • 최상 : $O(n^2)$ , 최악 : $O(n^2)$ , 평균 : $O(n^2)$

      

  • 병합(합병) 정렬 (2-Way Merge sort)

    • 두 개의 키들을 한 쌍으로 하여 각 쌍 순서에 대해 순서를 정한다.
    • 순서대로 정렬된 각 쌍의 키들을 합병하여 하나의 정렬된 서브 리스트로 만든다.
    • 최상 : $O(nlogn)$ , 최악 : $O(nlogn)$ , 평균 : $O(nlogn)$

  • 퀵 정렬 (Quick Sort)

    • 레코드의 많은 자료 이동을 없애고 하나의 파일을 부분적으로 나누어가면서 정렬하는 방법

    • 키를 기준으로 작은 값은 왼쪽, 큰 값은 오른쪽에 모이도록 서로 교환 시키는 부분 교환 정렬법

    • 최상 : $O(nlogn)$ , 피벗을 사용하며 최악의 경우 : $\frac{n(n-1)}2$ , 평균 : $O(nlogn)$

      

  • 힙 정렬 (Heap Sort)

    • 완전이진 트리를 이용하여 정렬하는 방법이다.
    • 정렬한 입력 레코드들로 힙을 구성하고 가장 큰 키값을 갖는 루트 노드를 제거하는 과정을 반복하여 정렬하는 기법이다.
    • 입력 자료의 레코드를 완전 이진 트리로 구성한다.
    • 최상 : $O(nlogn)$ , 최악 : $O(nlogn)$ , 평균 : $O(nlogn)$

검색과 해싱

• 검색의 정의 : 기억 공간 내 기억된 자료중에서 주어진 조건을 만족하는 자료를 찾는 것이다.
• 검색 방식의 종류
• 해싱의 정의
• 해싱 함수의 종류 ( 키값 → 홈주소 : 일방향 함수)
• 오버플로 해결 방법