자료구조 & 알고리즘 & cs/자료구조 (3) 썸네일형 리스트형 [TIL] 힙 - Heap 힙(Heap)이란? 완전 이진 트리(Complete Binary Tree) - 최대/최소값을 빠르게 찾기 위함 max heap과 min heap으로 분류 (최대값/최소값을 구하기 위한 구조) 각 노드의 값 >= 해당노드의 자식노드 값 (max heap) (min heap은 반대) 힙 구현시 배열 자료구조를 사용 * 완전 이진 트리 : 노드 삽입 시 가장 하단의 왼쪽 노드부터 차례대로 삽입하는 트리 힙 vs 이진 탐색 트리? -힙 : 최대/최소값 검색을 위한 구조 -이진 탐색 트리 : 탐색을 위한 구조 힙의 인덱스 구조 부모 노드의 인덱스 번호 = 자식 노드 인덱스 번호 // 2 왼쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * 2 오른쪽 자식 노드의 인덱스 번호 = 부모 노드 인덱스 번호 * .. [TIL] 트리 - Tree 트리(Tree)란? node와 branch를 이용한 데이터 구조 사이클x 탐색 알고리즘에 많이 사용(BST) 용어 노드(Node) : 데이터를 저장하는 기본 요소 (+ Branch) 루트노드(Root Node) : 트리의 최상위 노드 레벨(level) : 하위 브랜치로 연결된 노드의 깊이 부모 노드(Parent Node) : 어떤 노드의 다음 레벨 노드 자식 노드(Child Node): 어떤 노드의 상위 레벨에 연결된 노드 리프 노드(Leaf Node): 자식 노드가 하나도 없는 노드 (= terminal node) 형제 노드(Sibling Node): 동일한 부모 노드를 가진 노드 (= 레벨이 동일) Depth : 트리의 최대 level 이진 트리(Binary Tree) : 노드의 최대 Branch가 .. [TIL] 해쉬 테이블 - Hash Table 해쉬 테이블(Hash Table)이란? (파이썬의 Dictionary) 키에 데이터를 저장하는 데이터 구조이다. 데이터 검색 속도가 매우 빠르다 배열로 미리 해쉬 테이블 사이즈만큼 생성 후 사용한다. 용어 해쉬(Hash) : 임의의 값을 고정 길이로 변환하는 것 해싱함수(Hashing Function) : key를 가지고 연산하여 데이터의 위치를 찾을 수 있는 함수 해쉬 값(Hash Value) : 해싱함수를 이용하여 key에 대한 연산을 통해 해쉬값을 알아냄 해쉬 주소(Hash Address) : 해쉬 값을 기반으로 key에 대한 데이터의 위치를 찾아냄 슬롯(Slot) : 한개의 데이터를 저장할 수 있는 공간 장점 데이터 검색속도가 빠름 (데이터 저장, 데이터 읽기) // 배열과 비교하여 알아두기 해당.. 이전 1 다음