전체 글

[알고리즘] 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) 오퍼레이션 이기 때문에 선형 데이터 구조보다 빠른 검색을 가능하게 하고, 데이터를 삽입하거나 지울 수 있게 해주는 데이터 구조입니다. 이진 탐색 트리가..

[알고리즘] Binary Tree 이진 트리: 기본정리 - in-order 중위순회, pre-order 전위순회, post-order 후위순회 구현 - Kotlin

목차 이번 포스트에서는 이진 트리에 대해서 알아보겠습니다. 이진 트리를 알아보기전, 트리의 용어와 익숙하시지않으시다면 아래 포스트를 먼저 보고와주세요. [알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTra 목차 Tree 개념 Tree는 데이터 구조중 하나입니다. 1. 계층구조의 관계를 가진 데이터 구조이고 2. 정리되어 나열된 데이터를 다룰 때 검색이 빠릅니다. 3. Tree에는 사이즈, 모양이 다른 여러 tree들 underdog11.tistory.com 이진 트리 개념 이진 트리는 트리와 같지만 최대 2개의 자식만 가질 수 있는 트리구조입니다. 자식 두 개의 왼쪽을 LeftChild 오른쪽을 rightChild..

[알고리즘] Tree 트리 : 기본정리 - 트리 구성, 깊이우선순회(Depth-First Traversal), 레벨순회(LevelOrderTraversal), 검색(Search) - Kotlin

목차 Tree 개념 Tree는 데이터 구조중 하나입니다. 1. 계층구조의 관계를 가진 데이터 구조이고 2. 정리되어 나열된 데이터를 다룰 때 검색이 빠릅니다. 3. Tree에는 사이즈, 모양이 다른 여러 tree들 이 있습니다. 4. 트리는 노드들과 노드들을 연결하는 링크로 구성되어있습니다. Tree 구성 및 용어 우선 시작하기에 앞서 tree에 구성과 용어들을 살펴보겠습니다. 용어 설명 다이어그램 Node LinkedList와 비슷하게 tree에도 node가 있습니다. 각 node는 데이터를 포함하고있습니다. Parent(부모) / Child(자식) 부모노드는 다수의 자식 노드를 가지고있을수있습니다. 하지만 자식 노드는 하나의 부모만 가지고있을수있습니다. 루트 노드(Root) 트리에 가장 상단에 위치한..

[알고리즘] Queue 큐: 기본정리 - DoublyLinkedList(이중연결 리스트), Ring Buffer(원형큐),ArrayList, Stack으로 Queue 구현하기 - Kotlin

목차 Queue 개념 큐는 영화티켓을 사기 위해 기다릴 때, 롤 큐를 기다릴 때처럼 실생활에 적용되는 사례가 많습니다. 이 큐의 특징은 선입선출(FIFO: 먼저 들어온 것이 먼저 나가는 형태)이라는 것입니다. Queue 인터페이스 구현 큐에 인터페이스를 만들어보겠습니다. interface Queue{ fun enqueue(element: T): Boolean fun dequeue():T? val count: Int get val isEmpty: Boolean get() = count == 0 fun peek(): T? } 위에 4가지에 키 함수가 있습니다. enqueue: 맨뒤에 큐에 element를 삽입해준 후 성공하면 true를 반환합니다. dequeue: 큐에 가장 앞부분에 element를 지우고 ..

[티스토리] 코드블럭 편집하기 완결판 - 라인넘버 추가, 숫자추가, 폰트추가, 테마, 글자크기, 코드블럭 모서리 편집

목차 개요 우선 티스토리에서 기본적으로 제공하는 코드 블록 플러그인을 사용 시 코드 크기도 작고 모서리도 편집 못하고, 라인 넘버도 없어서 많은 디자인적인 제약이 있습니다. 그래서 이번포스트에서는 아래와 같이 커스텀 된 코드 블록 테마를 티스토리에 적용해보겠습니다. class MainActivity : AppCompatActivity() { val TAG = "MainActivity" override fun onCreate(savedInstanceState: Bundle?) { super.onCreate(savedInstanceState) setContentView(R.layout.activity_main) } 필요한 Highlight 파일들 업로드 2가지 파일을 티스토리에 업로드해야합니다. 1. hig..

[알고리즘] Stack 스택: 기본정리 - pop, push, peek, count - Kotlin

목차 스택 자료구조 개념 스택은 아이템을 쌓아 올리는 구조입니다. 제거할 때도 가장 위에 있는 아이템부터 제거하게 되고 추가할 때도 위에서부터 추가합니다. 그래서 스택에는 2가지 동작이 있습니다. 1. push: 스택에서 가장 위에 element를 추가합니다. 2. pop: stack에 가장 위에 있는 element를 제거합니다. 이 의미는 한쪽에서만 데이터를 추가하고 제거할 수 있다는 뜻입니다. 우리는 이러한 stack 구조를 LIFO(last-in-first-out - 가장 마지막으로 추가한 게 가장 먼저 나가는 구조)라고 부릅니다. 스택을 코드로 표현하면 아래와 같습니다. interface Stack { fun push(element:Element) fun pop(): Element? } 스택은 프..