예니의 코딩일기

강의 "해시"는 해시 테이블(Hash table)에 인덱스 대신 키를 활용하는 알고리즘 입니다. key에 대한 value를 저장하는 칸을 해시 버킷(Hash bucket) 이라고 합니다. 다른 key의 value가 같은 해시 버킷에 지정되는 경우를 해시 충돌(collision) 이라고 합니다. Step 1-3: 풀어서 내 것으로 만들자! 완주하지 못한 선수 ⭐ 직관적 풀이 : 완주하지 못한 선수가 한명이기에 정렬을 이용하여 해결하는 방법! def solution(participant, completion): participant.sort() completion.sort() for i in range(len(participant)): if i > len(completion)-1: return partici..

lv1_예산_소팅 def solution(d, budget): d.sort(reverse = True) cnt = 0 while budget > 0 and d != []: budget -= d.pop() cnt += 1 if budget < 0: cnt -= 1 break return cnt lv2_기능개발 ⭐ 큐를 이용하는 문제! 이지만 포인터로 풀어본 문제! import math def solution(progresses, speeds): n = len(speeds) days = [0] * n for i in range(n): days[i] = math.ceil((100 - progresses[i]) / speeds[i]) print(days) dist = [] start = 0 end = 0 whi..

강의 "힙"은 root node가 언제나 최대 또는 최소인 완전 이진 트리를 만족하는 자료구조 입니다. 모든 subtree는 최대 힙을 만족하지만 다른 subtree와의 관계는 정의되지 않습니다. 특정 키 값을 가지는 원소를 탐색하는 것에는 적절하지 않습니다. 노드의 추가/삭제는 마지막 노드에서만 가능합니다. 연산 __init__() : 비어있는 힙 생성 insert() : 원소 삽입 remove() : 최대 원소 반환 및 제거 배열을 이용한 이진 트리 표현 node = m left child node = 2m right child node = 2m + 1 parent node = m // 2 최대/최소 힙의 응용 우선순위 큐 (Priority Queue) : 시간 복잡도 O(log n) 힙 정렬 (he..

강의 "이진 탐색 트리"는 left subtree의 모든 값이 root node의 값보다 작고 right subtree의 모든 값이 root node의 값보다 큰 이진트리 입니다. 이때, 중복되는 데이터는 없다고 가정합니다. 이진 탐색 트리는 데이터 검색에 이용할 수 있습니다. 배열을 이용한 이진 탐색과 다르게 원소의 추가와 삭제가 용이하지만 공간 소요가 크다는 단점도 있습니다. 노드를 (key, value) 쌍으로 표현합니다. 균형이 없는 이진 탐색 트리는 효율적이지 않기 때문에 이진 탐색을 사용하는 것이 낫습니다. 연산 insert(key, data) : 원소 추가 remove(key) : 원소 삭제 lookup(key) : 원소 검색 inorder() : key의 순서대로 원소 나열 class No..

강의 "트리" 는 node와 edge를 이용하여 데이터의 배치 형태를 추상화한 자료구조 입니다. 노드의 종류 Root node : 맨 위 시작 노드 Leaf node : 맨 아래 마지막 노드 Internal node : 그 외의 중간 노드 Parent node : root node에 더 가까운 쪽의 노드 Child node : leaf node에 더 가까운 쪽의 노드 Sibling node : 같은 parent node를 갖는 내가 아닌 노드 ancestor : parent node부터 root node까지 이어지는 모든 노드 descendant node : child node부터 leaf node까지 이어지는 모든 노드 노드의 수준(level)은 root node를 0으로 시작하여 거쳐온 edge의 개..

강의 "우선순위 큐"는 선입선출 방식이 아닌 우선순위에 따라 큐에서 빠져나오는 방식입니다. 예시로는 운영체제의 CPU 스케줄러가 있습니다. 구현 1. 방식 선택 Enqueue 할 때 우선순위 순서를 유지 : 시간적으로 유리함 Dequeue 할 때 우선순위 높은 것을 선택 2. 자료구조 선택 배열 : 공간적으로 유리함 연결 리스트 : 시간적으로 유리함 16강 실습: ⭐ 효율성을 높이는 함수를 선택하는 문제! class PriorityQueue: def __init__(self): self.queue = DoublyLinkedList() def size(self): return self.queue.getLength() def isEmpty(self): return self.size() == 0 def enq..