분류 전체보기

[알고리즘] 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..

[알고리즘] Binary Search Tree 이진탐색 트리 : 필수기본정리 - 탐색,삽입,삭제, 검색연산, 삭제연산 - Kotlin

목차 이진 탐색트리를 알아보기전 이진트리와 익숙하시지않으시다면 아래 포스트를 참고해주세요. [알고리즘] Binary Tree 바이너리 트리: 기본정리 - 바이너리트리 구현, 중위순회, 전위순회, 후위순 목차 바이너리 트리 개념 바이너리 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild로 부릅니다. 바이너리 트리 구현하기 underdog11.tistory.com 이진 탐색 트리(BSF - Binary Search Tree) 이진 탐색 트리는 시간 복잡도에서 log(n) 오퍼레이션 이기 때문에 선형 데이터 구조보다 빠른 검색을 가능하게 하고, 데이터를 삽입하거나 지울 수 있게 해주는 데이터 구조입니다. 이진 탐색 트리가..