SMALL CS study/Data Structure7 6. Hash - 파이썬 해시 공부하기 해시 해시 맵/테이블은 키를 값에 매핑할 수 있는 자료구조이다. 가장 큰 특징은 대부분의 연산의 시간 복잡도가 O(1)이라는 점이다. 해싱을 할 때, 데이터들은 필연적으로 서로 다른 키 값이 같은 해시값을 가리키는 충돌을 발생시킨다. → 개별 체이닝, 오픈 어드레싱 개별 체이닝 충돌된 데이터들을 연결 리스트로 연결하는 방식 잘 구현한 경우 탐색은 O(1)이지만 최악의 경우 모든 해시 충돌이 발생하면 O(n)이 됨 오픈 어드레싱 충돌 발생 시 탐사를 통해 빈 공간을 찾아나서는 방식 일정 수(그 기준을 로드팩터라고 함) 이상 채워지면, 그로스 팩터의 비율에 따라 더 큰 크기의 또 다른 버킷을 생성한 후 여기에 새롭게 복사하는 리해싱 작업이 일어남 파이썬에서 해시 사용법 파이썬에서 해시는 '딕셔너리' 자료형으.. 2021. 8. 8. 6. Heap - 파이썬 힙 공부하기 힙 특정한 규칙을 가지는 트리로, 최댓값과 최솟값 추출 연산을 효율적으로 하기 위해 고안된 완전이진트리 구조 최소힙 부모 노드 키값이 자식 노드의 키값보다 항상 작은 힙 최대힙 부모 노드 키값이 자식 노드의 키값보다 항상 큰 힙 # 위 그림의 list표현에서 2k+1과 2k+2는 k번째 노드의 자식 노드들이 된다. # 위 그림의 list표현에서 k번째 노드의 부모 노드는 (k-1)//2가 된다. 주의할 점 힙은 정렬된 구조가 아니다. 상/하 관계는 있으나, 좌/우 관계는 없다. 추출 메서드 자체는 O(1)이지만, 재정렬 과정이 필요하기 때문에 O(logn)이 된다. → 삽입, 추출 모두 O(logn) 파이썬에서 힙 사용법 파이썬은 heapq 모듈을 제공한다. 내부적으로는 리스트를 활용한 최소 힙의 형태이.. 2021. 8. 8. 5. Priority Queue - 파이썬 우선순위큐 공부하기 우선순위 큐 우선순위가 가장 높은 요소가 먼저 추출되는 자료형 최댓값/최솟값 추출 일반적인 큐와 달리 데이터를 꺼낼 때 우선순위를 갖는 큐값이 입력되고 삭제될 때마다 자료구조가 내부적으로 정렬해줘야 하기 때문에 구현방법과 시간 복잡도에 차이가 있다. 구현방법 리스트 또는 힙을 이용 자료형 삽입 삭제 리스트 O(1) O(n) 힙 O(logn) O(logn) 우선순위 큐 (힙이용) O(logn) O(logn) 파이썬에서 큐 사용법 queue 모듈을 사용한다. 이 모듈은 내부적으로 heapq 모듈을 사용한다. from queue import PriorityQueue que = PriorityQueue() # 내부적으로 heap 모듈을 사용 limitedQue = PriorityQueue(maxsize=10) .. 2021. 8. 5. 4. Queue - 파이썬 큐 공부하기 큐란? 큐는 선입선출 (First-In-First-Out) 방식의 자료구조이다. 파이썬은 큐 자료형을 직접적으로 제공하지는 않지만, 리스트가 그 기능을 지원한다. 큐의 메소드 push() : 컬렉션에 요소를 추가한다. pop() : 컬렉션의 가장 최근에 추가된 요소를 제거한다. 데크 자료형 데크를 이용하면 popleft()시에 시간복잡도가 감소한다. 자료형 연산 시간 List.pop(0) O(n) Deque.popleft() O(1) import collections Q = collections.deque() # 데크 선언 Q.append(N)# 데크 요소 추가 Q.popleft() # 데크의 맨 앞 요소 추출 2021. 8. 5. 3. Binary Tree - 파이썬 이진트리 공부하기 Binary Tree 란? 모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리. 하나의 노드는 최대 2개의 자식을 가질 수 있음. 높이가 h인 이진트리 노드의 최소 개수 : h+1개 노드의 최대 개수 : 2^(h+1) - 1 개 Node의 depth(깊이)와 height(높이) 노드의 depth란, 가장 아랫 노드인 leaf 노드와의 거리. 노드의 height란, 가장 상위 노드인 root 노드와의 거리. 이진 트리의 종류 Full Binary Tree 모든 레벨에 노드가 포화상태로 차 있는 이진 트리 최대의 노드 개수인 2^(h+1) -1개 Complete Binary Tree 높이가 h이고 노드 수가 n개일 때 Full Binary Tree의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트.. 2021. 7. 13. 2. Linked List - 파이썬 연결리스트 공부하기 Linked List 개별적으로 위치하고 있는 원소의 주소를 연결한 선형 자료구조 링크를 통해 워소에 접근하므로, 물리적인 순서를 맞추는 작업이 필요없음 자료구조의 크기를 동적으로 조정할 수 있어, 메모리의 효율적인 사용이 가능 탐색 - 순차탐색 O(n) 특정 노드 주변에서 삭제, 추출 - O(1) 주의할 점 head를 변경할 때 주의 연결리스트를 종주할 때, 찾으려는 값이 연결리스트에 없는 경우에 대한 생각 찾으려는 값이나 파라미터로 들어온 node가 head인 경우에 대한 생각 연결리스트로 스택 구현 2021.07.07 - [CS study/Data Structure] - 1. Stack - 파이썬 스택 공부하기 1. Stack - 파이썬 스택 공부하기 스택이란? 스택은 후입선출 (Last-In-Fi.. 2021. 7. 13. 이전 1 2 다음 LIST
