개발공부/Algorithm

[알고리즘] Heap 힙 데이터구조 : 필수 기본정리 - Min Heap, Max Heap, 삽입, 제거, 탐색 구현

목차 힙(Heap) 개념 힙은 우선 우선순위의 개념을 대입한 자료구조입니다. 전포스트에서 다뤘던 Stack,Queue와 같이 자료가 들어오고 나가는 순서를 정할수있습니다. 우선순위개념과 Stack Queue에대하여 자세히 알고싶으시다면 아래 포스트를 참고해주세요. [알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin 목차 스택 자료구조 개념 스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이 underdog11.tistory.com [알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐)..

[알고리즘] Binary Search 이진 탐색 : 필수 기본 정리 - 장점, Kotlin 구현

목차 이진 탐색 Binary Search 이진 탐색은 가장 효율적인 탐색 알고리즘 중 하나입니다. Big O에서 O(log n)으로 나타냅니다. 균형 이진 탐색 트리(Balanced Binary Search Tree)에서 element를 찾는 것과 비슷한 구조를 가지고 있습니다. 만약 시간 복잡도와 이진 탐색 트리에 대하여 더 알고 싶으시다면 아래 링크를 확인해주세요. [알고리즘] Binary Tree 바이너리 트리: 기본정리 - 바이너리트리 구현, 중위순회, 전위순회, 후위순 목차 바이너리 트리 개념 바이너리 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild로 부릅니다. 바이너리 트리 구현하기 underdog11...

[알고리즘] Tries 트라이 자료구조 : 필수 기본 정리 - 구조, 장점, 삽입 Insert, 포함여부 contains, 제거 remove - Kotlin 구현

목차 Trie 자료 구조 개념 우리가 구글 엔진에서 방대한 자료 중 검색어를 찾을 때 위와 같이 뒤에 올 연관 검색을 찾아주거나, 사전에서 단어 검색을 할 때 자동완성시켜줄 때처럼 Trie는 문자열을 저장하기 위해 가장 효율적인 자료구조입니다. Trie 자료구조를 그림으로 나타내보겠습니다. springBoot, springCloud, springMvc sports라는 문자열들을 저장한다고 가정합시다. 그리고 springBoot를 검색할 때 node에 있는 character하나하나씩 접근하면서 문자열을 찾게 됩니다. 우리가 사전에서 단어를 찾을 때와 비슷한 메커니즘입니다. 한 글자씩 찾아가며 문자열에 도달합니다. Trie 자료 구조의 장점 words라는 Array에 몇 개의 단어가 있다고 가정해봅시다. c..

[알고리즘] AVL Tree(트리) : 필수기본정리 - Balanced Factor, 4가지 Rotation(회전), 삽입, 제거, Kotlin구현

목차 AVL 트리 개념 우선 AVL 트리는 이진 탐색 트리를 기초로 합니다. 이진 탐색 트리에 대하여 자세히 알고 싶으시다면 아래 링크를 확인해주세요 [알고리즘] Binary Search Tree 이진탐색 트리 : 기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 - Kotlin 목차 이진 탐색 트리(BSF - Binary Search Tree) 이진 탐색 트리는 시간 복잡도에서 log(n) 오퍼레이션 이기 때문에 선형 데이터 구조보다 빠른 검색을 가능하게 하고, 데이터를 삽입하거나 지울 수 있게 underdog11.tistory.com 위 포스트를 보셨다면 이진 탐색트리의 단점은 불균형한 트리 모형을 하고 있을 때 트리의 성능이 O(log n)에서 O(n)으로 떨어진다는 것을 알 수 있었습니다. AVL..