프로그래밍/알고리즘 (45) 썸네일형 리스트형 그래프에서의 BFS Graph Traversal 그래프 순회- 순회 (traversal)그래프의 모든 노드들을 방문하는 일을 말한다.- 순회를 하는 두 가지 방법BFS (Breadth-First Search, 너비 우선 순회)DFS (Depth-First Search, 깊이 우선 순회) 너비 우선 순회 (BFS)- BFS 알고리즘은 아래와 같은 순서로 노드들을 방문하게 된다.$L_0$ = {s} (s : 출발 노드)$L_1$ = $L_0$의 모든 이웃 노드들$L_2$ = $L_1$의 이웃들 중 $L_0$의 이웃에 속하지 않은 노드들...$L_i$ = $L_{i-1}$의 이웃들 중에 $L_{i-2}$에 속하지 않는 노드들*level order은 BFS의 이진 트리 버전이다. 큐를 이용한 너비 우선 순회1) check the .. 그래프의 개념과 표현 그래프 알고리즘 (Graph Algorithms) 그래프- (무방향) 그래프 G = (V, E)V : 노드(node) 혹은 정점(vertex)을 의미한다.E : 노드 쌍을 연결하는 엣지(edge) 혹은 링크(link)를 의미한다.개체(object)들 간의 이진관계를 표현한다.E(1, 2)는 (2, 1)과도 같은 의미를 내포한다.보통 두 접점을 연결하는 엣지는 하나 혹은 없다고 가정한다. 또한 self edge도 없다고 가정한다.n = | V |, m = | E | 방향 그래프와 가중치 그래프- 방향 그래프(Directed Graph) G = (V, E)엣지 (u, v)는 u로부터 v로의 방향성을 가지고 있다.self edge를 허용한다.- 가중치(weighted) 그래프엣지마다 가중치(weight)가 지.. 해싱 (Hashing) (3) Hashing 좋은 해쉬 함수의 조건- 현실에서의 키들은 무작위값이 아니다.- 만일 키들의 통계적인 분포에 대해 알고 있다면 이를 활용하여 해쉬 함수를 고안할 수 있겠지만 현실적으로 할 수 없는 방법이다.- 키들이 어떤 특정한(가시적인) 패턴을 가지더라도 해쉬함수 값이 불규칙적이도록 하는 것이 바람직하다. 이는 곧 해쉬합수의 값이 키의 특정 부분에 의해서만 결정되지 않도록 만들어야 한다는 뜻이다. 해쉬 함수를 만드는 방법- Division 기법h(k) = k mod m => 거의 모든 해쉬함수들이 가장 마지막에 수행하는 경향이 있다.Ex) m = 20, k = 91 -> h(k) = 11장점 : 한 번의 mod연산으로 계산하기 때문에 속도가 빠르다.단점 : 어떠한 m값에 대해서는 해쉬 함수의 값이 키 값.. 해싱 (Hashing) (2) Hasing Open Addressing을 통한 충돌 해결- 모든 키를 해쉬 테이블 자체에 저장한다.- 테이블의 각 칸(slot)에는 1개의 키만 저장한다.- 충돌 해결 기법의 종류Linear probingQuadratic probingDouble hashing Open Addressing의 방법 - Linear Probing- h(k), h(k) + 1, h(k) + 2, ...의 순서로 검사를 진행한다. 만일 원래 저장할 슬롯에 데이터가 존재한다면 계속 뒤로 진행하며 가장 처음에 나오는 빈 슬롯에 데이터를 저장한다.- 테이블의 끝에 도달하면 다시 처음으로 돌아가며 circular하게 저장 공간을 찾게 된다.- Linear Probing의 단점primary cluster : 키에 의해서 채워진 연속된 .. 해싱 (Hashing) (1) Hashing Hash Table- 해쉬 테이블은 dynamic set을 구현하는 효과적인 방법들 중 하나이다.적절한 가정을 한 후에는 평균적인 탐색, 삽입, 삭제 시간에 O(1)만이 소요된다.최악의 경우 시간 복잡도는 대부분의 경우 Θ(n)이 된다.- 해쉬 함수 (hash function) h를 이용해 키 k를 T[h(k)]에 저장하게 된다.h : U -> {0, 1, ..., m - 1} // 이 때 m은 테이블의 크기, U는 가능한 모든 키들의 집합이다.이 과정은 보통 키 k가 h(k)로 해싱되었다라고 말하게 된다. 해쉬 함수의 예- 모든 키들을 자연수라고 가정한다. (어떤 데이터들일지라도 자연수로 해석이 가능하다.)- Ex : 문자열ASCII 코드 : C = 67, L = 76 등- 해쉬 함수의 .. Red Black Tree (2) 보호되어 있는 글입니다. Red Black Tree (1) 보호되어 있는 글입니다. 이진 검색 트리 (3) 보호되어 있는 글입니다. 이전 1 2 3 4 5 6 다음
