λ³Έλ¬Έ λ°”λ‘œκ°€κΈ°

전체 κΈ€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.
λ°˜μ‘ν˜•

ν‹°μŠ€ν† λ¦¬νˆ΄λ°”