동적배열2 힙 형태 속성 : 힙은 완전 이진 트리 (완전 이진 트리의 높이 O(lg(n))) 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터 보다 크거나 같다. 정렬 알고리즘 : 데이터를 재배치하는 구체적인 방법 힙 구현하기 완전 이진 트리이기 때문에 동적 배열로 구현 ⇒ 파이썬에서는 동적 배열을 활용한 리스트로 구현 왼쪽 자식 인덱스 : 인덱스 * 2 오른쪽 자식 인덱스 : 인덱스*2+1 Heapify 원하는 노드를 힙속성에 맞는 위치로 재배치 시키는 알고리즘 시간 복잡도 O(lg(n)) 주어진 리스트를 힙으로 만들기 ⇒ 가장 맨마지막 노드부터 루트 노드까지 heapify를 호출해준다. → 역순으로 heapify를 호출해주면 부분트리마다 힙속성을 만족시키고 올라가기 때문에 모든 노드를 힙속성에 맞출수있고 힙이.. 2024. 1. 12. 배열 C 배열과 파이썬 리스트 차이 C배열 : 메모리에 값자체를 연속적으로 저장한다 파이썬 리스트 : 메모리에 레퍼런스를 저장하고 이 레퍼런스는 다른 값들을 가르킨다. 💡 배열에서 값을 받아오거나 저장하는건 램의 특성으로 O(1)으로 접근 가능하다. 배열탐색 선형 탐색이라고도 불리며 인덱스 0번부터 차례대로 배열을 살펴본다. ⇒ 즉, 탐색은 O(n)이 걸린다. 정적 배열 : 크기가 고정된 배열 동적 배열 : 크기가 변하는 배열 정적 배열로 만들어진 자료 구조 정적 배열의 크기를 상황에 맞게 조절한다. 동적 배열 연산 추가연산 정적배열에 남는 공간이 있을때 O(1) 정적배열이 꽉찼을 때 : O(n) 분할 상환 분석 연산을 n번 했을 때 총 드는 시간 X를 n으로 나눠주는 할부 개념 ⇒ 최악의 경우로 시간 복잡도.. 2024. 1. 7. 이전 1 다음
