[학교 수업]

0. 들어가기 전2024.05.02 - [자료구조 및 알고리즘] - 자료 구조 및 알고리즘 9 - AVL Tree   1. 구현 앞서 글을 통해 삽입이나 삭제를 통해 불균형이 생기는 경우 어떻게 AVL Tree 가 균형을 맞출 수 있는지에 대해 알아봤습니다. 요약하자면, 크게 4가지 case 로 불균형이 생길 수 있는데LL caseLR caseRL caseRR case입니다. 위 4가지 case 에 대한 구현이 가장 중요한 점입니다.    2. Node 노드는 이전 노드들과 달리 BF, height 요소를 추가적으로 가집니다. (* 해당 요소들에 대한 설명은 이전 글에 자세히 설명했습니다.) 또한 이전 노드 클래스와 달리 reValuing() 이라는 함수도 갖고 있는데, 삽입이나 삭제 이후 변화가 생긴 ..

0. AVL Tree AVL 트리는 발명자의 이름인 Adelson-Velsky and Landis 에서 따온 이름으로 자가 균형 이진 탐색 트리입니다. 자가 균형 이진 트리는 스스로 균형을 잡는 트리라는 의미로 삽입, 삭제와 같이 데이터 균형이 달라질 것 같은 수행에서 스스로 균형을 맞추도록 트리의 구조를 바꿉니다. 일반적인 이진 탐색 트리와 달리 검색, 삽입, 삭제는 모두 평균과 최악의 경우 O(logN) 을 보장합니다.(* BST 의 경우 최악의 경우 O(N) 입니다.)2024.04.20 - [자료구조 및 알고리즘] - 자료구조 및 알고리즘 8 - Binary Search Tree    1. Definition 1.1 Height-balance property 높이 균형 성질은 트리 T 에 대해 모든..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Binary Search Tree Definition Node contains key which can make us identify from other nodes There is one Root node(unless empty BST, but if there is Dummy data in Root, we do not have to take care of it Root node may have "two" child node(s) Each child is the root node of its subtree Each subtree is itself a BST The key values in left subtree are all smaller t..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. LinkedList LinkedList 는 Node 들로 구성되어있는 자료구조입니다. 노드는 저장요소들의 단위로 노드들을 포인터를 통해 서로 연결되어있습니다. 그래서 연결 리스트라 불립니다. 연결 리스트의 구조는 다음과 같습니다. 연결 리스트에는 head 라는 포인터를 통해 처음 요소를 가르킵니다. 또한 마지막 노드의 next 포인터는 null 값을 가르킴으로써 마지막 요소임을 나타냅니다. #include class Node{ public: Node(int data) : data{data}, next{NULL}{}; ~Node(){ std::cout data == x) return 1; else if((*l)->data < x){ *p = ..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Definition of Equivalance Relation Given a set A, a Relation on A is any subset of AxA There is a Relation R which is a Relation on A. for example, A = {1,2,3,4} , R = {(1,3), (3,4), (1,1), (2,2)} We can write 1R3 to mean (1,3) ∈ R An extreme example There is a Relation '

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Queue and Stack 0.1 Queue Insert 와 Delete 만을 제공하는 자료구조 입니다. Queue 의 매우 주요한 특징으로는 FIFO(* First In First Out) 입니다. 앞서 봤던 Sorted Packed Array 같은 자료구조들과 달리 LinkedList 를 기반으로 합니다. LinkedList 의 특징을 통해 Queue 의 각 수행들은 매우 빠른 성능을 보입니다. 실제로 빨라야 하는 수행이기도 합니다. Queue 는 생각보다 많은 곳에 쓰이지는 않지만 알고있으면 유용한 순간들이 있습니다. 0.1.1 성능 Insert : O(1) Delete: O(1) 0.2 Stack Queue 와 마찬가지로 Inser..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. String Matching 긴 텍스트형식의 문자열에서 패턴을 찾아주는 것을 말합니다. 생각보다 실생활에 많이 쓰입니다. 워드에서 ctrl+F 를 통해 원하는 단어를 찾는 것웹 페이지에서 원하는 검색어를 갖는 페이지를 찾아주는 것생명공학에서 DNA 염기 서열 중 원하는 염기 서열을 찾아주는 것etc...String Matching 에 사용되는 용어들과 문제를 재정의 해보겠습니다. Text : Simple String of CharactersPattern : Simple String of Characters to findTo Do : Find where in the Text the Pattern is 0.1 알고리즘 알고리즘시간 공간Naive..

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다. 0. Array 배열에서 요소의 탐색(* Search), 삽입(* Insert), 삭제(* Delete)는 매우 중요한 이슈입니다. 이에 그 배열이 Packed 되었는지 Unpacked 인지, Sorted 되었는지 Unsorted 되었는지에 따라 SID 의 성능의 차이가 발생합니다. 이에 Packed 의 유무와 Sorted 의 유무에 따라 4 가지 경우의 Array 들을 따져보겠습니다. (* 편의를 위해 중복된 값은 허용하지 않는다고 가정합니다.) 1. Packed, Unsorted 아마도 가장 간단한 방법이 아닐까 싶습니다. index 0 1 2 3 4 5 6 value 5 2 3 8 11 1.1 Search 해당 배열이 정렬이 되어있지 않기 ..