생성일: 2021년 11월 23일 오후 10:51

Heap

• 바이너리 트리 인데 특정한 모양과 순서를 만족 시키는 것
  • 모양 : complete binary tree
  • 순서 : 자신이 자신의 자식들보다 더 커야 함 (max-heap 기준)

Heap의 예시

• max-heap : 큰 것이 위에 있는 형태
• min-heap : 작은 것이 위에 있는 형태
• Complete binary tree 모양이여야 하므로 위의 그림처럼 제일 오른쪽 subtree에서 자식을 하나만 가져야 한다면 left child여야 한다. (right child만 가지면 heap X)
• 구현

  • Array를 이용하면 구현하기 쉽다. Why? complete binary tree이기 때문에 중간에 빈 공간없이 순서대로 나열시킬 수 있기 때문이다. BST를 어레이로 구현할 때의 인덱스 번호 배치 규칙을 따른다.

    

• 주요 함수
  • ReheapDown
    • deleteItem 등의 작업으로 작은 아이템이 위에 있을 때 순서를 바로잡는 기능 (재귀적)
  • ReheapUp
    • insertItem 등의 작업으로 큰 아이템이 아래에 있을 때 순서를 바로 잡는 기능 (재귀적)
• 가장 큰 노드 (root)를 반환하고 지울 때 heap을 유지하는 방법
  • rightmost element를 복사하고 root에 붙여 넣음
  • rightmost element 삭제
  • ReheapDown으로 순서 바로 잡기
• heap에 새로운 element insert하고 heap을 유지하는 방법
  • 새로운 element가 heap의 rightmost element가 되도록 위치시키기
  • ReheapUp으로 순서 바로 잡기

Priority Queue

• queue인데 highest-priority element를 Dequeue하는 구조 (예, 가장 큰 노드 먼저 or 가장 작은 노드 먼저)
• 구현 방법 (다양한 방법으로 구현 가능하지만 Heap이 가장 효율적)
  • Unsorted list
    • Dequeue 할 때 리스트의 모든 요소를 매번 확인해야 함 ⇒ 비효율
  • Array-Based Sorted List
    • Enqueue가 비효율적
  • Linked Sorted List
    • Enqueue가 O(N) ⇒ 비효율
  • Binary Search Tree
    • 평균적으로 O(logN) (dequeue or enqueue) 그러나, 일자로 쭉 나열되어 있는 BST일 경우 O(N) ⇒ 운 없으면 비효율적
  • Heap
    • O(logN) 보장 (complete binary tree이기 때문에)

Skewed는 BST에서 일자로 쭉 나열되게 형성된 경우

---

Graph

• nodes(vertices)와 edges의 집합으로 이루어진 자료구조
• G = (V, E)
  • V(G) : finite, nonempty set of vertices
  • E(G) : a set of edges (pairs of vertices)
• 그래프의 edge는 방향성(direction)이 있을 수도, 없을 수도 있다. ⇒ 있으면 화살표로 표현 and 튜플로 표현할 때 순서에 주의해야 함 ex) (1,3) ≠ (3,1)
• Tree는 그래프의 특수한 케이스 (부모가 한개의 노드 and 사이클이 없음)
• 용어
  • Adjacent nodes : 이웃한 노드
  • Path : a sequence of vertices that connect two nodes in a graph
  • Complete graph : a graph in which every vertex is diretly connected to every other vertex
• Complete directed graph (with N vertices) 예시 그림에서는 4P2(순열)
  
• Complete undirected graph (with N vertices) 예시 그림에서는 5C2 (조합)
  
• Weighted graph

  • a graph in which each edge carries a value

    

Graph implementation

1. Adjacency Matrix : Array-based implementation

   • 1D array ⇒ vertices를 저장
   • 2D array ⇒ adjacency matrix, edges 정보를 저장

   

2. Adjacency List : Linked-list implementation

   • 1D array ⇒ vertices를 저장
   • 각 vertex 노드는 인접한 노드를 링크드 형식으로 저장

   

• 1번과 2번 구현의 장단점
  • Adjacency matrix (Array implementation)
    • Good for dence graphs(V가 E보다 훨씬 많으면 2차원 어레이의 대부분의 공간이 0으로 가득참 ⇒ 비효율) : |E| ~ O(|V|^2)
    • Memory requirements : O(|V| + |E| ) = O(|V|^2 )
    • Connectivity between two vertices can be tested quickly
  • Adjacency list (Linked-list implementation)
    • Good for sparse graphs : |E|~O(|V|)
    • Memory requirements : O(|V| + |E| ) = O(|V| )
    • Vertices adjacent to another vertex can be found quickly

Graph searching

• 두 노드간의 path를 찾을 때 (e.g., Austin and Washington)
• 크게 두가지 방법이 존재

1. DFS (Depth-First-Search) : 깊이 우선 서치
2. BFS (Breadth-First-Search) : 너비(폭) 우선 서치

DFS (Depth-First-Search)

• 깊은 지점까지 쭉 내려가고 올라오면서 경로를 확인
• 가장 깊은 곳 까지 내려감
• Stack을 사용하여 구현
• 알고리즘
  

출발지점부터 Stack에 넣고 pop을 함 ⇒ pop한 결과물과 인접한 vertex들(Queue에 담아서 저장)을 stack에 넣는다 ⇒ 계속 반복(깊이 내려감) ⇒ 한번 방문한 vertex는 다시 넣지 않는다(mark 필요) ⇒ 목적지까지 도착하면 True를 리턴

BFS (Breadth-First-Search)

• 한 level의 모든 노드들을 방문 ⇒ 다음 level의 노드를 전부 방문 (한 층씩 넓혀 나감)
• 같은 깊이의 가능한 모든 경로를 다 확인하면서 밑으로 내려간다
• Queue을 사용하여 구현
• 알고리즘
  

출발지점부터 Queue에 넣고 Dequeue함⇒ Dequeue 된 vertec와 인접한 vertex들(다른 Qeueu에 넣어서 저장) 을 Enqueue함 ⇒ 계속 반복하면서 검사한 범위를 확장 시킴 ⇒ 번 방문한 vertex는 다시 넣지 않는다(mark 필요) ⇒ 목적지에 도착하면 True리턴

Shortest-path problem

• 단순히 path가 있는지 검사하는 것이 하니라 해당 path의 비용 (weight)을 체크해서 가장 낮은 비용의 경로를 찾는 것
• 다양한 알고리즘들 존재 : Dijkstra's algorithm, Bellman-Ford algorithm
• BFS는 특정한 상황에서 이문제를 해결 할 수 있다.
  • 모든 edge의 weight가 동일하거나 매우 작을 때 ⇒ 그냥 거처간 edge의 수가 적으면 Shortest인 상황 ⇒ BFS 사용가능