개발공부/Algorithm

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