분류 전체보기115 이진탐색(이분탐색)알고리즘 BinarySearchTree와 이진탐색 모두 조회에 있어 O(logN)의 성능을 보인다. 그러나 삽입&삭제 연산의 성능이 다르다. BST vs 이진탐색 알고리즘 성능비교 이름 조회 삽입 삭제 BST O(logN) O(logN) O(logN) 이분탐색 O(logN) N N 이진탐색 알고리즘(선형 자료구조)의 한계 이진탐색 알고리즘의 전제조건은 "데이터가 정렬되어 있어야한다" 라는 것이다. 이진탐색을 하기 위해서는 인덱스 접근을 빠르게 해야하므로 배열리스트를 이용할 수 밖에 없다. 배열 리스트에서의 데이터 삽입은 데이터들을 뒤로 밀어야하므로O(N)이다. 따라서 이진탐색 알고리즘(선형자료구조)에서의 삽입&삭제는 모두O(N)이다. 2021. 5. 30. 이진탐색 알고리즘 조회과정 정렬되어 있는 배열에서 특정한 값을 O(log N)에 찾는 알고리즘 이진탐색 알고리즘은 탐색범위의 중간값과의 비교를 통해, $\frac12$씩 탐색범위를 계속 좁혀가는 방식으로 탐색한다. 성능 한번의 연산마다 $\frac12$씩 탐색범위를 줄여 탐색범위를 1로 만드는 과정이다 n개의 데이터의 탐색범위를 1로 만들기 위해 k번의 비교연산을 한다고 생각해보자 아래와 같은 수식으로 표현된다 n개의 데이터에서, 1개 데이터 찾기위한 연산횟수 k $$n\times\frac12^k = 1$$ $$n = 2^k$$ $$log_2n = k$$ 따라서, n개의 데이터에서 1개의 데이터를 찾기위한 이진탐색의 연산횟수는$log_2n = k$번이며, 이것이 빅-오 노테이션 성능이다. 구체적인 탐색 과정 다음의 데이터에서 46.. 2021. 5. 29. BST 일반적인 삽입 과정 다음과 같은 BST에 50이라는 데이터를 삽입하려 한다. 삽입과정은 매우 재귀적이다 성능 트리의 밸런스가 잘 맞을 경우 → O(logN) 트리의 편향이 심할 경우 → O(N) 삽입 과정 •삽입하려는 노드와 루트노드를 비교한다 •삽입하려는 노드가 더 크다 → 오른쪽 서브트리에 반복(=재귀) •삽입하려는 노드가 더 작다 → 왼쪽 서브트리에 반복 (=재귀) 이 과정에서 서브트리가 비어있다면, 그 위치에 삽입한다 → 50이 더 크다. 그러므로 오른쪽 서브트리에 이 과정을 반복한다 → 50이 더 크다. 마찬가지로 오른쪽 서브트리에 반복한다 → 50이 더 작다. 왼쪽 서브트리에 반복한다 → 그런데 왼쪽 서브트리가 비어있다 → 왼쪽 노드로 삽입한다 → 완료 2021. 5. 29. BST 성능 = 높이 아래 이진탐색트리(BST)를 보고, 조회성능에 대해 생각해보자. 결과적으로 말하자면, 밸런스가 맞춰져 있다면 O(logN) 의 성능을 보이고, 편향된 정도가 심할수록 O(N)의 성능을 보인다. 편향된 BST = 리스트 ?? 이상하게 보일지 모르겠으나, 12를 루트노드로 갖는 BST라고 볼 수 있다 58을 찾기 위해선, 11번의 연산이 필요하다. 44를 찾기 위해선, 8번의 연산이 필요하다. 현재 조회과정은 O(N)의 성능을 보이며 결과적으로, [리스트] 자료구조 조회와 전혀 다를바가 없다! BST가 편향될 수록, 조회성능이 점점 O(N)에 수렴하게 된다. 밸런스가 맞춰진 BST의 성능 똑같은 데이터로 조금 다른 BST를 만들어보면 어떻게 될까? 58을 찾기 위해선 4번의 연산이 필요하다 44를 찾기 위해.. 2021. 5. 29. Binary Search Tree 조회 과정 BST 조회 과정 다음의 BST에서 41데이터를 찾는 과정을 살펴보자 성능 트리의 높이가 n 이라면 노드의 개수는 (2^n)-1 트리의 밸런스가 잘 맞을 경우 → O(logN) 트리의 편향이 심할 경우 → O(N) BST 성능 = 높이 조회 과정 41를 찾는다고 가정해 보자 노드와 비교해 41이 더 크면, 오른쪽 서브트리로 이동시키고 노드와 비교해 41이 더 작으면, 왼쪽 서브트리로 이동시킨다(재귀적) 데이터를 조회하는 과정에서 4번의 연산이 소요됐다. 한번에 한칸씩 내려가면서 결국 끝까지 가면 어떤 데이터든 찾을 수 있게 된다. 따라서, Binary Search Tree(BST)에서는 트리의 높이가 최대한 작아야 한다. 왜냐하면 트리의 높이가 곧, 조회성능과 비례하기 때문이다. 2021. 5. 29. Full Binary Tree vs Complete Binary Tree 2021. 5. 29. 트리의 순회 inorder(node) if node.left ≠ null then inorder(node.left) print node.value if node.right ≠ null then inorder(node.right) 대표적으로 3가지 순회 방법이 있다 전위 순회(preorder) 전위 순회의 방법 1. 노드를 방문한다. 2. 왼쪽 서브 트리를 전위 순회한다. 3.오른쪽 서블 트리를 전위 순회한다. 전위 순회는 깊이 우선 순회(depth-first traversal)라고도 한다. public void preorder(Node node){ System.out.println(node.value); if(node.left != null){ preorder(node.left); } if(node.right != .. 2021. 5. 29. 이진 탐색 트리(Binary Search Tree) 정렬된 상태로 데이터를 보관하는 이진트리 (binary tree) 이진탐색트리(Binary Search Tree)는 이진트리에서 다음의 규칙이 추가된 트리를 말한다. 모든 node에서 left child node가 자신보다 작고, right child node가 자신보다 크다 2021. 5. 29. HashMap과 LinkedHashMap HashMap은 쌍으로 저장할수 있는 자료구조이다. 하지만 단점이 있다 put을 이용해 데이터쌍을 삽입할때 삽입 순서가 지켜지지 않는다. 경우에 따라 순서가 보장되어야 할 때가 있고 그렇지 않을 때가 있다. 순서가 보장되어야 한다면 LinkedHashMap을 사용하면 된다. 예를들어 HashMap map = new LinkedHashMap(); //map을 Integer형 key배열로 변환한다. Integer key[] = map.keySet().toArray(new Integer[map.size()]); //map에 1,2,3 이차례로 들어갔다고 가정하면 key[0] = 1 ,key[1]=2,[key[2] = 3; 이된다. //그냥 HashMap을 사용하면 이순서가 지켜지지 않는다. HashMap ma.. 2021. 5. 15. 이전 1 2 3 4 5 6 ··· 13 다음
