Data Structure

Data Structure

전산학 전반에서 사용되는 기본적인 DS 를 소개한다.

Preliminaries

---

Big O notation

Let f, g be real valued function.

Then, f(x) = O(g(x)) if there is exist x` such that

f(x)

≤ M

g(x)

for any x > x’

Example.

$3n + 4 = O(n)$

$4n^2 + 3n + 1 = O(n^2)$

• 이걸 왜 쓰나?
  • 알고리즘의 효율성을 계산하기 위해서!
• 좋은 알고리즘이란?
  • 필요한 용량이 적음 (low space complexity)
  • 빠름 (low time complexity)

Sorting Algorithm

selection sort

time complexity : $O(n^2)$

def selectionSort(arr):
  
    for i in range(len(arr)):
        min = i
        for j in range(i, len(arr)):
                if arr[min] > arr[j]:
                        min = j
                
        arr[min], arr[i] = arr[i], arr[min]
    
    return arr

Bubble sort

time complexity : $O(n^2)$

def bubbleSort(arr):
    
    for i in range(len(arr)):
        for j in range(len(arr)-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

    return arr

Merge sort

time complexity : $O(nlog(n))$

def merge(arr1, arr2):
    result = []

    for i in range(len(arr1) + len(arr2)):
        if len(arr1) == 0:
            return result + arr2 
        if len(arr2) == 0:
            return result + arr1
        
        if arr1[0] < arr2[0]:
            result.append(arr1.pop(0))
        else:
            result.append(arr2.pop(0))
    
    return result

def mergeSort(arr):

    if len(arr) == 0 or len(arr) == 1:
        return arr
    
    if len(arr) == 2:
        if arr[0] < arr[1]:
            return arr
        else:
            return [arr[1], arr[0]]

    mid = len(arr) // 2
    leftHalf = mergeSort(arr[:mid])
    rightHalf = mergeSort(arr[mid:])

    return merge(leftHalf, rightHalf)

Quick sort

time complexity : $O(nlog(n))$

def quickSort(arr, low, high):
    if low >= high:
        return
    
    target = arr[low]
    mid = low
    for i in range(low+1, high): 
        if arr[i] < target:
            mid = mid + 1
            arr[i], arr[mid] = arr[mid], arr[i]
     
    arr[low], arr[mid] = arr[mid], arr[low]
    quickSort(arr, mid+1, high)
    quickSort(arr, low, mid)        

Dynamic Programming

• Dynamic programming 이 아닐 때

def fibo(n):
    if n == 0 or n == 1:
        return 1
    return fibo(n-1) + fibo(n-2)

• Dynamic programmin 을 사용하였을 때
  • 관계식과 Cache 사용하기!
  • space complexity 와 time complexity 의 trade off

def fibo(n):
    fibo_arr = []    
    for i in range(n+1):
        if i == 0:
            fibo[0] = 1
        elif i == 1:
            fibo[1] = 1
            
        fibo[i] = fibo[i-1] + fibo[i-2]
 
    return fibo[n];

Array

---

• add?

• remove?

Linked List

---

• singly linked list

• circularly linked list
• doubly linked list

Stack

---

• python list

Queue

---

• queue
• circular queue
• doubly-ended queue (deque)
• priority queue

Heap

---

• parent 값보다 항상 큰 binary tree
• complete 하다 := 각 level 의 node 가 maximal
• insert : log n. 밑 바닥에 넣음
• delete : log n. 맨 위 값(min) 를 뺌.
• array 로 구현할 때
  • 왼쪽 : $2f(p) + 1$
  • 오른 쪽 : $2f(p) + 2$
• heap 을 priority queue 만들 때 쓰면?
  • 넣고 뺄 때 $O(log(n))$​
  • unsorted list / sorted list / heap 과 비교
    • insert 자주 일어나면 unsorted list
    • min 조회 자주 일어나면 heap or sorted list
    • 둘 다 자주 적당히 일어나면 heap
• buttom up 방식으로 construction 하면 $O(n)$​
• heap sort
  • min 값 계속 빼면 sort 됨 ㅋ
  • heap 만드는데 O(n) + 하나 빼는데 O(log n) * n 개

Hash table, Map, Skip List

---

Map : (key, value) 로 저장하는 형태

Hash map

hash function mod

• chain
• probe
  • linear probe
  • quadratic probe

skip list

linked list 를 binary search

Tree

---

• Tree

• Binary Search Tree

  

• Balanced Search Tree

  • rotation
    • single rotation
    • double rotation (trinode restructuring)

• AVL Tree

  • Height Balance Property : For every interval position p of T, the heights of the children of p differ by at most 1
  • AVL tree := 위 조건을 만족하는 binary tree
  • height 변화 감지하여 trinode restructuring

• (2, 4) Tree

  • multiway search tree 중에 depth 같고 children 최대 4명
  • 넣다가 4명 넘으면 중간 값 하나 위로 올림 (split)
  • 값이 비면 parent 에서 값 가저옴 (fusing)

• AVL tree & 2,4 tree 는 balancing 에 많은 시간 쏟음

  • O(1) 이긴 한데 여러번의 step 이 필요할 수도 있음

• Red - Black Tree

  • balance 에 O(1)
  • rule
    • root is black
    • external node is black
    • children of red is black
    • every external node has same black depth

  

  • insertion
    • sibling 이 black -> trinode reconstruction
    • sibling 이 red -> 검은색 한 단계 아래로 보냄
  • deletion
    • 없어지는게 흰색이면?
      • child 중에 흰색인거 옮기거나
      • 둘 다 검은색이면 검은색 중 하나 흰색으로 만들면 됨
    • sibling 이 black & sibling 이 red child 가지고 있음 -> trinode reconstruction
    • sibling 이 black & children 둘 다 black -> recoloring
    • sibling 이 red -> single rotation & recoloring
  • https://www.cs.usfca.edu/~galles/visualization/RedBlack.html 이 사이트에서 실험해보기!

Graph

---

• DFS & BFS

  

  Shortest Path

  • Dijkstra’s Algorithm
  • Bellman fold Algorithm

  Minimum Spanning Tree

  • Kruskal’s Algorithm

  • Prim - Jarnik Alrogithm