필기용 블로그

○Depth-First Search (DFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/BACK)

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

  ▶모든 Vertices에 대해 DFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹 

   ▶vertex의 모든 incident edges에 대해

    ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

     ▷opposite이 UNEXPLORED라면,  edge를 DISCOVERY로 마킹하고, opposite에 대해 DFS(G,v)

     ▷opposite이 UNEXPLORED가 아니라면 edge를 BACK으로 마킹

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

 ▶Path finding

  ▷원래 알고리즘에서 Stack추가 (목적지에 도달하면 Stack 반환)

  ▷방문시 push, 나갈시 pop.

 ▶Cycle finding

  ▷back edge (v, w)를 만나면 w까지의 stack을 반환

○Breadth-First Search (BFS)

 ▷G의 모든 Vertices, Edges를 탐색

 ▷G가 Conncted graph인지 확인

 ▷G의 Connected components를 계산

 ▷G의 Spannng forest를 계산

 ▷O(e + v) - 각 vertex/edge가 2번씩 마킹됨. (UNEXPLORED, VISITED/CROSS)

 ▶Algorithm

  ▷모든 U, V를 UNEXPLORED로 마킹

  ▶모든 Vertices에 대해 BFS(G, v)를 적용

   ▷해당 vertex를 VISITED로 마킹

   ▷새로운 Sequence (L_0)를 만들고 해당 Vertex를 insertBack

   ▷i = 0

   ▶L_i가 empty할 때 까지

    ▷새로운 Sequence (L_i+1) 생성

     ▶모든 L_i element에 대해

      ▶모든 incidend edges에 대해

      ▷만약 UNEXPLORED라면, edge의 opposite를 받아옴.

       ▷opposite이 UNEXPLORED라면,

        ▷edge를 DISCOVERY로 마킹

        ▷opposite을 VISITED로 마킹후, L_i+1에 insertBack

       ▷opposite이 UNEXPLORED가 아니라면 edge를 CROSS으로 마킹

    ▷i++

 ▶특성

  ▷모든 Vertices, Edges를 방문

  ▷DISCOVERY edges로 Spanning Tree를 만들 수 있다.

  ▷L_0을 root로 한 Tree로 봤을 때, 각 Level은 root에서 도달하는데 필요한 최소 edge 수이다.

※DFS vs BFS

●Graphs

 ▶Graph G = (V, E)

  ▷V : Set of Vertex(Nodes), 정점 - Vertices

  ▷E : Collection of pairs of Vertices - Edges

  ▷V, E는 positions이고, elements를 저장한다.

 ▶종류

  ▶Directed graph

   ▷모든 edge가 Directed edge - 순서가 정해진 Edge (Origin(tail) -> Destination(head) )

  ▶Undirected graph

   ▷모든 edge가 Undirected edge - 순서가 없는 Edge

 ▶활용

  ▷전기회로

  ▷교통망

  ▷컴퓨터 네트워크

  ▷데이터베이스

 ▶용어

  ▶Endpoints of an edge

   ▷edge에 연결된 두 vertices

   ▷a - U, V

  ▶Edges incident on a Vertex

   ▷vertex에 연결된 edges

   ▷V - a, d, b

  ▶Adjacent vertices (인접한 vertices)

   ▷edge 하나로 연결되는 vertices

   ▷U, V

  ▶Degree of a vertex

   ▷vertex에 연결된 edges의 개수 (loop - 2개처리)

   ▷X : 5

  ▶Parallel edges

   ▷동일한 vertices와 연결된 edges

   ▷h, i

  ▶Self-loop (loop)

   ▷하나의 vertex와 연결된 edge

   ▷j

  ▶Path

   ▷하나의 Vertex로부터 edges, vertices를 거쳐 다른 Vertex로 가는 길

   ▶Simple Path

    ▷거치는 모든 Vertices, Edges가 반복되지 않음

  ▶Cycle

   ▷시작 Vertex와 끝 Vertex가 동일한 Path

   ▶Simple Cycle

    ▷거치는 모든 Vertices, Edges가 반복되지 않음

  ▶Subgraph

   ▷한 Graph의 일부로 만든 다른 Graph

   ▷Subgraph G' = (V', E')에서 V' ⊆ V, E' ⊆E

   ▶Spanning subgraph

    ▷Graph의 모든 Vertex는 포함하지만, 일부 Edge를 포함하지 않음.

    ▷Spanning subgraph G' = (V', E')에서 V' = V, E' ⊆E

  ▶Connected Graph

   ▷모든 Vertex pair에 대해 한쪽에서 다른 한쪽으로 가는 path가 존재함.

  ▶Connected component

   ▷가능한 최대로 연결된 connected subgraph

  ▶Complete Graph

   ▷모든 Vertex에 대해 가능한 최대의 edge를 연결한 것.

   ▷edge 개수 : v(v-1)/2 (v: vertex 개수)

  ▶(Free) Tree

   ▷Cycle이 없는 Undirected Connected Graph

   ▷Spanning Tree : Tree인 Spanning subgraph

  ▶Forest

   ▷Cycle이 없는 Undirected Graph

   ▷Forest의 Connected components는 Tree이다.

   ▷Spanning Forest : Forest인 Spanning subgraph

 ▶속성 (v : vertex 개수, e : edge 개수)

  ▷Σdeg(v) = 2e 

  ▷e ≤ v(v-1)/2 - complete graph의 edge 개수보다 작거나 같다.

○Graph ADT

 ▷Vertices, Edges는 position으로 구현한다.

 ▷element를 저장한다.

 ▶메소드

  ▶Accessor

   ▷e.endVertices() : e의 Endpoint vertices의 list 반환

   ▷e.opposite(v) : e에서 v의 반대쪽에 있는 vertex 반환

   ▷u.isAdjacentTo(v) : u와 v가 adjacent하다면 true 반환

   ▷*v : vertex v의 element

   ▷*e : edge e의 element

  ▶Update

   ▷insertVertex(o) : element o를 저장하는 vertex를 생성

   ▷insertEdge(v, w, o) : v, w vertices를 연결하는 element o 를 저장하는 edge 생성

   ▷eraseVertex(v) : vertex v 제거

   ▷eraseEdge(e) : edge e 제거

  ▶iterable collection

   ▷incidentEdges(v) : v와 연결된 edges의 list

   ▷vertices() : 그래프의 모든 vertices의 list

   ▷edges() : 그래프의 모든 edges의 list

 ▶Edge List Structure

  ▶Vertex Object

   ▷element를 저장

   ▷vertex sequence에서 position을 저장

  ▶Edge Object

   ▷element를 저장

   ▷edge sequence에서 position을 저장

   ▷origin/destination vertex object를 저장

  ▶Vertex sequence : vertex objects의 sequence

  ▶Edge sequence : edge objects의 sequence

  ▷Vertex에 관한 메소드가 비효율적

 ▶Adjacency List Structure

  ▷Edge List Structure를 기반으로 함.

  ▷Vertex 메소드의 효율성 개선

  ▶각 Vertex에 Incidence sequence 추가

   ▷각 Vertex가 Incident edges의 List를 가짐.

  ▶각 Edge가 Incidence sequece에서 자신의 position을 저장

 ▶Adjacency Matrix Structure

  ▷Edge List Structure를 기반으로 함.

  ▷각 Vertex가 고유한 Integer key값을 가지고 있음.

  ▶2차원 배열 Adjacency array

   ▷행의 Key값, 열의 Key값이 연결되는 Edge를 가졌다면, 그 Edge에 reference함. (Nondirected - 대각선에 대해 대칭)

   ▷연결되는 edge가 없으면 null값

 ▶Performance

●Heap

 ▷Binary Tree의 일종

 ▷Node에 key값들을 저장한다.

 ▶조건

  ▶Heap-Order : key(v) ≥ key(parent(v)) 만족

   ▷최소 Heap - root = 최소 key

   ※ key(v) ≤ key(parent(v)) 인 경우, 최대 Heap

  ▶Complete Binary Tree 만족

   ▷높이가 h인 Binary Tree에 대해서, depth i (i < h)에는 2ⁱ 개의 Node가 있다.

   ▷Internal nodes는 External nodes의 왼쪽에 있다.

 ▶Height of a Heap

  ▷n개의 key를 가지는 Heap의 height : log(n)

  ▷n = 1 + 2 = 4 + ... + 2^h-1 + (1 ~ 2^h) ＜ (2^h+1)

 ▶Bottom-up Heap Construction

  ▶Heap Merging 이용

   ▷2개의 Heap과 새로운 key K에 대해

   ▷k를 root로하며, 2개의 Heap을 subtree로 하는 Heap 생성

   ▷downheap - heap order restore

  ▶phase i에서

   ▷2ⁱ - 1의 heap 2개를 가지고 2ⁱ⁺¹ - 1인 Heap을 만듬.

   ▷O(log(n))

 ▶Heap - Priotity Queue

  ▷Heap을 이용하여 Priority Queue 구현

  ▷각 Node에 Key, Element 저장

  ▷Insert, removeMin 효율적으로 동작 가능

  ▷Last Node Tracking (마지막 노드)

  ▶Insertion

   ▷Last Node 다음에 새로운 element 저장 (key값 저장, Last Node Update)

   ▶Heap Order Restore (Upheap)

    ▷새로운 Node가 Heap order를 만족하지 않을 수 있음.

    ▷부모 노드로 가며 Swaping (key값이 부모 노드보다 작으면 Swap)

    ▷root이거나, 부모 노드보다 클 때 까지 반복

    ▷O(log(n))

  ▶Removal

   ▷Root Node의 Key를 제거

   ▷공백을 Last Node로 매꿈 (+Last Node Update)

   ▶Heap Order Restore (Downheap)

    ▷새로운 root Node가 Heap order를 만족하지 않을 수 있음.

    ▷root에서 자식 노드로 가며 Swaping (key값이 자식 노드들보다 크면 자식 중 하나와 Swap)

    ▷최대 height (log(n)) 에 도달하거나, 자식 노드들보다 작을 때 까지 반복

    ▷O(log(n))

  ▶Last Node Update

   ▷left child에 도달하거나, root에 도달할 때 까지 위로 감. (부모로 감)

   ▷left child에 도달한다면, right child로 이동

   ▷leaf까지 왼쪽 아래로 이동

   ▷O(log(n))

○Heap-sort

 ▷Heap으로 구현된 Priority Queue의 Sorting

 ▷차지하는 공간 : O(n)

 ▷Insert : O(log n)

 ▷removeMin : O(log(n))

 ▷n개의 element : O(n log(n))

○Vector-based Heap

 ▷Vector로 Heap 구현

 ▷length : n + 1인 Vector 사용 (index 0은 사용하지 않음)

 ▶Positioning : rank i의 Node에 대해

  ▷left child : rank 2i

  ▷right child : rank 2i+1

 ▷Insert(e) : rank n+1에 insert

 ▷removeMin() : rank n remove

 ▶In-place Heap Sort

  ▷1. Vector를 Heap으로 만듬

  ▷2. removeMin()하며 Sorting

●Priority Queues

 ▷우선순위의 개념으로 entry들의 집합을 저장함.

 ▷entry: key, value의 짝

 ▷위치가 아닌 우선순위를 기준으로 저장

 ▶메소드

  ▶Main Methods

   ▷Insert(e) : entry e 추가.

   ▷removeMin() : key값이 가장 작은 값(들)을 제거, return

  ▶Additional Methods

   ▷min() : 가장 작은 key를 return (지우진 않음)

   ▷size()

   ▷empty()

 ▶Total Order Relation

  ▷Key값 : 순서가 명시되는 arbitary object여야함.

  ▷다른 2개의 entry가 동일한 key를 가질 수 있다.

  ▶비교 규칙

   ▷Reflexive property (반사성) : x ≤ x

   ▷Antisymmetric property (비대칭성) : x ≤ y ∧ y ≤ x => x = y

   ▷Transitive property (이행성) : x ≤ y ∧ y ≤ z => x ≤ z

○Sequence-based Priority Queue

 ▶Unsorted List

  ▷정렬되지 않는 상태로 저장

  ▶Algorithm

   ▷Insert : O(1) - 바로 넣음.

   ▷removeMin : O(n) - 가장 작은 값 찾아야 함.

 ▶Sorted List

  ▷정렬된 상태로 저장

  ▶Algorithm

   ▷Insert : O(n) - 적절한 위치에 넣어야 함.

   ▷removeMin : O(1) - 가장 앞의 값

○Priority Queue Sorting

 ▷1. 모든 element들을 priority queue에 넣음.

 ▷2. removeMin으로 가장 작은 element부터 가져옴.

 ▶Selection Sort

  ▷Unsorted List를 이용

  ▷1. n개의 insert -> O(n)

  ▷2. n번의 removeMin -> 1+2+...n = n(n-1)/2

  ▷-> O(n²)

 ▶Insertion Sort

  ▷Sorted List를 이용

  ▷1. n개의 insert -> 1+2+...n = n(n-1)/2

  ▷2. n번의 removeMin -> O(n)

  ▷-> O(n²)

○Comparator

 ▷우선순위 비교를 위한 

 ▶isLess(p, q)

  ▷return p < q;

 ▷같다 : !isLess(p, q) && !isLess(q, p)

○Binary Tree

 ▶다음 규칙들을 가진 Tree

  ▷각 노드가 최대 2 개의 자식 노드를 가진다.

  ▷노드의 자식은 ordered pair를 이룬다. (left child, right child의 순서가 다르면 다른 Tree)

 ▶재귀적 정의

  ▷single node로 이루어져 있거나

  ▷root가 ordered pair인 자식을 지니고, 각각이 binary tree이다.

 ▶ADT

  ▷Tree ADT의 확장

  ▶Additional methods

   ▷position p.left(): left child의 position

   ▷postion p.right(): right child의 position

 ▶예시

  ▶Arithmetic Expression Tree: 수학 계산을 나타내는 Tree

   ▷Internal nodes: 연산자

   ▷External nodes: 피연산자

  ▶Decision Tree: yes/no 결정을 나타내는 Tree

   ▷Internal nodes: yes/no의 답을 할 수 있는 질문

   ▷External nodes: 결정(결론)

 ▶Proper Binary Tree

  ▷자식 노드가 0개 또는 2개이다. (1개일 경우 없음)

  ▶성질 (n: 노드 수 / e: external node 수 / i: internal node 수 / h: height)

   ▷e = i + 1

   ▷n = 2e - 1

   ▷h ≤ i

   ▷h ≤ (n-1/2

   ▷e ≤ 2^h

   ▷h ≥ log₂e

   ▷h ≥ log₂(n+1) - 1

 ▶순회

  ▶Inorder Traversal

   ▷left child -> node -> right child 순으로 순회

   ▷Artithmetic Expressions를 출력할 때 사용 가능

    ▷left subtree이전에 (, right subtree이후에 )추가

  ▶Postorder traversal

   ▷Arithmetic Expressions를 계산할 때 사용가능

    ▷양 옆의 노드를 재귀호출 (External -> 값, Internal -> 계산한 값)

  ▶Euler Tour Traversal

   ▷일반적인 Binary Tree 순회방법

   ▷Tree를 왼쪽에서부터 따라 가며, 노드들을 방문함. (한 노드당 최대 3번 방문 가능)

   ▷Proper binary tree인 경우, internal node에 대해서는 반드시 3회 방문한다. (external - 1회)

 ▶구현

  ▶Linked Structure

   ▷Position ADT를 포함한다.

   ▷각 노드는 다음의 정보를 가진다.

    ▷Element (요소)

    ▷Parent node

    ▷Left Child

    ▷Right Child

  ▶Array-Based Representation

   ▷Node들은 Array[rank(v)]에 저장되어있다.

   ▷각 child에는 다음과 같이 저장되어있다.

    ▷left child: rank(node) = 2×rank(parent(node)]

    ▷right child: rank(node) = 2×rank(parent(node)]+1