반응형 { Computer Science }/Data Structure12 [자료구조] 해쉬 함수의 충돌(collision) 문제 해결 ------------------------------------------------------------------- 요약: 다음과 같은 방법들로 해쉬 함수의 충돌을 방지함 - 오픈 어드레싱(open addressing method) 1. 선형 조사법(Linear Probing) 2. 이차 조사법(Quadratic Probing) 3. 이중 해쉬(Double Hash) - 닫힌 어드레싱(closed addressing method) 4. 체이닝(Chaining) -------------------------------------------------------------------- 해쉬함수의 충돌(collision) 문제 해결 1. 선형 조사법(Linear Probing) - 충돌 발생 시 그 옆자.. 2021. 10. 21. [자료구조] 트라이(Trie) 구현 - 파이썬 트라이(Trie): 검색트리의 일종으로 일반적으로 키가 문자열인, 동적 배열 또는 연관 배열을 저장하는 데 사용되는 정렬된 트리 자료구조다. class Node: def __init__(self): self.word = False self.children = {} class Trie: def __init__(self): self.root = Node() def insert(self, word): node = self.root for char in word: if char not in node.children: node.children[char] = Node() node = node.children[char] node.word = True def search(self, word): node = self.r.. 2021. 9. 7. [자료구조] 힙 Heap 정의와 연산 힙 : 힙의 특성을 만족하는 거의 완전한 트리인 특수한 트리 기반의 자료구조 힙의 예시로 최소 힙이 있다. 부모가 항상 자식보다 작기 때문에 루트가 결국 가장 작은 값을 갖게 된다. 주의할 점은 힙은 정렬된 구조가 아니다. 최소 힙의 경우 부모 노드가 항상 작다는 조건만 만족할 뿐 좌우에 대한 관계는 정의하지 않는다. - 삽입 삽입에는 업힙(up heap)연산이 필요하고 과정은 다음과 같다. 삽입의 시간복잡도는 O(logN)이다. 1. 요소를 가장 하위레벨의 최대한 왼쪽으로 삽입 2. 부모 값과 비교해 값이 더 작은 경우 위치를 변경 3. 계속해서 부모 값과 비교해 위치를 변경(가장 작은 값일 경우 루트까지 올라감) - 추출 루트를 추출하면 되는 간단한 작업이지만 추출 이후 힙의 특성을 유지하는 작업이 .. 2021. 4. 14. [자료구조] 이진탐색트리 Binary Search Tree / 주요 알고리즘 예제(전위 순회, 중위 순회, 후위 순회) 이진 '탐색' 트리 : 정렬된 트리 - 노드의 왼쪽 서브트리: 노드의 값보다 작은 값들을 지닌 노드들 - 노드의 오른쪽 서브트리: 노드의 값과 같거나 큰 값들을 지닌 노드들 이진탐색트리의 장점 -> 탐색의 시간 복잡도가 O(logN)이다. - 자가 균형 이진 탐색 트리 : 삽입, 삭제 시 자동으로 높이를 작게 유지하는 노드 기반의 이진탐색 트리 왼쪽 노드에 비해 오른쪽 노드가 높이를 가능한 작게 유지한 트리다. 즉 오른쪽 트리가 자가 균형 이진 탐색 트리다. 균형트리와 불균형트리의 성능차이는 매우 크다. 노드 갯수가 증가할수록 성능 차이는 커진다. 자가 균형 이진 탐색 트리의 대표적 예로 AVL 트리, 레드-블랙 트리가 있다. - 정렬된 배열로 자가 균형(또는 높이 균형) 이진탐색 트리 만들기 ☆☆☆ 문.. 2021. 4. 12. [자료구조] 이진트리 주요 알고리즘 응용 문제를 잘 풀기 위해 기본을 탄탄하게 만들어야 한다. 이진트리 문제 중 기본에 해당하는 문제들을 익히면서 나만의 접근법을 완성시키자! 1. 이진트리 최대 깊이 탐색(dfs 사용하였다.) leetcode.com/problems/maximum-depth-of-binary-tree # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: max_dep =0 def maxDepth(self, root: TreeNode) -> int: def df.. 2021. 4. 10. [자료구조] 트리 정의와 종류(그래프와의 차이점, 이진트리 유형) 트리 : 계층형 트리구조를 시뮬레이션하는 추상자료형으로, 루트값과 부모-자식 관계의 서브 트리로 구성되며, 서로 연결된 노드의 집합이다. 가장 큰 차이점은 트리는 순환 구조를 갖지 않는다는 것! 그래프는 단방향, 양방향을 모두 가리킬 수 있는 반면 트리는 단방향(부모->자식)뿐. 또한 트리는 하나의 부모만을 가지고 루트 또한 하나다. 위의 세 경우는 모두 트리가 아닌 경우의 예시다. 첫번째 - C의 부모가 둘이라 트리가 될 수 없음 두번째 - (A-B)와 (D-C-E)가 연결되어 있지 않고 루트가 둘이라 트리가 될 수 없음 세번째 - 순환구조라서 트리가 될 수 없음 이진 트리(Binary Tree) 트리 중 특히 모든 노드의 차수가 2 이하일 때를 이진 트리(Binary Tree)라고 부른다. 유형 3가.. 2021. 4. 9. 이전 1 2 다음 반응형
