IT개발/자료구조를 알아보자!7 자료구조 : 힙(Heap) 힙(Heap) 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리(Complete Binary Tree) 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙(Heap)을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 힙에 데이터를 넣고, 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용됨 힙(Heap)의 구조 힙은 최대값을 구하기 위한 구조와 최소값을 구하기 위한 구조로 분류할 수 있음 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 크거나 같다. (최대 힙의 경우) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노.. 2021. 8. 16. 자료구조 : 트리(Tree) 트리(Tree) 구조 트리 : 노드(Node)와 Branch를 이용해서 사이클을 이루지 않도록 구성한 데이터 구조 이진트리(Binary Tree) 형태의 구조이며 검색(탐색) 알고리즘 구현을 위해 사용됨 용어 Node : 트리에서 데이터를 저장하는 기본요소 Root Node : 트리 맨 위에 있는 노드 Level : 최상위 노드를 Level 0으로 하였을 때, 하위 Branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node : Child Node가 하나도 없는 노드 Sibling (Brother Node) : 동일한 Parent Node를 가진 노드 Depth : 트리에서 Node.. 2021. 8. 14. 자료구조 : 해쉬 테이블(Hash Table) 해쉬 구조 Key(키)에 Value(데이터)를 저장하는 데이터 구조 Key를 통해 바로 데이터를 받을 수 있음, 속도가 빨라짐 공간과 탐색 시간끼리 서로 바꾸는 기법. 일반적으로 배열에서 미리 Hash Table사이즈만큼 생성 후 사용 단어 해쉬(Hash) : 임의 값을 고정 길이로 변환하는 것 해쉬 테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱 함수(Hashing Function) : Key에 대해 산술 연산을 이용해 데이터 위치를 찾을 수 있는 함수 해쉬 값(Hash Value) : Key를 해싱 함수로 연산하여 해쉬 값을 알아내고 이를 기반으로 해쉬 테이블에서 해당 Key에 대한 데이터 위치를 일관성있게 찾을 수 있음 슬롯(Slot) : 한 개의 데이터를.. 2021. 8. 12. 자료구조 : 링크드 리스트 (Linked List) 링크드 리스트(Linked List) 구조 떨어진 곳에 존재하는 데이터를 화살표로 연결해서 관리하는 데이터 구조 노드(Node) : 데이터 저장 단위인 데이터값, 포인터로 구성 포인터(Pointer) : 각 노드 안에서, 다음이나 이전의 노드와의 연결 정보를 가지고 있는 공간 링크드 리스트(Linked List) 형태 Node 구현 class Node: def __init__(self, data): self.data = data self.next = None class Node: def __init__(self, data, next=None): self.data = data self.next = next Node와 Node 연결 (포인터 활용) node1 = Node(1) node2 = Node(2) n.. 2021. 8. 10. 이전 1 2 다음
