자료구조 (6) 썸네일형 리스트형 [자료구조] 힙 (heap) 힙 이란? 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리? 노드를 삽입할때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 힙을 사용하는 이유 배열에 데이터를 넣고, 최소값과 최대값을 찾는 시간 = O(n) 힙에 데이터를 넣고, 최소값과 최대값을 찾는 시간 = O(logn) 우선순위큐와 같이 최대값/최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현에 활용 힙 구조 힙은 최대힙(최대값을 구하기 위한 구조, Max Heap)과 최소힙(최소값을 구하기 위한 구조, Min Heap)으로 분류 힙은 두가지 조건을 가지고 있는 자료구조다 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(이게 최대힙) 완전 이진 트리의 구조를 가진다 힙과 이진 탐색 트리 공통점.. [자료구조] 트리 (Tree) 트리 구조 트리 : Node와 Branch를 이용해서, 사이클을 이루지 않도록 구성한 데이터 구조 실제로 어디에 많이 사용? 이진트리(Binary Tree)형태의 구조에서 탐색 알고리즘 구현을 위해 사용 용어 Node : 트리에서 데이터를 저장하는 기본 요소 (+다른 연결된 노드에 대한 branch정보) Root Node : 트리 맨위에 있는 노드 Level : 최상위 노드를 Level 0으로 했을때, 하위 branch로 연결된 노드의 깊이를 나타냄 Parent Node : 어떤 노드의 다음 레벨에 연결된 노드 Child Node : 어떤 노드의 상위 레벨에 연결된 노드 Leaf Node : Child Node가 하나도 없는 노드 Sibling : 동일한 Parent Node를 가진 노드 Depth : .. [자료구조] 해쉬테이블 (Hash Table) 해쉬 구조 키(Key)에 데이터(Value)를 저장하는 구조 Key를 통해 바로 데이터를 받아올 수 있으므로, 속도가 매우 빠르다 파이썬 Dictionary타입 = 해쉬테이블의 예시 보통 배열로 미리 해쉬테이블 사이즈만큼 생성한 후에 사용 = 공간과 탐색시간을 맞바꾸는 기법 용어 해쉬(Hash) : 임의값을 고정길이로 변환하는 것 해쉬테이블(Hash Table) : 키 값의 연산에 의해 직접 접근이 가능한 데이터 구조 해싱함수(Hashing Function) : 키에 대해 산술연산을 이용해 데이터위치를 찾을 수 있는 함수 해쉬값(Hash Value) : 키를 해싱함수로 연산해서 해쉬값을 알아내고, 이를 기반으로 해쉬테이블에서 해당 키에 대한 데이터 위치를 일관성있게 찾을 수 있음 슬롯(Slot) : 한개.. [자료구조] 링크드리스트 (linked list) 링크드 리스트 구조 연결 리스트라고도 한다 배열 : 순차적으로 연결된 공간에 데이터를 나열하는 구조 링크드 리스트 : 떨어진 곳에 있는 데이터를 화살표로 연결하는 구조 기본구조 & 용어 노드 (Node) : 데이터 저장단위로 구성 (데이터값+포인터) 포인터(pointer) : 각 노드 안에서 다음이나 이전의 노드와의 연결정보를 가지고 있는 공간 링크드 리스트 장단점 장점 미리 데이터 공간을 할당하지 않아도 됨 단점 연결을 위한 별도의 데이터 공간이 필요 = 저장공간 효율이 낮음 연결 정보를 찾는 시간이 필요하므로 접근속도가 느림 중간 데이터 삭제시, 앞뒤 데이터의 연결을 재구성해야 하는 부가적인 작업 필요 링크드 리스트 구현 class Node: def __init__(self, data, next=No.. [자료구조] 스택 (stack) 스택 구조 후입 선출 : 가장 나중에 쌓은 데이터를 가장 먼저 빼낼 수 있는 구조 데이터에 제한적으로 접근 (한쪽 끝에서만 데이터를 넣거나 뺌) 기능 push() : 데이터를 스택에 넣기 pop() : 데이터를 스택에서 꺼내기 스택의 장단점 장점 구조가 단순해서 구현이 쉽다 데이터 저장/읽기 속도가 빠르다 단점 데이터 최대 갯수를 미리 지정해야한다 저장공간의 낭비가 발생 파이썬 리스트 기능 append(push), pop() 메소드를 이용하여 스택기능 구현 [자료구조] 큐 (queue) 큐 구조 선입선출 = 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조 FIFO(First-in, First-out) 또는 LILO(Last-in, Last-Out) 스택과 꺼내는 순서가 반대 용어 Enqueue : 큐에 데이터를 넣는 기능 Dequeue : 큐에서 데이터를 꺼내는 기능 파이썬 큐 라이브러리 Queue() : 가장 일반적인 큐 자료 구조 LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조 (=스택) PriorityQueue() : 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터 출력 이전 1 다음
