가중그래프(Weighted Graph) : 각 간선이 무게(weight)라 부르는 수치값을 가지는 그래프
무게가 될 수 있는 것들은 거리,비용,시간 등 다양하다.
가중그래프의 예시
📢 최소신장트리
신장 부그래프(Spanning Subgraph) : 그래프 G의 모든 정점들을 포함하는 부그래프
신장트리(Spanning Tree) : (자유)트리인 신장 부그래프
최소신장트리(MST, Minimum Spanning Tree) : 가중그래프의 총 간선 무게가 최소인 신장트리
응용분야
👉 교통망, 통신망 등등
최소신장트리 예시 ( 파란색 경로가 추가될 경우 Cycle 생성됨 X )
최소신장트리 속성
👉 1. 싸이클속성 👉 2. 분할 속성
이 두개의 속성은 알고리즘의 정확성 검증에 이용한다.
📢 싸이클 속성
f를 e로 대체하면 더 좋은 신장트리를 얻는다.
싸이클 속성
👉 T를 가중그래프 G의 최소신장트리라 가정하자. 👉 e를 T에 존재하지 않는 G의 간선으로, C를 e를 T에 추가하여 형성된 싸이클로 가정하자. 👉 그러면 C의 모든 간선 f에 대해, weight(f) <= weight(e) 이다.
증명
👉 모순법 : 만약 weight(f) > weight(e)라면, f를 e로 대체함으로써 무게가 더 작은 신장트리를 얻을 수 있기 때문
📢 분할 속성
분할 속성
👉 G의 정점들을 두 개의 부분집합 U와 V로 분할한다고 하자. 👉 e를 분할을 가로지르는 최소 무게의 간선이라고 하자. 👉 간선 e를 포함하는 G의 최소신장트리가 반드리 존재한다.
증명
👉 T를 G의 MST라 하자. 👉 만약 T가 e를 포함하지 않는다면, e를 T에 추가하여 형성된 싸이클 C를 구성하는 간선들 가운데 분할을 가로지르는 간선 f가 존재할 것이다. 👉 싸이클 속성에 의해, weight(f) <= weight(e) 👉 그러므로, weight(f) == weight(e) 👉 f를 e로 대체하면 또 하나의 MST를 얻을 수 있다.
📢 최소신장트리 알고리즘
크게 3가지 알고리즘이 존재한다.
👉 1. Prim-Jarnik 알고리즘 ( 많이 씀 ) 👉 2. Kruskal 알고리즘 ( 많이 씀 ) 👉 Baruvka 알고리즘 ( 1번 + 2번 느낌 )
📢 Prim-Jarnik 알고리즘
탐욕(Greedy) 알고리즘의 일종
대상 : 단순 연결 무방향 그래프
아이디어
👉 임의의 정점 s를 택하여, s로부터 시작해서, 정점들을 (가상의)배낭에 넣어가며 배낭 안에서 MST T를 키워 나감 👉 s는 T의 루트(root)가 될 것이다. 👉 각 정점 v에 라벨 d(v)를 정의 = d(v)는 배낭 안에 정점과 배낭 밖 정점을 연결하는 간선의 weight 👉 반복의 각 회전에서 : 배낭 밖 정점들 가운데 최소 d(z) 라벨을 가진 정점 z를 배낭에 넣고, z에 인접한 정점들의 라벨을 갱신한다.
Alg PrimJarnikMST(G)
input a simple connected weighted graph G with n vertexs and m edges
output an MST T for G
for each v ∈ G.vertexs()
d(v) <- ∞ // 여기서, d(v)는 각 정점들의 거리
p(v) <- ∅ // 여기서, p(v)는 각 정점들의 MST로 이뤄지기위한 직계 부모 정점 정보
s <- a vertex of G
d(s) <- 0
Q <- a priority queue containing all the vertexs of G using d labels as keys
while(!(Q.isEmpty()) // 우선순위 큐를 비울 때까지 반복인데, 반복 작업은, 배낭(MST)에 정정을 하나씩 넓혀가는 것
u <- Q.removeMin() // 우선순위 큐에 들어가있는, 가장 거리 d 가 작은 정점 반환 u
for each e ∈ G.incidentEdges(u) // 정점 u에 부착된 간선 전부를 본다.
z <- G.opposite(u,e) // 정점 u와 이어진 간선 e를 통한 반대편 정점을 z라 한다.
if((z ∈ Q) & (w(u,z) < d(z))) // 정점 z가 우선순위 큐에 있는 것이고, 즉 아직 방문 안한 정점이고, 정점 u를 거쳐 정점 z로 가는 거리가, 아직 현재 정점 z거리보다 적으면
d(z) <- w(u,z) // 정점 z의 거리를 업데이트한다.
p(z) <- e // 그리고, 정점 z의 부모간선을 e로 업데이트한다.
Q.replaceKey(z,w(u,z)) // 이렇게, 정점 z의 거리(d)가 우선순위가 바꼈을 수도 있으니, 우선순위큐 재배치를 진행한다.
추가설명
👉 (가상의)배낭 밖의 정점들을 우선순위 큐에 저장 : 키(거리)-원소(정점정보) 👉 각 정점 v에 세 개의 라벨을 저장한다.
1. 거리(distance) : d(v) 2. 위치자(locator) : 우선순위 큐에서의 v의 위치 3. 부모(parent) : p(v), MST에서 v의 부모를 향한 간선
ㅌPrim-Jarnik 알고리즘 예시
알고리즘 분석
👉 라벨 작업 : 점정 z의 거리, 부모, 위치자 라벨을 O(deg(z))시간 읽고 쓴다. 라벨을 읽고 쓰는데 O(1)시간 소요 👉 우선순위 큐( 힙으로 구현할 경우 ) 작업
1. 각 정점은 우선순위 큐에 한번 삽입되고 한번 삭제 : 삽입과 삭제에 각각 O(log(N))시간 소요 2. 우선순위 큐 내의 정점 w의 키는 최대 deg(w)번 변경 : 각 키 변경에 O(log(N))시간 소요 (힙 이니깐)
👉 그래프가 인접리스트 구조로 표현되어 있다면, Prim-Jarnik 알고리즘은 O((N+M)log(N))시간에 수행한다. 👉 단순 연결그래프에서 N = O(M)이므로, 총 실행시간 : O(Mlog(N))
📢 Kruskal 알고리즘
탐욕(Greedy) 알고리즘
알고리즘을 위한 초기 작업
👉 모든 정점을 각각의 독자적인 (실제의)배낭에 넣는다. 👉 배낭 밖 간선들을 우선순위 큐에 저장한다. = 키(무게)-원소(간선) 👉 비어 있는 MST T를 초기화
반복의 각 회전에서 : 두 개의 다른 배낭 속에 양끝점을 가진 최소 무게의 간선을 MST T에 포함하고 두 배낭을 하나로 합친다.
반복이 완료되면 : MST T를 포함하는 한 개의 배낭만 남게 될 것이다.
Alg KruskalMST(G)
input a simple connected weighted graph G with n vertexs and m edges
output an MST T for G
for each v ∈ G.vertexs()
define a Sack(v) <- {v} // Sack은 배낭을 의미, 이것은 실제 구현에서는 Parent(v)로 제어하면 편하다.
Q <- a priority queue containnig all the edges of G using weights as keys
T <- ∅
while(T has fewer than n - 1 edges)
(u,v) <- Q.removeMin()
if(Sack(u) ≠ Sack(v))
Add edge(u,v) to T
Merge Sack(u)andSack(v)
return T
아Kruskal 알고리즘 예시
알고리즘 분석
👉 우선순위 큐 초기화 작업
힙을 사용하여 우선순위 큐 Q를 구현하면, 반복적인 삽입 방식에 의해서는 O(Mlog(M))시간에, 상항식 힙 생성 방식에 의해서는O(M) 시간에 Q 생성이 가능하다.
👉 반복의 각 회전에서는
최소 무게의 간선을 O(log(M))시간에 삭제 가능 = 여기서, G가 단순그래프이므로, O(log(M)) = O(log(N)) 각 배낭을 위한 분리집합을 리스트로 구현하면, find(u) ≠ find(v) 검사에 O(1) 시간 ( 또는 parent 배열을 이용 ! ) 두 개의 배낭 Sack(u), Sack(v)를 합치는데 O(min( |Sack(u)|, |Sack(v)| )) 시간 소요 ( 더 작은 배낭을 옮김 )
👉 총 반복 회수 : (최악의 경우) M번 👉 그러므로, Kruskal 알고리즘은O((N + M)log(N)) 시간에 수행 👉 G가 단순 연결그래프인 경우 N = O(M)이므로, 실행시간은 O(Mlog(N)) 이다.
📢 MST 알고리즘 비교
알고리즘
주요전략
수행시간
외부 데이터구조
Prim-Jarnik
탐욕
O(Mlog(N))
정점들을 저장하기 위한 우선순위 큐
Kruskal
탐욕
O(Mlog(N))
1. 간선들을 저장하기 위한 우선순위 큐 2. 배낭들을 구현하기 위한 분리집합(리스트로 구현가능) or 각 정점에 대해 부모정점(Parent배열)배열을 이용하는 방법
동적프로래밍(DP, Dynamic Programming) : 알고리즘 설계의 일반적 기법 중 하나
언뜻 보기에 많은 시간( 심지어 지수 시간 )이 소요될 것 같은 문제에 주로 적용한다.
적용의 조건은 :
👉 부문제 단순성(Simple Subproblems) : 부문제들이 j,k,l,m 등과 같은 몇 개의 변수로 정의 될 수 있는 경우 👉 부문제 최적성(Optimality Subproblems) : 전체 최적치가 최적의 부문제들에 의해 정의될 수 있는 경우 👉 부문제 중복성(Overlap Subproblems) : 부문제들이 독립적이 아니라 상호 겹쳐질 경우 ( 즉, 상향식으로 구축 )
대표적 예시
👉 피보나치 수(Fibonacci progression)에서 N-번째 수 찾기 👉 그래프의 이행적폐쇄 계산하기
동적프로그래밍 vs 분할통치법
공통점
👉 알고리즘 설계기법의 일종 👉 문제공간 : 원점-목표점 구조 ( 원점 : 문제의 초기 또는 기초지점 / 목표점 : 최종해가 요구되는 지점 )
차이점
👉 문제해결 진행 방향
동적프로그래밍(단방향) : 원점 -> 목표점 분할통치법(양방향) : 목표점 -> 원점 -> 목표점 ( 단, 해를 구하기 위한 연산을 진행, 방향은 원점->목표점 )
성능
👉 동적프로그래밍 : 단방향 특성때문에 종종 효율적 👉 분할통치법 : 분할 회수(보통 2분할을 한다.) , 중복연산 수행 회수에 따라 다름
이름은 "동적"프로그래밍이지만, 실제로 우리가 아는 "동적", 그때그때 사용하는 그런 의미는 아니다. 하나 구한 것은, 다를 때, 사용하는 의미일 뿐이고, 이러한 기법의 이름을 지은 사람이 그냥 "동적프로그래밍"이라 작명한 것 일 뿐이다. 오해하지말자.
📢 동적프로그래밍 예시
N-번째 피보나치 수 찾기 : 피보나치 수열(Fibonacci Progression)은 i = 0,1에 대해 f(i) = 1이며, i >= 2 에 대해 f(i) = f(i-1) + f(i-2)인 수열이다.
👉 M <= N(N-1) 이다. ( 무방향그래프에선 M <= (N(N-1)/2 였다. ) ( 여기서 M = 간선 수, N = 정점 수 이다. )
진입간선들(in-edges)과 진출간선들(out-edges)을 각각 별도의 인접리스트로 보관한다면, 진입간선들의 집합과 진출간선들의 집합을 각각의 크기에 비례한 시간에 조사 가능하다.
방향 그래프의 예시위에 그래프 기준으로, in-edges, out-edges를 표현하면 이런느낌
📢 방향 DFS
간선들을 주어진 방향만을 따라 순회하도록 하면, DFS 및 BFS 순회 알고리즘들을 방향그래프에 특화 가능하다.
방향 DFS 알고리즘에서 네 종류의 간선이 발생한다.
👉 트리간선(tree edges) : 트리에서, DFS경로에 해당하는 간선 👉 후향간선(back edges) : 트리에서 나의 조상방향으로 그려질 간선 👉 전향간선(forward edges) : 트리에서 나의 자식이 아닌, 더 아래 자식 정점의 경우 그려질 간선 👉 교차간선(cross edges) : 같은 레벨이나 하위레벨 정점끼리의 연결 간선
정점 s에서 출발하는 방향 DFS 👉 s로부터 도달 가능한 정점들을 결정한다.
위에 그래프를 통해 그려지는 DFS tree
도달 가능성이란 ?
👉 방향그래프 G의 두 정점 v와 u에 대해, 만약 G에 v에서 u로의 방향 경로가 존재한다면, "v는 u에 도달한다" 또는 "u는 v로부터 도달 가능하다" 를 의미한다. 👉 s를 루트로 하는 DFS 트리 : s로부터 방향경로를 통해 도달 가능한 정점들을 표시한 것
그래프 G에서 어떤 정점 s에서 "도달가능한" 예시
📢 강연결성
방향그래프 G의 어느 두 정점 u와 v에 대해서나 u는 v에 도달하며 v는 u에 도달하면
👉 G를 강연결(strongly connected)이라고 말한다. 즉, 어느 정점에서든지 다른 모든 정점에 도달 가능하다.
이런 방향그래프가 있다 가정하자.
강연결 검사 알고리즘
👉 1. 그래프 G의 임의의 정점 v를 선택한다. 👉 2. 그래프 G의 v로부터 DFS를 수행한다. ( 방문되지 않은 정점 w가 있다면, False를 반환한다. ) 👉 3. 그래프 G의 간선들을 모두 역행시킨 그래프 G` 를 얻는다. 👉 4. G`의 v로부터 DFS를 수행한다. ( 방문되지 않은 정점 w가 있다면, False를 반환. 그렇지 않으면, True 반환)
실행시간 = O(N + M)
그래프 G와 G의 역행방향인 G` 에 대해 DFS 실행한 결과 ( 두 경우 모두 모든 정점을 전부 방문한 것을 확인 )
강연결요소
👉 방향그래프서 각 정점으로 다른 모든 정점으로 도달할 수 있는 최대의 부 그래프 👉 DFS를 사용하여 O(N + M)시간에 계산 가능하다.
강연결요소의 예시. ( 방향그래프에 싸이클 집합을 찾아보면 된다. ), 위에 예제는 강연결요소가 2개
📢 이행적폐쇄
주어진 방향그래프 G에 대해, 그래프 G의 이행적폐쇄(Transitive Closure)는 다음을 만족하는 방향그래프 G*
👉 G* 는 G와 동일한 정점들로 구성 👉 G에 u로부터 v ≠ u 로의 방향경로가 존재한다면,G*에 u로부터 v로의 방향간선이 존재한다. 👉 더 쉽게, 수학적으로, "A -> B , B -> C 이면, A -> C" 를 의미하는 것
이행적폐쇄는 방향그래프에 관한 도달 가능성 정보를 제공한다.
방향그래프 G와 이행적폐쇄를 만족하는 방향그래프 G*
이행적폐쇄 계산
👉 각 정점에서 출발하여 DFS를 수행할 수 있다.
실행시간 : O(N(N + M))) 👉 N개의 각 정점의 대해 * DFS
대안으로, 동적프로그래밍(DP, Dynamic Programming)을 사용할 수 있다.
👉 Floyed-Warshall 알고리즘 : 위에서 설명한, "A -> B , B -> C 이면, A -> C"
📢 Floyed-Warshall 이행적폐쇄
정점들을 1,2,....n으로 번호를 매긴다.
1,2,....,k로 번호 매겨진 정점들만 경유 정점으로 사용하는 경로들을 고려해본다.
Floyed-Warshall 이행적폐쇄 예시
Alg Floyed-Warshall(G)
input a digraph G with n vertexs
output transitive closure G* of G
Let V(1),V(2),...,V(n) be an arbitrary numbering of the vertexs of G
output labeling of the edges of G in the connected
component of v as tree edges and back edges
l(v) <- Visited // 방문한 노드 체크
for each e ∈ G.incidentEdges(v) // 정점 v에 부착된 간선에 대해
if(l(e) == Fresh) // 간선 e가 아직 안지나간 간선이면
w <- G.opposite(v,e) // 정점 v와 간선 e를 통한 반대편 정점 w
if(l(w) == Fresh) // w가 아직 미방문 정점이면
l(e) <- Tree // 일단, 간선 e는 Fresh -> Tree 간선으로 변경
rDFS(G,w) // rDFS 재귀호출
else// 간선 e가 Fresh한 간선이 아니다 ?
l(e) <- Back // 그럼, 간선 e는 Fresh -> Back 간선으로 변경
DFS 수행 예시
DFS 처리 예시
DFS 속성
👉 속성 1. rDFS(G,v)는 v의 연결요소내의 모든 정점과 간선을 방문한다. 👉 속성 2. rDFS(G,V)에 의해 라벨된 트리 간선들은 v의 연결요소의 신장트리(DFS tree)를 형성한다.
DFS 분석
👉 정점과 간선의 라벨을 쓰고 읽는데 O(1)시간 소요 👉 각 정점은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Visited ) 👉 각 간선은 두 번 라벨 ( 한 번은 Fresh, 또 한번은 Tree 또는 Back 으로 ) 👉 incidentEdges( ) ( 한 정점에 붙어있는 부착간선 메소드 )는 각 정점에 대해 한 번 호출 👉 그래프가 인접리스트 구조로 표현된 경우, DFS는 O(N + M)시간에 수행 ( 어떤 그래프 G의 deg(v) 합 = 2M )
DFS 템플릿 활용
👉 연결성 검사, 경로 찾기, 싸이클 찾기 등의 문제들을 DFS를 확장해서 해결할 수 있다.
📢 비재귀적 DFS
rDFS ( 재귀 DFS )는 이름 그대로, 재귀호출을 통해서 그래프 순회를 한다.
비재귀적 DFS는 재귀호출이 아닌, 스택(Stack)을 사용해서 DFS를 실행한다.
Alg DFS(G,v)
input graph G and a start vertex v of G
output labeling of the edges of G
in the connected component of v
as tree edges and back edges
S <= empty stack
S.push(v) // 매개변수 v정점 스택에 push
while(!(S.isEmpty()) // 스택을 비울동안
v <= S.pop() // 스택 pop()
l(v) <- Visited // pop()한 정점는,이제 Visited
for each e ∈ G.incidentEdges(v) // pop()한 정점에 부착된 모든 간선에 대해
if(l(e) == Fresh) // 그 간선이 아직 방문안한 간선이면
w <- G.opposite(v,e) // pop()한 정점 v와 연결된 간선 e의 반대편 정점이 w
if(l(w) == Fresh) // 그 정점 w가 아직 방문안한 정점이면 ?
l(e) <- Tree // 건너언 간선 e는 일단 Fresh -> Tree 간선으로 변경
S.push(w) // 그리고, w정점을 스택에 push
else// 정점 w가 이미 방문한 정점이면
l(e) <- Back // 건너온 간선 e는 Fresh -> Back 간선으로 변경 ( 싸이클 제어 )
👉 G(v) : v의 연결요소라 했을 때 👉 속성 1. BFS1(G,v)는 G(v)의 모든 정점과 간선을 방문한다. 👉 속성 2. BFS1(G,v)에 의해 라벨된 트리 간선들은 G(v)의 신장트리(BFS tree)라 불린다. ( T(v) ) 👉 속성 3. L(i)내의 각 정점 w에 대해
1. T(v)의 v에서 w로 향하는 경로는 i개의 간선을 가진다. 2. G(v)내의 v에서 w로 향하는 모든 경로는 최소 i개 간선을 가진다.
BFS 분석
👉 정점과 간선의 라벨을 쓰고 읽는데 O(1) 시간소요 👉 각 정점은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Visited 로 ) 👉 각 간선은 두 번 라벨 ( 한 번은 Fresh로 , 또 한 번은 Tree 또는 Cross 로 ) 👉 각 정점은 리스트 L(i)에 한 번 삽입 ( 여기서 리스트는 큐(queue)를 의미 ) 👉 incidentEdges( ) ( 부착간선 메소드 )는 각 정점에 대해 한 번 호출 👉 그래프 G가 인접리스트 구조로 표현된 경우, BFS는 O(N + M)시간에 수행
BFS 템플릿 활용
👉 G의 연결요소들을 계산하기 👉 G의 신장숲을 계산하기 👉 G내의 단순 싸이클 찾기 또는 G가 숲임을 보고하기 👉 G의 주어진 두 정점에 대해, 그 사이의 최소 간선로 이루어진 G 내의 경로 찾기, 또는 그런 경로 없음을 찾기 ( 즉, 최단 경로(Directed Path) 문제 활용 가능 )
// Total = O(n) // 나를 제외한 모든 정점에 대해, 연결되어 있는지 하나씩 조사해야되니깐
나의 부착간선 반환 메소드( incidentEdges(v) )
Alg incidentEdges(v)// 인접리스트 버젼
input vertex v
output set of edge objects
L <- empty list
e <- (v.incidentEdges).next
while(e != ∅)
L.addLast(e)
e <- e.next
return L.element()
// Total = O(deg(v)) // 나한테 부착된 연결리스트만 확인하면 되니깐
=================================
Alg incidentEdges(v) // 인접행렬 버젼
input adjacency matrix A, vertex v
output set of edge objects
L <- empty list
vi <- index(v)
for j <- 0 to n - 1
if(A[vi,j] != ∅)
L.addLast(A[vi,j])
return L.elements()
// Total = O(n) // 나를 제외한 모든 정점에 대해 부착됬는지 확인해야되니깐
📢 번외
그래프 구현 방식 선택 : 다음 각 경우에 인접리스트 구조와 인접행렬 구조 둘 중 어느 것을 사용하겠는가 ?
👉 a. 그래프가 10,000개의 정점과 20,000개의 간선을 가지며, 가능한 최소한의 공간 사용이 중요 👉 b. 그래프가 10,000개의 정점과 20,000,000개의 간선을 가지며 가능한 최소한의 공간 사용이 중요 👉 c. 얼마의 공간을 사용하든, areAdjacent 질의에 가능한 빨리 답해야 할 경우
해결책
👉 a. 인접리스트 구조가 유리 = 실상 인접행렬 구조를 쓴다면 많은 공간을 낭비한다. 왜냐면 20,000개의 간선만이 존재하는데도 100,000,000개의 간선에 대한 공간을 할당하기때문 ( M <= (N(N-1)/2 ) 👉 b. 일반적으로, 이 경우에는 양쪽 구조 모두가 적합 = areAdjacent 작업은 인접행렬 구조가 유리, insertVertex와 removeVertex 작업에서는 인접리스트 구조가 유리 👉 c. 인접행렬 구조가 유리 = 이유는, 이 구조가 areAdjacent작업을 정점이나 간선의 개수에 관계없이 O(1)시간에 지원하기 때문이다.
O(log M) == O(log N)인 이유 ( M = 간선 수, N = 정점 수 )
👉 G를 N 개의 정점과 M 개의 간선으로 이뤄진 단순 연결그래프라 가정하자. 👉 M <= N(N-1)/2 이며, 이는 O(N^2)이다. 👉 따라서, O(log M) == O(log N^2) == O(2log N) == O(log N) 이다.
👉 키들을 외견상 무작위하게(Random) 분산시켜야 한다. 👉 계산이 빠르고 쉬워야 한다 ( 가능하면 상수시간 )
해시함수 예
📢 압축맵
나누기(Division) (보통사용 방식)
👉 h2(k) = |k| % M 👉 해시테이블의 크기 M은 일반적으로 소수(Prime)로 선택
승합제(MAD, Multiply Add and Divide)
👉 h2(k) = |ak + b| % M 👉 a와 b는 음이 아닌 정수로서, a % M != 0, 그렇지 않으면, 모든 정수가 동일한 값 b로 매핑됨
📢 해시코드맵
메모리 주소(Memory address)
👉 키 개체의 메모리 주소를 정수로 재해석( 모든 Java객체들의 기본 해시코드다. ) 👉 일반적으로 만족스러우나 수치 또는 문자열 키에는 적용 곤란
정수 캐스트(Integer case)
👉 키의 비트값을 정수로 재해석 👉 정수형에 할당된 비트 수를 초과하지 않는 길이의 키에는 적당 ( Java의 byte, short, int, float )
요소합(Component sum)
👉 키의 비트들을 고정길이(16 or 32bit)의 요소들로 분할한 후 각 ㅊ 합한다(overflow는 무시한다.) 👉 정수형에 할당된 비트 수 이상의 고정길이의 수치 키에 적당 ( 예 : Java의 long, double ) 👉 문자의 순서에 의미가 있는 문자열 키에는 부적당 ( 예: temp01-temp10, stop-tops-spot-pots )
다항 누적(Ploynomial accumulation)
👉 요소합과 마찬가지로, 키의 비트들을 고정길이(8,16,32bit)의 요소들로 분할 ( a(0),a(1),...,a(N-1) ) 👉 고정값 z를 사용하여 각 요소의 위치에 따른 별도 계산을 부과한 다항식 p(z)를 계산 (overflow 무시) 👉 p(z) = a(0) + a(1) * z + a(2) * z^2 + .... + a(N-1) * z ^ (N-1) 👉 문자열에 특히 적당 ( 예 : 고정값 z = 33을 선택할 경우, 50,000개의 영단어에 대해 단지 6회 충돌만 발생
📢 충돌해제 (중요 !!)
충돌(Collision) : 두 개 이상의 원소들이 동일한 셀로 매핑되는 것
즉, 상이한 키, k1과 k2에 대해 h(k1) = h(k2)면 "충돌이 일어났다."고 말한다.
분리연쇄법(Separate Chaining), 연쇄법 : 각 버켓 A[i]는 리스트 L(i)에 대한 참조를 저장 ( L(i)는 리스트 )
👉 해시함수가 버켓 A[i]로 매핑한 모든 항목들을 저장 👉 무순리스트가 또는 기록파일 방식을 사용하여 구현된 미니 사전이라 볼 수 있다.
장단점 : 단순하고 빠르다는 장점이 있으나 테이블 외부에 추가적인 저장공간을 요구
분리연쇄법(Separate Chaining)
예시
👉 h(k) = k % M 👉 키 : 25,13,16,15,7,28,31,20,1 ( = 충돌 일어난 키값 ) 👉 리스에 추가되는 항목들의 위치는, 리스트의 맨 앞에 삽입하는 것이 유리하다. (리스트의 tail 포인터 없는경우)
분할연쇄법 예시
📢 개방주소법 ( 선형조사법 )
개방주소법(Open Addresssing) : 충돌 항목을 테이블의 다른 셀에 저장
장단점 : 분리연쇄법에 비해 공간 사용을 절약하지만, 삭제가 어렵다는 것과 사전 항목들이 연이어 군집화
개방 주소법
선형조사법(Linear Probing) : 충돌 항목을 (원형으로)바로 다음의 비어있는 테이블 셀에 저장함으로써 충돌을 처리
즉, 다음 순서에 의해 버켓을 조사한다.
👉 A[ (h(k) + f(i)) % M ], f(i) = i, i = 0,1,2,...
검사되는 각 테이블 셀은 조사(Probe)라 불린다.
충돌 항목들은 군집화하며, 이후의 충돌에 의해 더욱 긴 조사열(Probe sequence)로 군집됨 = "1차 군집화"
예시
👉 h(k) = k % M 👉 키 : 25,13,16,15,7,28,31,20,1,38( = 충돌 키 )
선형조사법 예시
📢 개방 주소법( 2차 조사법 )
2차 조사법(Quadratic Probing) : 다음 순서에 의해 버켓을 조사
👉 A[ (h(k) + f(i) % M ], f(i) = i^2, i = 0,1,2,...
해시 값이 동일한 키들은 동일한 조사를 수반한다.
1차 군집화를 피하지만, 나름대로의 군집을 형성 할 수 있다. = "2차 군집화"
M이 소수가 아니거나 버켓 배열이 반 이상 차면, 비어 있는 버켓이 남아 있더라도 찾지 못할 수 있다. ( 단점 )
예시
👉 h(k) = k % M, f(i) = i^2 👉 키 : 25,13,16,15,7,28,31,20,1,38
2차 조사법 예시
📢 이중해싱
이중해싱(Double Hashing) : 두 번째의 해시함수 h`를 사용하여 다음 순서에 의해 버켓을 조사
👉 A[ (h(k) + f(i)) % M ], f(i) = i * h`(k), i = 0,1,2,....
동일한 해시값을 가지는 키들도 상이한 조사를 수반할 수 있기 때문에 군집화를 최소화한다.
h`는 계산 결과가 0이 되면 안된다. 👉 ( 0이 되면, f(i)는 결과적으로 0만 되겠죠 ? 그럼 한자만 계속 해싱충돌 )
최선의 결과를 위해, h`(k)와 M은서로소(Relative Prime)여야 한다.
👉 d(1)*M = d(2)*h`(k)이면, d(2) 개의 조사만 시도한다. 즉, 버켓들 중 d(2)/M만 검사 👉 h`(k) = q - (k % q) 또는 1 + (k % q)를 사용 ( 단, q < M은 소수며 M 역시 소수일 경우 ) 👉 한 마디로 위에 두 조건을 만족시키는, 해시함수를 적용하면, 군집화를 최소화하면서, 최소화로 실행가능
예시
👉 h(k) = k % M, h`(k) = 11 - (k % 11), ( 이때 q = 11이고, 11은 서로소이다. ) 👉 키 : 25,13,16,15,7,28,31,20,1,38( = 충돌 키 )
이중해싱 예시
개방주소법( 선형조사법, 2차조사법 ), 이중해싱 알고리즘
Alg findElement(k)
input bucket array A[0...M-1], hash function h, key k
사전에 관한 주요 작업 1. 탐색(Searching) 2. 삽입(Inserting) 3. 삭제(Deleting)
사전에는 두 종류의 사전 존재한다. 1. 무순사전 ADT (Ex. "가계부") 👉 "순서가 없다" 2. 순서사전 ADT (Ex. "출석부", "백과사전") 👉 "학번 or 자음순,모음순" 등의 정렬된 순서가 있다.
사전 응용에는 두 가지 1. 직접 응용 👉 "연락처 목록", "신용카드 사용승인", "인터넷주소 매핑" 2. 간접 응용 👉 "알고리즘 수행을 위한 보조 데이터구조", "다른 데이터구조를 구성하는 요소"
📢 탐색
비공식적 : 탐색(Search)은 데이터 집단으로부터 특정한 정보를 추출함을 말한다.
공식적 : 탐색(Search)은 사전으로 구현된 데이터 집단으로부터 지정된 키(key)와 연관된 데이터 원소를 반환함을 말한다.
사전 구현에 따른 탐색 기법
구현 형태
구현 종류
예
주요 탐색 기법
리스트
무순사전 ADT
기록(log)파일
선형탐색
순서사전 ADT
일람표
이진탐색
트리
탐새트리
이진탐색트리 AVL 트리 스플레이 트리
트리탐색
헤시테이블
해싱
📢 무순사전 ADT
무순리스트를 사용하여 구현된 사전 👉 사전 항목들을 임의의 순서로 리스트에 저장 ( 이중연결리스트 또는 원형 배열을 사용 )
성능 삽입 : O(1) 소요 👉 새로운 항목을 기존 리스트의 맨 앞 또는 맨 뒤에 삽입하면 되기 때문 삭제 : O(N) 소요 👉 (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문 탐색 : O(N) 소요 👉 (최악의 경우)항목이 존재하지 않을경우, 리스트 전체를 순회해야 하기 때문
효과적인 경우 : 소규모 사전, or 삽입은 빈번하나, 탐색이나 삭제는 드문 사전 ( Ex. 서버의 로그인 기록 )
input doubly linked list with header H and trailer T, Key K
output element with Key K
i <- H.next // 연결리스트 Header에 다음 노드로 초기화
while(i != T) // 연결리스트의 끝 Tailer전까지
if(i.key == K) // i.key == 목표 Key값
return i.elem
else// i.key == 목표 Key값
i <- i.next
return NoSuchKey
📢 순서사전 ADT
순서리스트를 사용하여 구현된 사전 👉 사전 항목들을 배열에 기초한 리스트에 키로 정렬된 순서로 저장
성능 삽입 : O(N) 👉 새 항목을 삽입하기 위한 공간 확보를 위해, (최악의 경우) N개의 기존 항목을 이동해야 한다. 삭제 : O(N) 👉 항목이 삭제된 공간을 기존 항목들로 메꾸기 위해 (최악의 경우) N개의 기존 항목 이동해야 한다.탐색 : O(log(N)) 👉 이진탐색을 사용하면 가능하다.
효과적인 경우 : 소규모 사전, or 탐색이 빈번하나, 삽입 삭제는 드문 사전 ( Ex. 전화번호부 )
📢 이진탐색(Binary Search)
키값으로 된 "배열(Array)"에 기초한 리스트로 구현된 사전에 대해 탐색 작업을 수행한다.
배열의 키값들은 반드시 "정렬(Sorted)"되어 있어야 한다.
재귀적인 방식비재귀적 방식이 두 가지 모두 구현 가능하다.
입력크기(N)의 로그 수(log(N))에 해당하는 수의 재귀(or 비재귀)를 수행한 후 정지한다. ( Ex. 스무고개 )
