[알고리즘2] 기말고사

8장 symbol table

 

BST

->목표 효율적인 symbol table(2-3 tree,B-tree(2-3tree확장형) 등등) 구현-> 2-3 tree 대부분 작업에 대해 log N

1. 왼쪽 오른쪽 중 어느쪽이라도 먼저 자식이 추가될 수 있음

2. 배열로 구현 어려우며,자식/부모와 링크 포함해 실제 트리 구조 구현

조건-> Symmetric order: 왼쪽 key< 부모 key < 오른쪽 key (symbol table의 key 탐색에 효율적인 조건)

성능-> 트리의 깊이에 비례 (~depth) 

원소 추가삭제 순서에 따라 깊이는 log N~N까지 가능하다(logN<<√N <N) 추가삭제할때 순서반복에 의해(ordered iteration)N까지 가능

 

 

Symbol table 의 다른 구현방식 : hash table(key같은 정확히 같은값 탐색에 유리(단점:근접한 값탐색(범위탐색) 원소순서 파악 불리))

hash 함수 h(key)로 계산한 값을 index로 사용해 hash table의 저장할 위치에 바로 접근->주의점: 같은 자리에 여러원소 놓이게 되는 충돌을 막는것이 중요(같은자리에 여러원소 놓이게 되면 탐색시간 증가)

따라서 get(key),put(key,value)모두 상수시간 ~1에 수행가능

 

hash table(한개의 정확한 key값 구함) vs bst(여러 필요한 key 값을 구함 범위탐색)->상황에따라 쓰셈!

 

이번에는 BST 기준으로 symbol table 본다

 

2-3Tree

 

2node:bst와 동일 ->(상수시간만큼의 차이) 3-node:k1<k2

but,  같은 logN 시간

 

 

2-3 Tree 에서의

get(key): 3방향중 하나로 이동.   2node:bst와 동일 ->(상수시간만큼의 차이) 3-node:k1<k2but,  같은 logN 시간

put(key,val): get(key)처럼 추가 위치 찾고 k node를 ->k+1 node로 만듬 (2node->3node , 3node->임시로 4node)

4node는 2node 두개로 split 됨(가운데 key를 부모노드로 두고 만듬)->깊이 1증가 (부모가 생김)

 

 

 

 

split 특징:

2-3 node :4node되면 split(특징 split시 양쪽이 균형잡힌 트리로 분화)

2-tree: 3-node 되면 split(양쪽균형 깨짐)

put 하는법

2-3 tree에서 put(key,value)-> 내려가며 추가위치 찾음(depth),올라오며 split(depth)

node추가하기위해 내려가면서 put위치 찾음 넣고, root 방향으로 올라가면서 split 반복함

->put 시간복잡도 : log N에 비례하는 시간에 종료

 

2-3 tree 성능: worst case ~log N 

 

따라서 2-3 tree는 좋으나 올바른 구현이 어려워서 bst 코드를 재활용 변형하여 구현함

 

2-3tree와 bst가 합쳐진것이  Red Black BST 라고 함

 

LLRB(Left-Leaning Red-Black) BST: BST로 표현한 2-3 tree

내부연결(Red),외부연결(Black)구분해표현
내부연결은왼쪽으로기울어지도록(Left-Leaning)표현:
원래BST의특성에맞게작은값을큰값왼쪽에두는데,특히큰값이부모가되도록표현

 

 

LLRB와 RLRB의 차이

RLRB:내부연결에서의 작은값을(위에) 부모로 큰값을 오른쪽 자식으로

LLRB:내부연결에서의 큰값을 부모로 작은 값을 왼쪽 자식으로

 

 

4-node: 경우

양쪽 자식과 link가 모두 RED면, 

1 이들을 BLACK으로 만들며 

2 부모와의 링크를 RED로 flip(밑에 예시)

 

get(K) 등 탐색작업은 기존의 BST 코드 그대로 수행함

 

LLRB 정리: 기본 BST의 2-3 tree 규칙 따른 변형
 지금까지 본 것처럼 2-3 tree 규칙에 맞게 BST 운영하면 상당히 균형 잘 잡음
 Worst-case에도 대부분 작업에 대해 ~log N 성능 유지
 2-3 tree는 다양한 프로그래밍 언어에서 symbol table 구현에 사용
 (Java) TreeMap, TreeSet, (C++) map, multimap, multiset, ...
 2-3 tree의 확장형인 B-tree는 다양한 file system, database 구현에 사용 § (Windows) NTFS, (Mac) HFS, HFS+, (Linux) JFX, XFS, ...
 Database: ORACLE, PostgreSQL, ...

 

 

1-D Range Count(lo, hi): lo≤key≤hi 범위의 key 개수 찾기

rangeCount(F, T)

rank가 없을 경우 자기바로 다음 값의 rank ()********************의문

 

실습 Sweep-line 수평선에따라 scan 교차 확인

 

---

9장 Undirected and Directed Graphs

Digraph (Directed Graph) 한방향성 있는 그래프가 더 복잡함

간선이 양방향으로 있는 그래프는 digraph의 부분 집합 “모든 간선이 양방향으로 있는”Digraph로 볼 수 있으며,

->undirected graph로 단순화해 표현

 

 

single source 보다 multi source가 더짧은 거리를 사용

multi source : 여러 출발지s...에서 동시에 BFS 진행 -> s...모두를 큐에 넣고 탐색 시작 ->목적지까지 최단 경로를 찾음

single source : 한 출발지s에서 BFS 진행 ->s만 큐에 넣고 탐색 시작

 

[Q] multi-source BFS가 있다면, multi-source DFS는 없는가?

없다 multi-source DFS 와 DFS(sigle source)랑 기능 상 동일하기 때문에

 

Garbage collection 사용하지 않는 객체 주기적으로 확인해 메모리에서 삭제함

 

DFS 탐색시 깊이 우선이라서 한 도메인에 빠져 무한루프 걸릴 위험성

BFS를 웹 크롤링에 사용하는이유!!->여러 브랜치를 돌아가며 탐색하여 같은 시간에 더 다양한 도메인 발견 가능

 

Topological Sort (위상 정렬,DFS의 역순) 수행시간 V+E 

간선 향하는 방향 순으로 정점의 순서 정함(간선이 한방향으로만 향하도록 정점의 순서 정함)

Topological order 순으로 정점 나열하는 것을 topological sort라 함(v->w 경로있을시 v 후에 w가 오도록)

고도화 높은 방향에서 물이 흐르는 방식

topological sort: topological sort로 Topological order를 얻기 위한 정렬방법이다.

Topological Order: Topological sort를 수행한 결과 얻은 정점의 순서를 말함

 

실제로 활용되는 곳: Task(Job) Scheduling: 여러작업 간 선후관계 있을때, 이를 따르도록 수행하는 순서 정하기

 

"Cycle 없는"이라는 조건이 Topological order에 존재한다

Cycle이 만약 있다면 topological order는 존재할수없다->TRUE

 

같은 그래프에 대해 여러 topological order 존재가능(밑에 사진 예시)

 

 

topological order 구하는 법:물이 가득차고 그것의 역순으로 정렬 (DFS와 동일)

물이 가득차고 그것의 역순으로 정렬

2->1->3->0. ==> 정답: 0->3->1->2

 

따라서 DFS로 정점을 구하고 역순으로 정렬하면 답이 나온다->복수의 답이 나올수있음

->번외)bfs는 맞는답이 나올수도있지만 문제가 많다 DFS 는 선후관계가 없어도 항상 맞는답이 나온다!!

 

 

 

Toplogical Sort 의 수행시간은 V+E에 비례한다

 

Strongly-Connected Component(SCC)의 탐지 ->topological order의 역순(DFS역순의 역순) 또는 BFS 가능
(strongly+방향성 없는 그래프 => digraph 한방향성 존재하며 사이클 존재)

digraph 간선에 방향성있는 그래프: 

strongly-connected(v,w): v→w, w→v 경로 모두 존재
Strongly-Connected Component (SCC): 서로 간에 모두 strongly-connected인 (양방향으로 도달 가능한, 즉 갔다가 돌아올 수 있는) 정점의 최대 집합-->digraph 중에서도 순환이 되는 애들

 

undirected graph 모든 간선이 양방향:

connected(v,w): v-w 경로 존재
connected component: 서로 간에 모두
연결된 (도달 가능한) 정점의 최대 집합

->그냥 connected 하면 양방향임

 

**** SCC 존재 유무 확인법****

(1)같은 SCC 내부에는 반드시 cycle 존재 (즉 양방향 경로 존재)
(2) 서로 다른 SCC 간에는 (i) 간선이 없거나 (ii) 간선이 한 방향으로만 존재. 즉 서로 다른 SCC 간에는 양방향으로 간선이 존재하지 않음 (cycle 없음)

 

Naïve한 (Brute-force) 방법: 모든 정점의 쌍 v, w에 대해 DFS(v) 해서 w에 도달 가능한지 확인하고
DFS(w) 해서 v에 도달 가능한지 확인

->성능은 무엇에 비례하나 scc->v^2(V+E)==~V^3==N^3

->N으로 만들고싶다!!!!

 

 

Topological order의 역순 얻어야 하므로 reverse graph에 DFS 적용

 

 

 

 

 

Kosaraju-Sharir (코사라쥬-샤이르) 알고리즘
(Phase 1) Reverse graph의 (DFS 적용해) topological order 얻기 

(Phase 2) 그 순서로 원래 그래프에 DFS (or BFS) 수행해 SCC 찾음

Kosaraju-Sharir 알고리즘이 digraph에서 SCC를 찾는 시간은 다음 중 무엇에 비례하나?

V+E

---

10장 WordNet

---

11장 MST