루루의 우당탕탕 개발 스토리 루루의 우당탕탕 개발 스토리

1. 이진탐색 정의 데이터가 정렬돼 있는 배열에서 특정한 값을 찾아내는 알고리즘 배열의 중간에 있는 임의의 값을 선택하여 찾고자 하는 값 X와 비교 X가 중간 값보다 작으면 중간 값을 기준으로 좌측의 데이터들을 대상으로, X가 중간값보다 크면 배열의 우측을 대상으로 재탐색 선택된 배열의 중간값을 다시 선택하고 위 과정을 반복하여 해당 값을 찾을 때까지 반복 2. 이진탐색 예시 ex) { 17, 28, 43, 67, 88, 92, 100 } , target = 43 2-1. arr = { 17, 28, 43, 67, 88, 92, 100 }, mid = 67 가운데에 위치한 67을 기준으로 43은 67보다 작다. 그렇다면 다음의 배열은 67보다 한칸 앞에 있는 것까지로 한다. 2-2. arr = { 17,..

1. Binary Search Tree (BST) 개념 - 각 노드가 최대 두개의 자식을 갖는 탐색 트리이다. - 왼쪽 자식은 부모보다 키 값이 작고, 오른쪽 자식은 부모보다 키 값이 크다. - 검색 목적 자료구조이므로 모든 노드는 유일한 키를 갖게 됨 - 부모 노드의 왼쪽과 오른쪽 서브트리도 이진 탐색 트리 - 시간복잡도 : O(logn) ex) key = [8, 3, 10, 1, 6, 14, 4, 7, 13] - 이진 탐색 트리는 하나만 존재하는 것이 아닌 여러 개 존재할 수도 있음 2. Binary Search Tree (BST) 검색 및 삽입 방법 검색 타겟 데이터가 존재하는 지 찾고자하는 값과 현재 루트 노드의 값 비교 → 타겟 값이 더 크다면 오른쪽 서브 트리로 → 타겟 값이 더 작다면 왼쪽 ..