배열2 [코딩 + 알고리즘 완주반] 15일차. 힙 # 힙 데이터에서 최대값과 최소값을 빠르게 찾기 위해 고안된 완전 이진 트리 완전 이진 트리 : 노드를 삽입할 때 최하단 왼쪽 노드부터 차례대로 삽입하는 트리 # 힙을 사용하는 이유 배열에 데이터를 넣고, 최대값과 최소값을 찾으려면 O(n)이 걸림 힙에 데이터를 넣고 최대값과 최소값을 찾으면 O(logn)이 걸림 우선순위 큐와 같이 최대값 또는 최소값을 빠르게 찾아야 하는 자료구조 및 알고리즘 구현 등에 활용 # 힙 구조 힙은 최대값을 구하기 위한 구조(최대힙) 와, 최소값을 구하기 위한 구조( 최소 힙) 으로 분류 가능 1. 각 노드의 값은 해당 노드의 자식노드가 가진 값보다 크거나 같다(최대힙) 최소 힙의 경우는 각 노드의 값은 해당 노드의 자식 노드가 가진 값보다 작거나 같음 2. 완전 이진 트리 .. 2021. 3. 29. [코딩 + 알고리즘 완주반] 11일차. 배열, 큐 # 꼭 알아둬야 할 자료구조 - 배열 데이터를 나열하고 각 데이터를 인덱스에 대응하도록 구성한 데이터 구조 파이썬에서는 리스트 타입이 배열 기능을 제공하고 있음 장점 - 빠른 접근 가능 단점 - 데이터 추가/삭제가 어렵다 # 파이썬과 배열 파이썬 리스트 활용 # 대표적인 데이터 구조 : 큐 FIFO ( First in First Out) ( 줄을 서는 것과 유사) LILO ( Last In Last Out) # 용어 enqueue : 데이터를 넣는 기능 dequeue : 데이터를 빼는 기능 # 파이썬 큐 라이브러리( import queue ) Queue() : 가장 일반적인 큐 자료 구조 - put, get, qsize LifoQueue() : 나중에 입력된 데이터가 먼저 출력되는 구조(스택구조) - p.. 2021. 3. 25. 이전 1 다음 반응형
