자료구조 강의정리(k-mooc)

 

시간복잡도-주어진 N대비 소모시간

=> weak ordering : 약하게 순서매기기

 

Shortest path

 

Minimum Spanning Tree

 

Topological Sort and Critical Path(a.k.a 순서)

 

Dynamic Programming : sub-problems로 나눠서 결과취합하여 최종적인 결과도출

-Ex) edit distance(ex.키워드찾아주기)

-matrix chain multiplication

 

 

[Array&Stack&Queue]

<Array->Linked lists(연결리스트)>

<Stack(LIFO)>

-push&pop: 처리가 항상 top에서만 일어남

-Parenthesis(괄호) Matching가능

여는괄호 -> stack push

닫는괄호 -> stack 괄호pop&matching

<Queue(FIFO)>

-insertion: rear(or back or tail)

-deletion: front(or head)

=>enqueue dequeue 둘이 다른 위치에서 발생됨

 

—linear queue(logical): 계속 뒤로 밀리기때문에 앞에 공간비어도 저장못하는 problem

—circular queue: 공간 최대활용형태

 

<Tree>

-degree: number of children nodes

—Leaf(degree==0)&Internal(degree>=1) Nodes

 

-unordered(ordinary), ordered: children nodes에 순서가 있는지없는지

 

-Paths: sequence of nodes(a0, a1, … an)

—lengths of path: n(0부터 시작하는거 잊지말기 즉 3개면 3-1=2)

 

-Depth: root->해당node까지의 length

—경로는 unique하다(하나의 경로만 존재)

 

-Height: maximum depth of all nodes => empty tree’s height = -1

 

-ancestor&descendant-> 자기는 자기자신의 조상이자 자손으로 정의한다

—strictly descendant: 자기자신이 스스로의 조상/자손 되는것 금지

 

>>Tree 표현: list representation for child nodes(using linked list)

 

:각 node들이 포함하는 자녀들의 개수만큼 reference하고 있는 linked 구조

 

<Graph>

:인접한 정보(관계성-edge로 연결)를 저장하는 자료구조

-Object(or vertex)

 

Undirected Graph(순서가 없는 pair)

—maximum edge== 조합 vC2

-Degree: 인접 이웃(연결되어있는)의 갯수

-Sub Graph: Original graph에서 edge,vertex들을 추출했을때 그 추출한 것을 말함

-Path: 몇개의 edge를 거쳐갔는지(몇개의 vertex가 있는지가 아님)

—trivial path: length==0(자기자신에 머물러있는거)

—simple path: 중복을 제외한 경우(처음/끝 제외) -> 처음==끝 : simple cycle

-Connectedness: 어떤 두 vertex를 봐도 연결된 그래프를 connected라고 봄

 

>Weighted (연결됨+숫자/값 부여함)

-Path length: 각 edge의 값을 더한것 (shortest path=lowest value of sum)

 

-Tree도 Graph의 한 종류로 볼 수 있음

—> graph가 tree가 되려면 connected&&경로가 unique -> edge개수 = node개수 -1

->tree는 cycle이 X, if 아무데나 edge추가시 cycle생김

->하나의 edge 제거시 disconnected되어 두개의 서로다른 graph로 나뉨 ->두개의 tree로 존재됨

 

Directed Graph : edge에 방향성이 부여됨

-Degree(in-degree 나로 들어오는 edge/out-degree 나로부터 출발하는 edge)

—Sources: in-degree==0 / Sink: out-degree==0

-Path: Directed graph에서 방향성 고려함

-Connectedness: 방향성 고려&&all pairs connected=strongly connected

방향성 무시하고 connected=weakly connected

>Weighted(same)

>Directed Acyclic Graph(DAG): 방향이 있으나 No Cycle!!

partial ordering, 즉 커리큘럼같은 순서정하는것에 많이 사용됨

 

>>graph representation

1. Binary-relation list: edge 쭉 나열 -> edge 수만큼 메모리 필요
2. Adjacency matrix
3. Adjacency list

 

<Forest>:tree들의 집합

-tree에서 connectedness제거 —> no cycle

-vertex > edge

-forest에서 edge하나 제거시 tree+1