자료구조 1

자료구조에서 배웠던, 여러 자료들에 대해서 간략히 설명하겠다.

ADT(Abstract Data Type): 컴퓨터 과학에서 자료들과 자료들에 대한 연산들을 명기한 것.

                                  자료구조의 추상화

1. Array

-      장점: 배열에서 특정 위치의 값을 찾기에 편리하다.

-      단점: 배열의 크기를 넘는 값을 삽입할 경우 문제 / 배열의 중간에 삽입 or 삭제 연산 시 번거로움 발생

2. Linked List

-      선형으로 연결된 노드들을 가지는 자료구조

-      노드간 pointer를 이용해 list를 구현하므로 메모리에 연속적으로 값을 저장할 필요 없다.

-      Array list와 달리, 추가 및 삭제가 쉽지만 데이터 접근 시 최악의 경우 O(n) time 소요

-   3가지로 나뉨

  1)    Single Linked list

-      한방향으로 연결된 리스트로, 각 node는 element와 다음 node의 pointer로 구성

    (노드 사이의 간선이 단방향으로 하나씩만 존재)

-      ADT method: empty(), front(), addFront(), removeFront()

   2)    Double Linked list

-      양방향으로 연결된 리스트로, 각 node는 element, next pointer, prev pointer로 구성

    (노드 사이의 간선이 양방향으로 2개씩 존재)

-      노드의 탐색이 양방향으로 가능하므로 탐색 양이 single에 비해 절반 감소한다.

-      ADT method: empty(), front(), back(), addFront(), removeFront(), addBack(), removeBack()

   3)    Circular Linked list

-      Single linked list의 구조를 원형으로 만든 자료구조

    (첫번째 노드와 마지막 노드가 연결)

-      마지막 노드를 참조하는 cursor가 single에서의 head역할을 한다.

     3. stack

-      LIFO원칙에 따라 자료를 삽입 또는 삭제하는 자료구조

-      ADT method: push(object), pop(), top(), size(), empty()

-      Exceptions: stack이 빈 상태일 때, pop(), top()연산 수행 시 StackEmpty exception 발생

-      C++ Run-Time Stack: c++ run-time system은 stack을 이용하여 active function들의 chin track을 유지한다. 함수 호출 시 시스템은 호출된 함수에 관한 정보(지역변수, 반환 값, pc, 현 실행지점)를 포함하는 하나의 frame을 stack에 push한다. 함수 종료 시 해당 frame이 pop되고 stack의 top함수가 수행됨

-  구현 방법

  1)    Array-based Stack

-      공간 복잡도: O(n)

-      시간 복잡도: push(object), pop(), top(), size(), empty() 모두 O(1)

-      한계: 배열을 사용하기 때문에 stack크기 조정 불가능하다. 

   따라서 full stack에 대해 push()연산 수행 시 StackFull exception발생 ç implementation-specific exception

   2)    Linked list-based Stack

-      Single linked list로 구현

-      배열과 달리 full stack문제가 발생하지 않는다. 크기 제한이 없어서.

-      공간 복잡도: O(n)

-      시간 복잡도: 모든 연산에 대해 O(1)

     4. queue

-      FIFO원칙에 따라 자료를 삽입 또는 삭제하는 자료구조

-      ADT method: size(), empty(), enqueue(object), dequeue(), front()

-      Exceptions: 빈 큐에 대해 dequeue()와 front()연산 수행 시 QueueEmpty exception 발생

-   구현 방법

        1)    Array-based Queue

-      크기가 N인 circular array를 사용한다. (현재 front의 인덱스, 원소의 크기, 배열의 크기를 따로 지정한 변수에 저장)

-      Full queue에 대해 enqueue(e)연산 수행 시 QueueFull exception발생 ç implementation-specific exception

-      공간 복잡도: O(n)

-      시간 복잡도: 모든 연산에 대해 O(1)

   2)    Linked list-based Queue

-      Circular linked list이용하여 구현

-      공간 복잡도: O(n) (n: queue에 저장된 요소의 개수)

-      시간 복잡도: O(1)

     

     5. vector

      -   Linked list의 장점을 뽑아온 자료구조

-      Index를 이용하여 element에 대한 접근, 삽입 그리고 삭제를 지원하는 자료구조

-      ADT method: at(i), set(i, object), insert(i, object), erase(i), size(), empty()

-      Exceptions: 부정확한 index가 주어질 경우 예외처리

-   구현 방법

   1)    Array-based 구현

-      크기가 N인 배열 사용하며 저장된 요소의 개수를 변수 n에 저장

-      공간 복잡도: O(N)

-      시간 복잡도

Size()	Empty()	At(i)	Set(i, e)	Insert(i, e)	Erase(i)
O(1)	O(1)	O(1)	O(1)	O(n)	O(n)

-      배열이 full일 때 insert()연산을 수행할 경우: 예외처리를 하는 대신 더 큰 배열로 배열을 교체한다.

배열 크기 확장 ç 값을 옮기면서 O(n)의 시간이 필요함.

① Incremental strategy : 상수만큼 더 큰 배열 

② Doubling strategy : 기존배열의 두배

6. Tree

-      List와 vector가 선형구조인 반면, tree는 계층적 구조를 가진다.

-      노드간 부모-자식 관계가 존재

-      용어

①     Root: tree에서 부모가 없는 최상위 노드

②     Internal node: 1개 이상의 자식 node가 존재하는 node

③     External node: 자식이 존재하지 않는 node로 leaf를 뜻한다.

④     Ancestors of a node: 한 노드의 부모를 포함한 조상 노드들

⑤     Descendant of a node: 한 노드의 바로 연결된 자식과 그 밑 자식들

⑥     Depth: 한 노드의 조상의 수

⑦     Height: 노드들의 depth중 가장 큰 depth로, tree의 높이다.

⑧     Subtree: tree의 한 노드와 그 후손들로 구성된 하나의 트리 (트리안에 트리)

⑨     Sibling: 같은 부모 노드를 가진 자식 노드들의 관계

-      ADT method: size(), empty(), root(), positions() (모든 노드들의 위치 list), parent(), children(), isRoot(), isExternal()

-      트리의 순회(Traversal) 방법

①     Preorder Traversal: 부모 à 자식(왼->오)순으로 방문한다. 주로 책의 목차를 print할 때 사용

②     Postorder Traversal: 자식 à 부모순으로 방문한다. 주로 하위 디렉토리들이 차지하는 공간의 용량을 계산할 때 사용

 

 -   Binary tree

-      트리중 모든 노드가 최대 두개의 자식 노드를 가진 트리

-      종류

①     Proper(=full=plane) binary tree: 모든 노드가 0 or 2개의 자식을 가진 tree

②     Complete(=perfect) binary tree: 모든 internal 노드가 2개의 자식을 가지며 leaf 노드들의 깊이가 모두 같은 tree)

③     Almost complete(=complete) binary tree: complete tree에서 모든 leaf노드들이 왼쪽부터 오른쪽 방향으로 채워진 tree

   Complete binary tree를 perfect binary tree라 지칭할 경우 almost complete를 complete라고도 부름

-      응용: 수식표현, decision tree, searching(binary search tree)

-      ADT method: Tree ADT의 함수들 + left(), right()

-      Binary Tree의 Traversal : Tree 순회방법에서 하나 더 추가됨

①     Preorder: 부모à왼쪽 자식à오른쪽 자식 순서로 순회

②     Postorder: 왼쪽 자식 à 오른쪽 자식 à 부모 순서로 순회

③     Inorder: 왼쪽 자식 à 부모 à 오른쪽 자식 순서로 순회

④     Euler Tour Traversal

Ø  preorder, inorder, postorder traversal을 모두 실행한다.

Ø  Tree 주위를 순회하며 각 node를 3번 방문(왼쪽 자식 방문 전, 왼쪽 자식 방문 후 오른쪽 자식 방문 전, 오른쪽 자식 방문 후)한다.

Ø  한 노드당 하는 일의 수가 모두 3개로 일정하여 이 순회의 시간 복잡도는 O(n)

-   구현 방법

 1)    Linked list-based: 각 노드는 element, parent node, left child, right child로 구성

 2)    Array-base: 노드가 깊이 순서로 배열에 저장. Root=1, 왼쪽 자식=2*i, 오른쪽 자식=2*i+1

     7. priority queue

 -      우선순위에 의해 데이터가 정렬되기 때문에 queue에 삽입되는 요소의 순서가 중요하지 않으며 데이터 속성에 따라 제거가 가능하다.

 -      ADT에서 Entry는 (key, value) 쌍으로 구성되며 key는 우선순위를 가리킴

 -      ADT method: insert(e), removeMin(), min(), size(), empty()

 -   구현 방식

        List-based Priority queue

   List를 정렬된 상태로 저장 vs 정렬되지 않은 상태로 저장 수행 시간 비교

(sorted list)                 (unsorted list)

Operation	Unsorted List	Sorted List
Size, empty	O(1)	O(1)
Insert	O(1)	O(n)
Min, removeMin	O(n)	O(1)

   

 -    PQ를 이용한 sort 방법들 -> 정렬을 위해 insert, removeMin연산을 이용

Priority queue에 n개의 원소를 삽입(insertion)하는 시간 =  1*n

Priority queue에서 원소 하나씩 꺼내어 기존 배열에 옮기는 작업(removeMin) 시간 = 1+2+…+n

=> n+1+2+3+…+n = O(n^2)

   1) selection-sort : unsorted list를 사용하여  O(n^2)에 동작가능.

  - 실제 selection sort는 주어진 배열에서 0부터 n-1까지의 i에 대하여 [i, n]구간에 대하여 가장 최솟값을 맨 앞에 세우는 과정을 반복.

   2) insertion-sort : sorted list를 사용하여 O(n^2)에 동작가능.

	구현	시간 복잡도
Selection-Sort	Unsorted List를 이용한 PQ	O(n^2)
Insertion-Sort	Sorted List를 이용한 PQ	O(n^2)