본문 바로가기

알고리즘17

13-1강. 해슁(Hashing) 1 SUHA(Simple Uniform Hashing Assumption) - 각각의 키가 모든 슬롯들에 균등한 확률로() 독립적으로(independently) 해슁된다는 가정 => 사실 현실적이지 않다. - 성능분석을 위해서 주로 하는 가정일 뿐 - hash 함수는 deterministic하므로 현실에서는 불가능하다 - Load factor alpha = n/m: - n : 테이블에 저장될 키의 갯수 - m : 해쉬테이블의 크기, 즉 연결리스트의 깃수 - 각 슬롯에 저장된 키의 평균 갯수 - 연결리스트 T[j]의 길이를 Nj라고 하면, E[Nj] = alpha - 만약 n = O(m)이면 평균검색시간은 O(1) 2020. 11. 24.

12-2강. 레드블랙트리 (3) RB-DELETE(T, z) // T: Binary Search Tree, z : 삭제할 노드 if left[z] == nil[T] or right[z] == nil[T]// 자식이 없거나, 자식이 하나거나 then y 2020. 11. 22.

12-1강. 레드블랙트리(1) 문제 상황 : 현실세계에서는 완벽하게 정렬된 Binary Search Tree는 찾기 힘들다. 오른쪽으로 극단적으로 치우친 경우가 존재할 수 있다. 보완 방법 : 레드블랙트리(Red-Black Tree)는 이를 보완하기 위해 등장했다. 완벽하게 트리의 균형을 맞출 수는 없으나, 어느정도 보완을 가능하게 한다. INSERT, DELETE 알고리즘을 적절하게 수정했다. 레드블랙트리 - 이진탐색트리의 일종 - 균형 잡힌 트리 : 높이가 O(log2n) - SEARCH, INSERT, DELETE 연산을 최악의 경우에도 O(log2n) 시간에 지원한다. - 각 노드는 하나의 키(key), 왼쪽자식(left), 오른쪽 자식(right), 그리고 부모노드(p)의 주소를 저장한다. - 자식노드가 존재하지 않을 경우,.. 2020. 11. 17.

11-3강. 이진검색트리 (Binary Search Tree) 지난 강의 공부 내용... 이진검색트리의 탐색, 삽입 이진검색트리/이진탐색트리의 삭제 Case 1 : 자식노드가 없는 경우 -> 해당 노드를 그냥 삭제한다. Case 2 : 자식노드가 1개인 경우 -> 자신의 자식노드를 원래 자신의 위치로 보낸다. Case 3 : 자식노드가 2개인 경우 -> 해당 노드의 자리는 그대로 두고, 데이터만 삭제한다. 그리고 해당 노드와 가자아 가까운 값인 다른 노드를 해당 자리로 가져 온다. 그 다른 노드는 삭제하려는 노드의 successor이다. 삭제하려는 노드의 successor는 최대 1개의 자식노드를 가진다. TREE-DELETE(T, z)// z : 삭제할 노드 { if left[z] == null or right[z] == null then y 2020. 11. 15.

제11-1강. 이진검색트리(Binary Search Tree) 이진검색트리(Binary Search Tree) - 여러 개의 키(key)를 저장 - 다음과 같은 연산들을 지원하는 자료구조 INSERT - 새로운 키의 삽입 SEARTCH - 키 탐색 DELETE - 키의 삭제 ex) 심볼테이블 search insert delete 배열 정렬된 경우 O(logn) O(n) O(n) 정렬되지 않은 경우 O(n) O(1) O(1) 연결리스트 정렬된 경우 O(n) O(n) O(1) 정렬되지 않은 경우 O(n) O(1) O(1) 다양한 방법들 - 정렬된, 혹은 정렬되지 않은 배열 혹은 연결리스트를 사용할 경우 INSERT, SEARCH, DELETE 중 적어도 하나는 O(n) - 이진탐색트리(Binary Search Tree), 레드-블랙트리(red-black tree), A.. 2020. 11. 10.

제 10강 트리와 이진트리 트리 (Tree) 계층적인 구조를 표현하는 데 사용한다. 예를 들면 조직도나 디렉토리와 서브디렉토리의 구조를 표현할 때, 가계도를 표현할 때 쓴다. 트리는 노드(node) 들과 노드들을 연결하는 링크(link)들로 구성된다. 루트(root) : 맨 위의 노드 링크(link) : 노드들을 연결하는 선 (=edge, branch) 트리의 부모-자식 관계 트리 구조 상에서 상대적으로 위에 있는 노드를 부모 노드라 하고, 아래에 있는 노드를 자식 노드라 한다. 트리의 형제 관계 부모가 동일한 노드들을 형제(sibling) 관계라고 한다. 루트 노드를 제외한 트리의 모든 노드들은 유일한 부모 노드를 가진다. 리프노드 자식이 없는 노드들을 리프(leaf) 노드라 한다. 리프노드가 아닌 노드들을 내부(internal.. 2020. 11. 8.

9강. Java에서의 정렬 - Arrays 클래스가 primitive type의 데이터를 위한 정렬 메서드를 제공한다. int[] data = new int[capacity]; // data[0]에서 data[capacity-1]까지 데이터가 꽉 차있는 경우에는 다음과 같이 정렬한다. Arrays.sort(data); //배열이 꽉 차있지 않고, data[0]에서 data[size-1]까지 size개의 데이터만 있다면 다음과 같이 정렬한다. Arrays.sort(data, 0, size); - int 이외의 다른 primitive type 데이터(double, char 등..)에 대해서도 제공한다. Primitive type 데이터와 마찬가지로 Arrays.sort() 메서드로 정렬된다. // fruits라는 이름의 배열 선언과 .. 2020. 11. 5.

10. 합병정렬 (merge sort) - 분할정복알고리즘(Divide and Conquer) 그냥 말 그대로, 배열을 분할하고, 해결하고, ... 이를 반복하는 알고리즘이다. 1. 분할 : 해결하고자 하는 문제를 작은 크기의 동일한 문제들로 분할 2. 정복 : 각각의 작은 문제를 순환적으로 해결 3. 합병 : 작은 문제의 해를 합하여(merge), 원래 문제에 대한 해를 구함 대표적인 분할정복알고리즘에는 합병정렬(merge sort)과 퀵정렬(quick sort)이 있다. 분할은 하나의 큰 문제를 각자 작은 문제로 나누는 것이다. 이 각각의 작은 문제들은 원래 문제와 동일한 문제여야 한다. 정복이라는 의미는 각각의 작은 문제를 해결하는 것이다. 위의 그림은 합병정렬을 간단하게 표현한 예이다. 예를 들어 위의 배열에서 최댓값을 구하는 문제를 .. 2020. 10. 15.

이전 1 2 다음

티스토리툴바