본문 바로가기

분류 전체보기137

14-3강. 그래프에서의 DFS DFS(Depth-First Search) 깊이 우선 탐색 level order traversal (BFS) inorder traversal (DFS) pre-order traversal (DFS) post-order traversal (DFS) 1. 출발점 s에서 시작한다. 2. 현재 노드를 visited로 mark하고, 인접한 노드들 중 unvisited 노드가 존재하면 그 노드로 간다. 3. 2번을 계속 반복한다. 4. 만약 unvisited인 이웃노드가 존재하지 않는 동안 계속해서 직전 노드로 되돌아 간다. 5. 다시 2번을 반복한다. 6. 시작노드 s로 돌아오고, 더이상 갈 곳이 없으면 종료한다. 이 그래프에서는 1-3-7-8-7-3-5-2-4-2-5-6 순서로 간다.. (하지만 순서는 바뀔 수.. 2020. 12. 6.

14-1강. 그래프(Graph) 개념과 표현 (무방향) 그래프. G = (V, E) - V : 노드(node) 혹은 정점(vertex) - E : 노드 쌍을 연결하는 에지(edge) 혹은 링크(link) - 개체(object)들 간의 이진관계를 표현 - n = |V|, m = |E| 방향그래프(Directetd Graph). G=(V, E) - 에지(u, v)는 u로부터 v로의 방향을 가짐 가중치 (weighted) 그래프 - 에지마다 가중치(weight)가 지정 그래프의 표현 - 인접행렬 (adjacency matrix) - 인접리스트 (adjacency list) 위의 그림에서 m은 엣지의 갯수를 나타낸다.. n(:노드의 갯수) + 2m(:노드 갯수) 이어서 저장공간은 O(n+m)이다. 방향그래프를 표현하는 방법 가중치 그래프의 인접행렬 표현 .. 2020. 12. 1.

13-3. 해슁 3 좋은 해쉬 함수란? - 현실에서는 키들이 랜덤하지 않음 - 만약 키들의 통계적 분포에 대해 알고 있다면 이를 이용해서 해쉬 함수를 고안하는 것이 가능하겠지만 현실적으로 어려움 - 키들이 어떤 특정한 (가시적인) 패턴을 가지더라도 해쉬함수값이 불규칙적이 되도록 하는 게 바람직 - 해쉬함수 값이 키의 특정 부분에 의해서만 결정되지 않아야.. Division 기법 - h(k) = k mod m - 예 : m = 20 and k = 91 -> h(k) = 11 - 장점 : 한 번의 mod 연산으로 계산. 따라서 빠름. - 단점 : 어떤 m값에 대해서는 해쉬 함수값이 키값의 특정 부분에 의해서 결정되는 경우가 있음. 가령 m = 2^p이면 키의 하위 p비트가 해쉬함수 값이 됨. Multiplication 기법 -.. 2020. 11. 29.

13-1강. 해슁(Hashing) 1 SUHA(Simple Uniform Hashing Assumption) - 각각의 키가 모든 슬롯들에 균등한 확률로() 독립적으로(independently) 해슁된다는 가정 => 사실 현실적이지 않다. - 성능분석을 위해서 주로 하는 가정일 뿐 - hash 함수는 deterministic하므로 현실에서는 불가능하다 - Load factor alpha = n/m: - n : 테이블에 저장될 키의 갯수 - m : 해쉬테이블의 크기, 즉 연결리스트의 깃수 - 각 슬롯에 저장된 키의 평균 갯수 - 연결리스트 T[j]의 길이를 Nj라고 하면, E[Nj] = alpha - 만약 n = O(m)이면 평균검색시간은 O(1) 2020. 11. 24.

이전 1 ··· 29 30 31 32 33 34 35 다음

티스토리툴바