티스토리 툴바


'공부/알고리즘'에 해당되는 글 13건

  1. 2011/07/13 Single-Source Shortest Paths
  2. 2011/07/13 Minimum spanning tree (최소신장트리)
  3. 2011/07/13 Elementary Graph Algorithms
  4. 2011/07/11 Data Structures for Disjoint Sets
  5. 2011/07/11 Greedy Algorithms
  6. 2011/07/09 Dynamic Programming
  7. 2011/07/08 11장 Hash Table
  8. 2011/07/03 8장 Sorting in Linear Time
  9. 2011/07/03 7장 Quicksort
  10. 2011/06/30 Heapsort (1)
공부/알고리즘2011/07/13 22:33


Properties of shortest paths

vertax u에서 v로 최소 weight로 가는 path
shortest path의 sub path도 shortest path이다.

Triangle inequality
δ(u, v) ≤δ(u, x) + δ(x, v).
거쳐서 가면 길어진다.

그래프가 음수 weight를 갖는 cycle이 있다면 some shortest paths는 존재하지 않을지도 모른다.
사이클 돌면서 weight가 계속 작아질 수 있으니까 말이다.

Single-source shortest paths

하나의 vertex s∈V가 모든 vertex v ∈ V에 대해 shortest path를 찾기.
만약 모든 edge가 음수가 아니라면 모든 shortest-path weight는 존재한다.
Greedy로 보여줄게.
vertex s부터 시작해서 각 단계마다 s에서 최소로 갈 수 있는 vertex v를 선택해서 s가 속한 집합에 넣는다.
v에 인접한 vertex들의 거리를 수정한다.

Dijkstra’s algorithm

우선순위큐를 가지고 있다. 큐안에는 아직 s로부터 가장 짧은 거리가 정해지지 않은 vertex들이 있다.
큐에 있는 모든 vertex가 시작 vertex s가 속한 집합 S에 포함될 때까지
큐에서 최소값(u)을 뽑아서 S에 포함시킨다.
u의 인접 vertex(v)들에 대해서 u를 통해서 v로 가는 게 원래 가는 방법보다 더 가깝다면 바꿔준다.
우선순위큐의 값이 바뀌게되어서 다시 min heap을 만들어 준다.

Correctness

Greedy라서 맞는지 검증을 해야 한다.
증명 생략

Analysis

 출처 : Introduction to Algorithm
 
모든 edge의 weight가 1이라면 어떻게 될까?
우선순위 큐 대신에 FIFO 큐를 쓸 수 있다.
Breadth-first search와 같다.
O(V+E)


Bellman-Ford algorithm

vertex s∈V 로부터 모든 v∈V에 대한 shortest-path lengths를 찾거나 아니면 negative-weight cycle이 존재하는지 알아내는 방법.

알고리즘
초기화하고, |V|-1 번 모든 edge들을 relax한다. (모든 edge를 relax하고 나면 vertex 하나씩 최소 거리가 정해진다. 가장 긴 simple path는 최대 |V|-1번이다.) 
다 하고 나서 다시 모든 edge (u,v)에 대해서 d[v] > d[u] + w(u,v)가 있는지 찾는다. 음수 사이클이 없으면 d[u]가 최소값이 되어야 된다.
O(VE)

'공부 > 알고리즘' 카테고리의 다른 글

Single-Source Shortest Paths  (0) 2011/07/13
Minimum spanning tree (최소신장트리)  (0) 2011/07/13
Elementary Graph Algorithms  (0) 2011/07/13
Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09


Posted by skyjumps
공부/알고리즘2011/07/13 16:01


Spanning tree
 

그래프에서 그래프의 모든 정점을 다 포함하는 트리.
부분 그래프이다. 트리라서 사이클이 없다.

Minimum spanning tree (MST)
 

spanning tree 중에서 가중치 합이 최소가 되는 spanning tree.
N개 vertex가 있으면 edge는 N-1개 있다.

일반적인 MST
처음에 A를 0으로 놓고 safe edge를 계속 추가해 나간다. 더 이상 안나올때까지 반복.
safe edge : 단계마다 하나의 edge를 선택할 때, minimum spanning tree를 유지하도록 하는 edge.
respect a set A : 그래프를 하나의 선으로 나눌 때, A의 어떤 edge도 그 선을 지나가지 않을 때, 그 선이 A를 respect한다고 한다.
light edge : respect하게 cut(나눈 선)을 지나는 edge 중에서 최소 weight를 가진 edge들 중 하나. (light edge가 여러개 일 수도 있다. 그리고 어떻게 cut을 하느냐에 따라 light edge가 달라질 수 있다.)

light edge면 safe edge이다.

MST 구하는 방법

1. Kruskal algorithm
set A는 forest이다.
전체 forest에서 두개의 tree를 연결하는 weight가 가장 작은 edge를 찾는다. vertex 하나도 하나의 tree이다.
그 edge가 light edge이면 safe edge이다.
safe edge를 set A의 forest에 추가해 나간다.

탐욕적인 방법(Greedy method)이다.

사이클을 이루지 않도록 최소 weight edge를 하나씩 선택해서 모든 vertex가 다 포함되면 minimum spanning tree가 된다.

구현
disjoint-set 이용.
vertex set을 만든다. edge들을 정렬한 다음 제일 작은 edge부터 선택한다. 선택된 edge가 사이클을 안만드는 것이어야 한다. edge (u,v)에서 u와 v를 find-set(x)해서 두개 값이 똑같으면 같은 set에 있다는 거니까 다른 값이 나와야 한다. 다르면 union한다.

성능
disjoint-set의 구조에 따라 성능 차이가 있다. union-by-rank와 path-compression을 이용하면 빠르다.
Edge수를 m, Vertex 수를 n이라 하면
1. set 초기화 Θ(n)
2. edge 정렬  Θ(m lg m),
3. find, equal, merge는 Θ(lg m), 이것을 모든 Edge에 대해 반복하므로 Θ(m lg m)이다.
m >= n-1이기 때문에 2,3 번이 1번을 지배. 따라서 Θ(m lg m)
최악의 경우 완전그래프일 경우 edge의 개수는 m=n(n-1)/2. 따라서 시간복잡도가 (n^2lg n)

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.


2. Prim algorithm 
마찬가지로 탐욕적인 방법.
set A는 언제나 하나의 tree이다.(Kruskal은 forest)
set A와 연결되는 light edge 구하기. set A와 나머지를 나누는 선을 긋고, 그 선을 지나는 최소 edge중 하나가 light edge.
root vertex에서 시작한다.

구현
Minimum spanning tree를 A라고 하자.
모든 노드를 우선순위큐에 넣고
최소 key를 가진 vertex를 꺼낸다. (처음에 초기화할 때 루트의 key가 0이고 나머지는 다 무한대로 설정해서 처음에 루트가 꺼내져서 A에 들어간다.) 꺼낸 vertex(u)의  인접 vertex(v) (큐에 아직 남아있는 것)만 탐색하여 v의 키값이 (u,v) edge의 weight 값보다 크다면 key값을 weight 값으로 변경한다. 그리고 부모노드를 u로 설정한다. 큐가 비워질 때까지 이 과정을 반복한다.

성능
큐에 vertex가 없을 때까지 while문 반복, |V|번. (V는 vertex수)
큐에서 최소값 뽑는 것이 O(lg V).
while 다 돌면 큐에서 모든 vertex를 뽑으니까 O(V lg V) ----------1번

그래프의 인접리스트의 총 edge 길이는 2|E| (undirected graph, E는 edge 수)
그래서 큐에서 vertex 뽑고 그 vertex의 인접리스트를 탐색하는 거 O(E).
탐색 과정에서 vertex가 큐에 있는지 확인하고 있으면 key값 변경하고, 부모노드 설정.
큐에 있는지 확인하는 것은 vertex에 bit하나를 할당하여 큐에 있는지 없는지 상태를 나타내면 큐를 다 뒤지지 않고도 상수시간에 큐에 존재여부를 확인 할 수 있다.
부모노드 설정도 상수시간.
그리고 key값 변경하는 것은 min-heap에서 Decrease-key랑 같은거다.(key값 변경하고 min-heap이 유지되도록 변경된 vertex의 트리에서의 위치를 찾는 것) O(lg V)이다.
따라서 인접리스트 탐색하면서 key값 변경하는 시간은 O(E lgV) ----------2번
1,2번에 의해 total time은 O(V lg V + E lg E) = O(E lg V)

Fibonacci heap을 통해 성능향상을 할 수 있다.

Greedy method를 사용해서 값을 구하면 이게 정말 optimal solution인지 확인해야 한다.

'공부 > 알고리즘' 카테고리의 다른 글

Single-Source Shortest Paths  (0) 2011/07/13
Minimum spanning tree (최소신장트리)  (0) 2011/07/13
Elementary Graph Algorithms  (0) 2011/07/13
Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09


Posted by skyjumps
공부/알고리즘2011/07/13 11:54


Graph basics

그래프는 vertex(node) set과 edge(link) set으로 구성되어 있다.

directed graph
directed graph는 방향이 있는 edge를 사용하는 그래프.
한 vertex가 어떤 edge의 끝점일 때 그 edge는 그 vertex와 incident하다고 한다. 
self-loops - 자기자신한테로 가는 edge.
edge는 vertex의 순서쌍으로 표시할 수 있다. (예 : E= {(1,2), (2,2)}, 숫자는 vertex)

undirected graph
방향이 없는 edge 사용
방향이 없으니까 Edge (u,v) 는 edge (v,u)하고 같다.
self-loops가 없다.
Adjacency - 두 vertex 사이에 edge가 있을 때 둘이 adjacent 하다고 한다.

Degree
out-degree 자기로부터 나가는 edge의 수
in-degree 자기로 들어오는 edge의 수.
한 노드의 degree는 out-degree + in-degree
undirected graph에서는 in, out degree가 없다. 그냥 한 vertex에 incident한 edge의 수를 degree라 한다.

Path
한 vertex서 다른 vertex까지 가는 길. edge를 지나는 vertex들의 집합으로 볼 수 있다.
path의 length는 path안에 있는 edge의 수.
한 vertex에서 다른 vertex까지의 path가 있을 때 두 vertex는 reachable하다라고 한다.

Simple path
같은 vertex를 두번 이상 지나지 않는 path.

Cycle
path의 시작 vertex와 끝 vertex가 같을 때.
사이클이 없으면 acyclic graph

Connected graph
undirected 그래프에서 임의로 2개 vertex를 선택하였을 때 path가 존재.

connected components
undirected connected graph을 모아논 graph

Strongly connected
directed graph에서 임의 두 vertex의 path가 있을 때

Strongly connected components
directed connected graph들을 모아논 graph

Complete graph
undirect graph의 임의 두 vertex가 adjacent할 때
edge 개수 : n(n-1)/2

Bipartite graph
undirected 그래프를 두개의 파티션을 나누는데, 각각의 파티션안에는 edge가 없고 서로의 파티션간에 edge가 있는 그래프. 

Forest
tree들의 모음
사이클이 없고, undirected graph

Tree
사이클 없고, connected한 undirected graph
사이클이 없으니까 두 vertex는 simple path가 하나밖에 없다.
edge 하나가 제거되면 graph는 disconnected가 된다.
edge 하나가 추가되면 graph는 사이클이 생긴다.
|E| = |V|-1

Dag
Directed Acyclic Graph

Handshaking lemma
모든 vertex들의 degree 합은 2*(edge 수). 왜냐하면 edge 하나가 vertex 2개의 degree를 만들기 때문.

Edge의 수
undirected graph
최대 |V|(|V|-1)/2. (완전그래프가 될 때)

directed graph
위에거에 곱하기 2에다가 self loop edge를 가질 수 있으므로 더하기 |V|. 계산하면 |V|^2이고 이는 최대로 가질 수 있는 edge 갯수이다.

그래프 구현방법

1. 행렬
vertex u, v에 edge가 있으면 행렬 M(u,v)의 값이 1, 없으면 0.
Θ(V^2) space, undirected graph이면 행렬이 main diagonal을 기준으로 symmetry하므로 Lower matrix만으로 충분.
2. 리스트
vertex별로 리스트 하나씩. adjacent한 vertex가 리스트의 노드가 된다.
Θ(V+E) space

그래프가 sparse 하면 행렬에 빈공간이 많으므로 리스트가 효율적, dense하면 행렬이 edge하나를 bit만으로 표현할 수 있으니 더 효율적.
모든 edge를 방문하고자 할 때 행렬은 존재하지 않는 edge도 방문한다. 리스트는 있는 edge만 방문한다.

edge에 값이 있는 weighted graph일 때는 행렬에 1대신에 weight값을 넣고, 리스트로 구현할 때는 각 노드에 weight 항목을 추가한다.

Transpose

main diagonal을 기준으로 대칭했을 때, 두 행렬이 같으면 transpose. 그래프로 봤을 땐 edge의 방향을 바꾸는 것. undirected graph는 바꿔도 변함이 없으므로 transpose이다.

Breadth-first-search

시작 vertex에서 거리가 가까운 노드부터 탐색.
탐색한 edge와 vetex들은 tree를 이룬다.
vertex들을 큐에 넣어 거리가 가까운 노드부터 탐색한다.
탐색여부는 색깔로 구분할 수 있다. 탐색안된것, 탐색중, 탐색완료.
모든 vertex는 최대 한번 탐색된다.
모든 edge는 최대 두번 탐색된다. 인접 vertex 찾아서 enqueue할 때, dequeue해서 인접vertex 찾을 때. 
수행시간 O(V+E), reachable 하지 않은 것이 있어서 Θ가 아님.

Depth-first-search

이것도 vetex에 색깔을 넣어 탐색여부를 알 수 있다. white는 탐색안한 vertex, gray는 탐색중인 vertex, black은 그 vertex의 모든 인접 vertex를 다 조사하고 끝난 vertex.

Parenthesis theorem
한 노드가 gray인 기간. 노드가 탐색이 시작되고 끝날 때까지의 기간.
자식이 끝나야 부모가 끝나기 때문에 시간간격이 부모가 자식을 포함하고, 겹쳐 지는 경우는 없다.

edge의 분류
tree edges
depth-first-forest(depth-first-search를 하면 트리들의 집합이 만들어진다)의 edge들
(u,v) edge에서 v가 white인 edge. 

back edges
depth first tree에서 자식에서 조상으로 가는 edge, self loop도 back edge.
(u,v) edge에서 v가 grey인 edge

Forward edges
조상에서 후손으로 가는 edge
(u,v) edge에서 v가 black인 edge (cross edge일수도 있다. u,v가 포함관계가 아닐 경우.)

cross edges 
다른 depth first tree에서 온 edge
 
undirected graph일 때, depth-first search하면 모든 edge는 tree edge이거나 back edge이다.
forward edge는 back edge가 되고(자식 노드에서 먼저 edge를 탐색하기 때문에)
cross edge는 tree edge가 된다. (unconnected 였는데 connected가 되기 때문)

running time : Θ(V+E), list로 구현했을 때.

스택을 사용한다.

Topological sort

그래프가 DAG(엣지방향이 있고 사이클이 없는 그래프)일 때, 모든 엣지를 왼쪽에서 오른쪽 방향으로 되도록 vertex를 일렬로 배열 할 수 있다.

출처 : homepages.ius.edu

 사이클이 있으면 불가능. no back edge. right에서 left로 가는 edge가 있기 때문이다.

 in-degree가 0인 vertex를 왼쪽부터, out-degree가 0인 것을 오른쪽부터 둔다.
Depth first search를 돌려서 finish time이 빠른 vertex부터 맨 오른쪽부터 놓는다.

 

'공부 > 알고리즘' 카테고리의 다른 글

Single-Source Shortest Paths  (0) 2011/07/13
Minimum spanning tree (최소신장트리)  (0) 2011/07/13
Elementary Graph Algorithms  (0) 2011/07/13
Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09


Posted by skyjumps
공부/알고리즘2011/07/11 23:10


Disjoint set
A,B 두 집합의 교집합이 공집합일 때, A와 B는 disjoint이다.

Collection
disjoint set들의 집합
collection의 각 set들은 representative member(대표 원소)를 가지고 있다.

Disjoint-set operations
make-set(x) - x를 set으로 만들고 disjoint sets에 추가.
union(x,y) - x를 포함하는 집합과 y를 포함하는 집합을 합침.
find-set(x) - x를 포함하는 집합의 representative member 찾기

union operation의 수는 최대가 make-set operation의 수 -1이다.

Disjoint-set의 활용
Computing connected components
연결된 컴포넌트 계산하기
 
출처 : en.wikipedia.org

그래프가 정적일 때는 Depth-first search로 해결.
하지만 동적일 때는 DFS가 비효율적이다. 새로 들어오면 다시 DFS해야 되니까.
disjoint-sets을 만들고 유지하는 것이 더 효율적. 
Vertex마다 set을 만들고 모든 edge를 체크해서 두 vertex가 같은 set에 없으면 union한다.

disjoint-set data structures 구현 방법
1. Linked-list representation
각각의 set들을 linked list로 표현 할 수 있다.
set 안의 멤버들은 list의 element가 된다.
첫번째 element가 representative이다.
모든 element가 representative를 가리키고 있다.

make-set(x)
Θ(1)
head와 tail 포인터를 자기자신을 가리키게 하고, representative를 가리키는 포인터도 자기자신을 가리킨다.

Find-set(x)
Θ(1)
x의 representative 포인터를 참조하면 한번에 찾을 수 있다.


Union(x,y)
두 linked-list를 붙인다.
앞의 리스트의 tail이 뒤에 붙는 리스트의 마지막을 가리키게 한다.
뒤에 붙는 리스트의 elements들의 representative 포인터를 앞 리스트의 representative를 가리키게 한다.
Θ(m2) 시간이 걸린다. 뒤에 붙는 리스트의 모든 elements들의 representative 포인터를 바꿔줘야 하기 때문.

전체시간
단순하게 구현한 union을 사용하면
O(n^2) (make-set n번, union 최대 n-1번)
union할 때 짧은 리스트를 뒤에 붙이면 시간을 줄일 수 있다.
O(m + n lg n) (m은 총 operation 갯수. n은 총 노드 갯수)

2. Forest representation
각각의 set을 트리로 나타냄.
각각의 member는 자신의 부모를 가리킴
트리의 루트는 representative임.

make-set(x)
부모포인터를 자신을 가리키게 함.

find-set(x)
부모포인터가 자신이면 루트이므로 바로 x를 리턴.
아니면 루트에 도착할 때까지 부모를 따라 올라간다.

running time 개선 방법
1. Union by rank
트리의 높이정보인 rank를 이용해서 높이가 짧은 트리를 긴 트리에다가 붙인다.
union 시간 단축

2. Path compression
find-set할 때 모든 노드가 루트를 가리키게 한다. 한번에 representative를 찾도록.
find-set 시간 단축
 
O(m α(n)), α는 보통 4이하인 상수. 

참고사이트
http://aronze.egloos.com/214354
http://pixelenvy.ca/wa/uf_details.html 

'공부 > 알고리즘' 카테고리의 다른 글

Minimum spanning tree (최소신장트리)  (0) 2011/07/13
Elementary Graph Algorithms  (0) 2011/07/13
Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09
11장 Hash Table  (0) 2011/07/08


Posted by skyjumps
공부/알고리즘2011/07/11 21:22


greedy algorithms은 그 상황에서 가장 최선의 선택을 한다. 그 선택이 optimal solution으로 되기를 바란다.
subproblems가 풀리기 전에 선택을 한다.
단지 하나의 subproblem만 생성된다.

Dynamic programming의 경우에는 subproblems를 푼 후에 선택을 한다는 점이 Greedy Algorithms 하고 비교된다.

Huffman Code
prefix code
Prefix가 없는 코드. 한 코드는 다른 코드의 prefix가 되면 안된다. 포함되면 안된다. 포함되면 해석할 때 여러개로 해석될 수 있다. 
코드로 트리를 만들었을 때 중간노드에 코드가 없고 leaf 노드에만 있으면 prefix code이다. 그리고 full binary tree(모든 노드가 자식이 둘)가 최적의 코드이다.

huffman code 만들기
min heap을 만들어서 빈도수가 작은 수 2개씩 뽑아 합쳐서 합친 수를 두개의 부모노드로 만들고 합친수를 힙에 넣어 다 합쳐서 한개만 남을 때까지 반복한다. 
min heap 만들기 O(n), n-1번 합치기. 작은 수 뽑을 때마다 min heapify O(lg n). 따라서 running time은 O(n lg n)

 

'공부 > 알고리즘' 카테고리의 다른 글

Elementary Graph Algorithms  (0) 2011/07/13
Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09
11장 Hash Table  (0) 2011/07/08
8장 Sorting in Linear Time  (0) 2011/07/03


Posted by skyjumps
공부/알고리즘2011/07/09 22:49


Dynamic programming은 문제를 subproblems로 쪼개서 문제를 푸는 방식이다.

subproblem들이 독립적이면 divide-and-conquer 방식으로 풀 수 있고
독립적이지 않으면 dynamic programming을 한다.
독립적이지 않은 것의 의미는 sub problems가 subsub problems를 공유하는 것이다.
dynamic programming 알고리즘은 같은문제를 또 풀지 않기 위해서 subproblem을 한번만 풀고, 그 결과를 table에 저장한다. 그리고 나중에 필요할 때, 테이블을 참조해서 값을 가져온다.

 Dynamic programming은 최적화 문제(optimization problems)를 푸는데 이용된다.
솔루션은 여러개이지만 그중에 최적화 된 값(최소값 or 최대값)을 가진 솔루션은 하나다. Dynamic programming으로 그 솔루션을 찾는다.

문제 푸는 4가지 단계 
1. optimal substructure를 구한다.
2. recursive solution을 구한다. 
3. optimal solution의 값을 bottom-up 방식으로 계산한다.
4. 계산된 정보로 optimal solution을 구한다.

optimal solution의 sub solution도 optimal solution이다.

overlapping subproblems
순환적인 알고리즘이 같은 문제를 계속 반복하여 방문할 때.

참고 
cs.kangwon.ac.kr/~ysmoon/courses/2011_1/alg/06.pdf

'공부 > 알고리즘' 카테고리의 다른 글

Data Structures for Disjoint Sets  (0) 2011/07/11
Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09
11장 Hash Table  (0) 2011/07/08
8장 Sorting in Linear Time  (0) 2011/07/03
7장 Quicksort  (0) 2011/07/03


Posted by skyjumps
공부/알고리즘2011/07/08 12:00


1. Direct-address tables
키가 n개 있으면 테이블의 크기도 n개
키를 테이블에서 찾는 것, element를 삽입하는 것, 삭제하는 것 모두 running time O(1)
전체 키에서 실제 사용되는 키가 적을 경우 공간 소비가 심하다.
O(1)를 유지시키면서 공간을 줄일 수 있는 방법이 없을까?

2. Hash tables
Hashing
키를 해쉬함수에 넣어서 나온 값으로 hash table에 들어갈 위치를 정하는 것.
Collision
두 키의 Hashing 결과 같은 위치를 가질 때
테이블의 크기가 키크기보다 작기 때문에 collision을 피할 수 없다. collision을 최소화하도록 한다.
어떻게? Hashing function을 잘 만들기.

Collision이 발생하였을 때 해결하는 방법

i) Channing
두 키가 해시테이블에서 같은 위치(collision)일 경우 리스트에 element를 추가한다.
리스트가 길 경우 찾는 시간이 늘어난다. 

load factor
해쉬테이블의 성능 분석 척도
α = n/m (엘리먼트 갯수/슬롯의 갯수)
worst case
모든 키가 테이블의 한 슬롯에만 들어갈 때.

ii) Open addressing
모든 값들이 해시테이블 내에 저장된다. 리스트가 없고 테이블 밖에 element가 저장되지 않는다.
element를 찾을때까지 table slot을 조사한다.
load factor가 1을 넘지 않는다.
포인터 안써도 되고, 리스트일때 사용되지 않던 메모리 공간을 slot으로 이용할 수 있다.

probe : 삽입할 때 slot이 비어있는지 아닌지 확인하는 것.
probe sequence에 따라 slot을 조사한다.

Deletion : search할 때 멈추는 것을 막기 위해서 비워두지 않고 'Deleted' 같은 특별한 표시를 해놓는다.

probing 방법
i) Linear probing
h(k')에 값이 있으면 (h(k') + i) mod m 을 조사(i는 0,1,2,3, ... m-1)
단점
primary clustering : 채워져 있는 slot들이 한곳에 모일 가능성이 높다. i번째까지 가득찬 slots이 있을 때 다음 slot이 가득찰 확률은 (i+1)/m이기 때문에. 평균 search 시간이 늘어난다.

ii) Quadratic probing
h(k, i) = (h'(k) + c1*i + c2*i^2) mod m을 이용
단점
linear probing의 primary clustering은 발생하지 않지만
secondary clustering이 발생. 즉 두 키가 같은 해시값을 가지면 probe하는 위치가 같다.
linear probing처럼 처음 probe 하는 위치가 모든 probing sequence를 결정한다.

iii) Double hashing
h(k,i) = (h1(k) + i*h2(k)) mod m
h1에 의해 같은 값을 갖게 되더라도 h2에 의해 다른 값을 가져서 다른 해쉬값을 가질 수 있다.
따라서 h2가 모든 테이블의 slot를 탐색할 수 있도록 잘 설계되어야 한다.
예를 들어 h1(k1) = 0 이고 h2(k1) = 2일 경우 홀수 slot만 간다.

3. Hash functions
각각의 키가 hash table의 slot에 고르게 들어가도록 hash function을 만든다.
The division method
key k를 m으로 나눈 나머지값이 해쉬값이 된다.
i) m이 2^p 일때,
h(k)의 값은 k의 뒷부분 p bits이다.
ii) m이 2^p-1 일 때,
k는 2^p진법으로 표현 가능하다.
k의 자리수만 바꾼 값들은 k와 해시값이 같다. (각 자리를 modular한 합이 같기 때문에)

좋은 m값
2의 지수승과 가깝지 않은 소수

The multiplication method
key값에 소수인 A를 곱해서 나온 수에서 소수부분에 m을 곱하여 나온 수에서 정수부분이 헤시값이 된다.


'공부 > 알고리즘' 카테고리의 다른 글

Greedy Algorithms  (0) 2011/07/11
Dynamic Programming  (0) 2011/07/09
11장 Hash Table  (0) 2011/07/08
8장 Sorting in Linear Time  (0) 2011/07/03
7장 Quicksort  (0) 2011/07/03
Heapsort  (1) 2011/06/30


Posted by skyjumps
공부/알고리즘2011/07/03 18:57


Lower bounds for sorting
worst case에서 nlgn보다 빠른 comparison sort(원소의 순서를 정할 때 비교만 사용하는 정렬)가 없다.
참고) heap sort랑 merge sort가 worst case에서 O(nlgn)

The decision-tree model

출처 : http://serverbob.3x.ro/IA/DDU0048.html


모든 원소가 구별되는 값(distinct)이라면
input의 모든 원소를 ai <= aj 로 표현할 수 있다.

comparison sort를 decision trees로 볼 수 있다.
내부 노드 (i,j)는 ai<=aj 임을 의미한다.
각각의 잎노드는 input 원소의 순열(permutation)이다.
 
decision tree의 루트부터 leaf까지의 path는 sorting algorithm의 수행하고 같다.
가장 긴 path의 길이는 worst case를 의미한다.
즉, worst case는 트리의 높이와 같다.

모든 comparison sort algorithm은 worst case일 때 Ω(nlgn) 만큼 비교한다.
n! <= 2^h      (n!은 총 잎의 갯수, h는 트리의 높이)
h>= lg(n!)  
h = 
Ω(nlgn)   ( 왜냐하면 lg(n!) = Θ(nlgn) )

Counting sort
n개의 입력원소가 정수이고 범위가 0부터 k(k<=n)일 때라고 가정한다.
"입력원소 x는 x보다 작은 원소의 수가 i-1개 라면 정렬후에는 i에 위치해야 한다." 라는 원리
집합 A의 원소의 범위가 0~k일 때, 집합 A의 원소의 값이 집합 C의 i와 같으면 Ci값에 1을 추가한다. 집합 C는 A의 원소의 범위가 0~k이므로 k+1크기의 배열이면 된다. C는 A원소의 횟수를 저장한 집합이 된다. C'는 C의 누적합이다. (C'[i] = C[0] + ... + C[i]) 
이 C'를 이용해서 A를 정렬을 할 수 있다. C'i의 값이 a라고 하면 이는 i보다 작거나 같은 값이 집합 A에 a개 있다는 소리다. 그래서 i가 들어갈 자리는 a가 될수 있다.
Stable(입력값이 같은 값이 있을 때 그 순서를 결과값에도 유지 시키는 것)하게 하기 위해서 A의 맨 끝에 있는 원소부터 C'를 이용해서 위치를 찾는다.
수행시간
Θ(n+k)
Θ(k) : C를 0으로 초기화
Θ(n) : A를 스캔하면서 C에 카운터를 증가.
Θ(k) : C를 스캔해서 C' 구하기
Θ(n) : C'과 A를 이용해서 정렬된 집합 B를 구하기. B[C'[A[j]] <- A[j]
k가 O(n)이면 수행시간은 Θ(n)!

Radix sort
n 자리수 숫자들이 있을 때 각 자리수끼리 정렬.
1) 최대유효숫자 -> 최소유효숫자
최대유효숫자부터 정렬. 이전 그룹을 유지하면서 정렬을 해줘야 바르게 정렬이 된다. 
2) 최소유효숫자 -> 최대유효숫자
최소유효숫자부터 정렬.

정렬할 때 stable한 sort 알고리즘을 쓴다.

각 자리수의 범위가 k일 때 d 자리인 n개의 수를 radix sort한 수행시간은?
k가 안크면 counting sort 사용하면 된다.
Θ(d(n+k))           (n+k을 d번한거)
d가 상수고, k = O(n)일 때 radix sort는 linear한 소트이다.

b-bit인 수 n개를, r<=b일 때, r개씩 자르고 radix-sort로 정렬했을 때 수행시간은?
Θ((b/r)(n+2^r)) time.
b/r은 d이고 2^r은 k.
예를 들면
32bit를 8bit씩 4개로 나눠서 4자리씩 radix sort.
r=8, b=32, k는 8bit로 0부터 2^8-1까지, 0부터 255까지 표현할 수 있으니 256개 필요하고, b/r=4, n+2^r = n+256.

Θ((b/r)(n+2^r))을 최소화하는 r
1. b < floor(lgn) 일 때
r<=b 이므로 (n+2^r)은 Θ(n)
그래서 r=b일때, (b/b)(n+2^b) = Θ(n) 

2. b >= floor(lg n) 일 때
r=floor(lg n)을 선택는 것이 최적이다. (b/lgn)(n+2^(lgn) = (b/lgn)(2n) = 
Θ(bn/lg n)
r이 floor(lg n)보다 커지면 2^r은 기하급수적으로 증가하고
r이 floor(lg n)보다 작아지면 b/r은 커지고 n+2^r 은
Θ(n)이 된다.

따라서 1,2 종합해보면 r=lg n씩 자를 때가 최적이다.

Radix sort가 퀵소트보다 좋을까?
Radix sort는
Θ(n)이고 퀵소트
는 Θ(nlgn) 이니 radix sort가 더 좋을 것 같다.
퀵소트보다 각단계(pass)의 횟수가 작을 수가 있지만 Θ(n)에 감춰진 상수값이 클 수가 있다. 즉, Radix sort의 각각의 pass에서 오래 걸릴 수 있다. 그리고 퀵소트는 하드웨어 캐쉬를 더 효과적으로 사용해서 더 빨리 처리된다. 그리고 Radix는 sort in place가 아니다. 정렬하면서 중간값을 저장할 공간이 더 필요하다. 이런점에서 메모리가 좋다면, in-place 알고리즘인 퀵소트가 빠르다.
퀵소트와 캐쉬 locality를 설명한 글 참고
http://soyoja.tistory.com/248#comment1449755



 

'공부 > 알고리즘' 카테고리의 다른 글

Dynamic Programming  (0) 2011/07/09
11장 Hash Table  (0) 2011/07/08
8장 Sorting in Linear Time  (0) 2011/07/03
7장 Quicksort  (0) 2011/07/03
Heapsort  (1) 2011/06/30
4 Recursion  (0) 2011/06/28


Posted by skyjumps
공부/알고리즘2011/07/03 01:08



Divide-and-Conquer

(1) 피봇을 정하고 (2)피봇보다 작은 수 큰 수를 나누고 나눠진 집합에 대해 다시 (1),(2)번을 반복하면 정렬이 되는 그러한 정렬방식이다.

Partition
피봇을 정하고 피봇보다 작은 수 큰 수를 나누는 과정이다.
time은 Θ(n) 이다. 리스트 한번만 읽으면 되니까.

Balanced partitioning
파티션이 반반씩 나눠질때, T(n) <= 2T(n/2) +  Θ(n) = O(nlgn)
퀵소트에서 피봇이 잘 뽑이면 이러한 결과가 나온다.

Unbalanced partitioning
피벗이 가장 작은 수나 가장 큰 수가 뽑혔을때
원소가 n개 있으면 파티션이 하나, n-1개로 나눠져서
최악의 경우가 된다. 파티션을 많이 해야 한다.
최악의 경우가 insertion sort랑 비슷하다.
T(n) = T(n-1) +  Θ(n) 이므로 계산하면 Θ(n^2)가 된다.

worst cast 분석
unbalanced partitioning이 최악의 경우임을 보증하는가?
증명 여기 사이트 formal worst case analysis 참고

Average-case analysis
Zij = {zi, zi+1 ... zj} 인 array를 퀵소트한다고 하자.

X를 임의의 quicksort 실행에서 전체 비교횟수인 확률변수로 보면
quicksort의 평균수행시간은 O(n+E[X]). (n은 스캐닝 + etc)

각각 파티션마다의 비교횟수를 생각하지말고 전체적으로 비교횟수를 보자.
그러면 array에서 임의의 2개 원소는 많아야 한번 비교한다. 2개중 하나가 피봇일 때 한번 비교 하는 것이다. 그리고 피봇은 다음번 단계 이후부터는 비교대상에서 제외된다. 그래서 임의의 두개 원소는 기껏해야 한번 비교가 된다.
 
그럼 이 식들이 이해가 되었음.


계산과정은 생략하고 
계산하면 O(nlgn)이 나온다. 평균수행시간이 된다.

Randomized quicksort
피벗을 랜덤으로 뽑는다.
average-case를 보장하도록 한다.
input의 형태에 관계없이 항상 uniform하게 quicksort를 할 수 있다. 

'공부 > 알고리즘' 카테고리의 다른 글

11장 Hash Table  (0) 2011/07/08
8장 Sorting in Linear Time  (0) 2011/07/03
7장 Quicksort  (0) 2011/07/03
Heapsort  (1) 2011/06/30
4 Recursion  (0) 2011/06/28
3장 Growth of Funtions  (0) 2011/06/24


Posted by skyjumps
공부/알고리즘2011/06/30 18:58


merge sort와 같이 running time이 O(nlgn)이다.
insertion sort와 같이 sorts in place이다.

Heaps
complete binary tree이다. 높이가 k일 때 k-1까지는 노드가 모두 채워져 있고 마지막 레벨 k부터는 왼쪽부터 오른쪽으로 노드가 채워지는 tree.

참고) full binary tree : 각 레벨에 노드가 꽉 차있는 트리

힙의 종류
max-heaps 과 min-heaps가 있다.

max-heap
부모 노드 값이 항상 같거나 크다. A[Parent(i)] >= A[i]
루트 노드는 최대값이다.
subtree의 루트노드는 그 subtree의 최대값이다.

min-heap
부모노드값이 항상 작거나 같다.
루트노드는 최소값이다.

힙은 배열에 저장할 수 있다.
배열 A[1]에 루트노드가 저장되고 A[2]부터 레벨순으로 왼쪽에서 오른쪽으로 차례대로 배열에 저장된다.
배열에서 노드의 부모값과 자식값을 알 수 있는 방법
Parent(i) = floor(i/2)
left(i) = 2i
right(i) = 2i+1

heap의 높이
각 레벨의 노드 갯수 ; 1, 2, 4, 8 ..... 2^(n-1)
k레벨일 때까지 등비수열 합을 해주면 총 노드 갯수 n = 2^k -1
k = lg(n+1) 따라서 높이 h = θ(lgn)

Maintaining the heap property
Max-Heapify
노드의 왼쪽 오른쪽 서브트리가 max heap인데 정작 노드는 자식노드보다 작을 때 부모는 자식보다 크다는 max heap 속성을 어기므로 만족할때까지 밑으로 내린다. 내려가는 횟수는 아무리 많아도 트리의 높이보다 작다. O(h) = O(lg n)
 
Building a heap
자식을 가진 맨 아래 오른쪽에 있는 노드부터 시작해서 Max-heapify 해준다. (밑에서부터 힙이 이루어지도록 한다.) 다음 max-heapify 해줄 노드 방향은 오른쪽 -> 왼쪽, 아래 -> 위다.
위에서부터 밑으로 내려가는 방식은 힙이라는 것을 보증하지 못하기 때문에 힙이 안만들어 질 수도 있다.

Running time
Upper bound는 Max-HEAPIFY가 O(lg n)이므로 노드 O(n)개에 대해 수행하면 O(nlg n) 이 된다.
Thighter bound를 살펴보면 트리의 아래쪽에 있는 노드는 lg n보다 적은 시간이 들고 이러한 아래에 있는 노드들이 많으므로 tighter bound는 Upper bound 보다 작다. 계산하면 O(n)이 된다. linear time으로 기존의 배열을 힙으로 만들 수 있다.

max힙에서 n번 최대값을 뽑는 비용은? (Heap sort)
O(nlgn)
루트가 최대값이므로 그 값을 뽑고 루트 자리에 가장 낮은 노드를 넣어서 max heapify 한다. 그래서 n-1번 동안 O(lgn) 이므로 O(nlgn)

Priority queue
우선순위 개념을 큐에 도입한 자료 구조. 데이터가 우선순위를 가지고 있고 우선 순위가 높은 데이터가 먼저 나가게 된다. 힙으로 구현할 수 있다.
최대값을 읽는 것은 O(1)이고 읽고 지우는 것은 지우고 나서 Max heapify가 사용되므로 O(lg n)
노드의 키값을 증가시킬때, 바꾼 값이 힙을 깨뜨릴 가능성이 있다. 힙을 유지하기 위해 위로 올라가면서 자기자리를 찾는다. 기껏 올라가봤자 트리 높이 보다 작다. O(lg n)
노드를 삽입할 때는 힙의 맨 마지막에 넣고 힙을 유지하기 위해 노드를 위로 올리면서 자기자리를 찾는다. 이것도 O(lg n)

'공부 > 알고리즘' 카테고리의 다른 글

8장 Sorting in Linear Time  (0) 2011/07/03
7장 Quicksort  (0) 2011/07/03
Heapsort  (1) 2011/06/30
4 Recursion  (0) 2011/06/28
3장 Growth of Funtions  (0) 2011/06/24
2장 insertion sort, merge sort, binary search, selection sort, bubble sort  (1) 2011/06/23


Posted by skyjumps