데굴데굴

min-heap data structure 이진 트리를 기반으로 한 자료구조 부모 노드가 자식들보다 작거나 같은 구조 가장 작은 값이 부모 노드에 위치하는 자료구조 우선순위 큐 구현, Heap Sort에도 활용된다. 가장 작은 값을 `O(1)`의 시간으로 빠르게 찾을 수 있다는 장점이 있다. 다음은 자바스크립트로 최소 힙을 구현하는 코드이다. class MinHeap { constructor() { this.heap = []; } push(value) { this.heap.push(value); this.heapifyUp(); } pop() { if (this.isEmpty()) return null; const root = this.heap[0]; const lastNode = this.heap.pop..

공부자료: 신찬수 교수님 '자료구조' 재생목록 자료구조 - 균형이진탐색트리 - 정의와 회전 - YouTube 이진탐색트리의 연산시간을 빠르게 하기 위해서는 트리의 높이를 최대한 작게 유지하는 것이 좋다. 여러 값이 추가되거나 삭제되더라도 높이를 O(log n)으로 유지할 수 있는 트리를 '균형이진탐색트리'라고 한다. 균형이진탐색트리의 종류는 세 가지가 있다. AVL 트리 Red Black 트리 Splay 트리 삽입과 삭제 연산을 수행하여 트리의 높이가 변할 때에는 높이를 O(log n)으로 유지할 수 있도록 높이를 조절해야 한다. 그리고 이는 rotation이라는 기본 연산으로 이루어진다. 왼쪽으로 회전하는 방법과 오른쪽으로 회전하는 방법 두 가지가 있다. rotation을 한 후에도 값의 순서가 이진탐..

공부자료: 신찬수 교수님 '자료구조' 재생목록 자료구조 - 이진트리 - 정의와 순회 - YouTube 자료구조 - 이진트리 - 이진탐색트리 정의와 탐색, 삽입 연산 - YouTube 자료구조 - 이진트리 - 이진탐색트리 삭제 연산 - YouTube 이진트리: 자식 노드를 최대 두 개까지만 갖는 트리 힙에서 배웠던 세 가지 표현법 중 노드로 표현하는 법을 사용한다. 한 노드에 부모 노드와 오른쪽 자식노드, 왼쪽 자식노드를 가리키는 링크를 추가한다. 순회 traveral - 이진트리 노드의 key 값을 빠짐없이 출력하는 방법 - 노드의 key 값에 모두 일정한 값을 더하거나 빼고 싶을 때, 값을 하나씩 전부 출력하고 싶을 때 순회가 필요하다. 순회 방법에는 세 가지가 있다. 부모 노드를 M이라 하고 이를 기..

공부자료: 신찬수 교수님 '자료구조' 재생목록 자료구조 - 트리구조 소개 - YouTube 자료구조 - 힙 (heap) 정의 - YouTube 자료구조 힙 (heap) make_heap 연산 - YouTube 자료구조 힙 (heap) - insert와 delete_max 연산 - YouTube *별도로 출처가 표기되지 않은 이미지는 직접 제작한 것 트리(tree): 부모-자식 관계를 계층적으로 표현한 자료구조 이진트리(binary tree): 부모 노드에 자식 노드가 최대 2개까지만 존재하는 자료구조, 두 개 이상의 노드가 올 수도 있지만 이진트리가 가장 많이 쓰임. 힙(heap): 특정 조건을 만족하는 이진트리 Tree Data Structures by C.Barkin Ozer | Medium 노드와 ..

해시에 대한 자세한 내용은 이전 포스팅을 참조바람 해시테이블 Hash Table과 Open Addressing (tistory.com) 해시테이블 Hash Table과 Open Addressing 공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 해시테이블 - 소개, 해시 함수 - YouTube 자료구조 해시테이블 - open addressing (linear probing) - YouTube 해시테이블은 데이터를 읽고 쓰는 haruisshort.tistory.com 공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 해시테이블 - 성능평가, chaining - YouTube Chaining 해시테이블의 충돌 회피 방법 중 하나. 각 slot에 한방향 연결리스트를 만든다. 값이 중..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 해시테이블 - 소개, 해시 함수 - YouTube 자료구조 해시테이블 - open addressing (linear probing) - YouTube 해시테이블은 데이터를 읽고 쓰는데 훨씬 빠른 속도를 자랑한다. CS50에서 배웠던 내용을 살짝 정리해보면 이렇다. 해시 (CS50 강의 참고) 해시는 '연결 리스트의 배열'. 여러 값들을 바구니에 나눠 담는다고 가정할 때, 각 값들은 '해시 함수'를 통해서 어떤 바구니에 담길지 결정된다. 그럼 이 해시 함수는 무슨 기준으로 값을 분류하는가? 이는 명확하지 않다. 맨 첫 글자일수도 있고, 앞에 두 글자일수도 있고.. 값이 어떠느냐에 따라 다른 해시 함수를 선택한다. 이상적인 해시 함수는 각 바구니..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 양방향연결리스트 삽입-삭제-탐색 연산 - YouTube 양 끝이 연결된 원형 양방향 연결리스트 Circularly Doubly Linked List로 관리하면 편하다. 빈 노드 = 더미노드 dummy node를 head 노드로 설정한다. (더미노드의 key 값은 None) 즉 양방향 연결리스트의 초기 상태에서 더미노드는 자기 자신을 가리킨다. splice 연산 splice(a, b, x): a부터 b까지를 잘라 x 다음에 넣는다. splice 연산을 위한 전제조건 1. a -> ... -> b 2. a와 b 사이에 head node가 있으면 안 됨. 3. a와 b 사이에 x 노드가 있으면 안 됨. def splice(self, a, b, x)..

공부자료: 신찬수 교수님 유튜브 '자료구조' 재생목록 자료구조 연결리스트 소개 - YouTube 자료구조 한방향연결리스트 - 삽입, 삭제 연산 - YouTube 자료구조 한방향연결리스트 - 탐색 연산 - YouTube 배열과는 달리 메모리상에서 흩어져 있음. 실제 데이터값(key)과 값이 저장된 곳의 주소(link)로 구성된 쌍(key, link), 즉 하나의 노드 node를 갖고 있어야 함. 가장 앞에 있는 노드는 헤드노드 head node 배열은 인덱스가 주어지면 상수시간 O(1) 내에 인덱스에 있는 값을 바로 알 수 있다는 것이 장점 연결리스트는 그렇지 않음. 하지만 배열은 값을 삽입하거나 삭제할 때 나머지 값에서 인덱스의 이동이 발생함. 최악의 경우에는 O(n)이 듦. 연결리스트에서는 link만 ..