파이썬 힙큐(heapq)
파이썬의 힙큐는 min heap을 구현한 내장 모듈이고, heap은 완전 이진 트리의 일종이므로 완전 이진 트리 -> heap -> 파이썬 힙큐 순으로 설명. 완전 이진 트리와 포화 이진 트리 이진 트리란 자식 노드가 최대 2개로 구성된 트리를 말한다. (참고로 이진 탐색 트리BST…
Data Structure/Algorithm
BigO 알고리즘 시간 복잡도 비교
알고리즘의 효율성은 빅오표기법으로 많이 표시되는데, 이는 running time complexity가 최악인 case를 측정해서 비교하는 것이다. Input size가 n이고 c가 양의 상수일 때 Time complexity를 비교하자면 아래와 같다. 빅오표기법 효율성 비고 예시 🚀 Constant…
이진 탐색 트리(BST) - Insert와 Delete 메서드
3. 이진 탐색 트리(Binary Search Tree) 3-1. 이니셜라이저 3-2. Search 메서드 3-3. Insert 메서드 insert는 search와 매우 흡사하다. 다만 이진탐색트리는 중복 노드가 있어선 안되므로 search…
이진 탐색 트리(BST) - 구성요소와 Search 메서드
왜 이진 탐색 트리(Binary Search Tree, BST)인가? 정렬된 배열에서의 검색은 이진 검색으로 하면 되므로 O(logN)으로 매우 빠르다. 단, 삽입과 삭제는 느리다. 정렬된 상태를 유지하려면 최악의 경우 N개의 원소를 시프트해야 하므로 O(N…
배열과 비교한 연결 리스트
연결 리스트(linked-list)는 배열과 마찬가지로 항목의 리스트를 표현하는 자료 구조이다. 배열과 다른 점 배열은 어떤 인덱스든 한 단계만에 접근할 수 있다.(=읽기가 ) 프로그램은 배열이 어떤 메모리 주소부터 시작하는지 알고 있으며 전체 길이를 알고 있기 때문이다. 예컨대 0번째 인덱스의 주소가 100…