반응형 전체 글340 [알고리즘] Tree - 레드 블랙 트리(Red Black Tree) - 1 Tree - 레드 블랙 트리(Red Black Tree) - 1 앞서 본 이진 탐색 트리의 기본연산 3가지(Insert, Search, Delete)가트리의 높이에 비례하는 시간복잡도를 가지고 있었다.이때, 극단적으로 비대칭 적이며 높이가 높은 트리에서는 그 효율이 높지 않다. 따라서 이진 탐색 트리의 구조를 유지하며 안정성도 살리는 트리가 필요해졌다.이 들 중 하나가 레드 블랙 트리이다. 레드 블랙 트리는 이진 탐색 트리의 일종이다.이진 탐색 트리에서 Insert와 Delete 알고리즘을 적절하게 수정하여이진 탐색 트리임에도 불구하고 트리의 높이에 상관없이 O(logN)의 시간복잡도를 유지해준다. 레드 블랙 트리의 형태는 다음과 같다.1) 각 노드는 하나의 키(key), 왼쪽 자식 노드, 오른쪽 자식 .. 2017. 4. 19. [알고리즘] Tree - 이진 검색 트리 - 3 Tree - 이진 검색 트리 - 3 이어서 delete 연산이다.delete가 3개의 연산중에 가장 복잡한데, 경우에 따라 연산이 다르기 때문이다. 첫번째는 자식이 없을 때이다.자식이 없을 때는 노드를 그냥 삭제한다. 두번째는 하나의 자식이 있는 경우이다.이 경우는 링크드 리스트에서 가운데 값을 하나 삭제하는 것과 비슷하므로간단하게 처리할 수 있다.7을 삭제하고 노드 6의 포인터를 13을 가리키도록 해주면 된다. 마지막으로 자식을 둘인 노드를 삭제하는 경우이다.이것이 delete 연산의 가장 복잡한 경우이다 노드 13을 삭제하는 경우, 13을 그냥 없애 버리면 자식 노드의 부모가 없어지므로 노드 13의 저장된 데이터(13)만 삭제한다. 이후에 없어진 데이터의 successor를 삭제된 부분으로 옮겨온다... 2017. 4. 19. [알고리즘] Tree - 이진 검색 트리 - 2 Tree - 이진 검색 트리 - 2 12345TREE-MINIMUM(x){ while left(x) != null do x 2017. 4. 19. [알고리즘] Tree - 이진 검색 트리 - 1 Tree - 이진 검색 트리 - 1 검색 트리라는 것은 트리라는 자료구조를 이용하여순회하며 데이터를 검색하는 것이다. 트리는 계층적인 구조를 가지고 있으나,검색트리는 일종의 컨테이너나 집합이라고 볼수있다.따라서 이를 다이나믹 셋(dynamic set)이나 딕셔너리(dictionary), 검색 구조(search structure)라고도 부른다.데이터들이 고정되지 않고 새로운 데이터의 추가/삭제가 가능한것이 특징이다. 다이나믹 셋의 조건은 다음과 같다.여러개의 키를 저장하고 있으면서insert/search/delete가 가능하다. 연결리스트와 배열을 정렬되어지거나 정렬되어지지 않거나에 대한비교는 위의 표와 같다. 연결 리스트나 배열을 썼을 때, 위의 표에서 알수 있는 점은search, insert, dele.. 2017. 4. 19. [알고리즘] Tree - 트리와 이진트리 Tree - 트리와 이진트리 트리라는 것은 쉽게 말해 계층적인 구조를 표현하기 위해서사용하는 것이다.일반적으로 조직도나 가계도, 파일 시스템 등에서 많이 사용된다. tree에서 각각의 노드(node)라고 하며, 노드에서 뻗어나오는 가지를 링크(link)라고한다.그리고 맨 꼭대기에 있는 노드를 루트(root)라고한다.마지막으로 마지막 레벨의 노드를 리프(leaf) 노드 라고한다. 또한 상위계층의 노드를 부모 노드 라고 하며하위계층을 자식 노드 라고 하는데 이 명칭은 상대적이다.예를 들어, 어떤 노드의 자식노드가 상대적으로 부모 노드가 될수있다는 것이다.따라서 부모가 없는 노드를 루트 노드 라고 하거나, 자식이 없는 노드를 리프 노드 라고 할수도 있다.2단계 상위 노드를 조상(ancestor), 하위 노드를.. 2017. 4. 19. [알고리즘] Sort - Java에서의 정렬 (Sort in java) Sort - Java에서의 정렬 (Sort in java) 정렬 알고리즘에 대한 이야기가 아닌 실생활에서 쓰이는것에 대해 말해보자실제로 정렬알고리즘은 기초적이고 매우 많이 사용 되기 때문에직접 구현하지 않고 제공되는 경우가 많다.따라서, 가장 많이 사용하는 Java를 예로 들어 정렬의 사용법에 대해 알아보자 1234567int[] data = new int [capacity];// data[0]에서 data[capacity-1]까지 데이터가 꽉// 차있는 경우에는 다음과 같이 정렬한다.Arrays.sort(data);// 배열이 꽉 차있지 않고 data[0]에서 data[size-1] 까지 // size개의 이터만 있다면 당음과 같이 한다.Arrays.sort(data,0,size);Colored by .. 2017. 4. 19. [알고리즘] Sort - Radix sort와 정렬의 속도 비교 Sort - Radix sort와 정렬의 속도 비교 이어서 다음 non-comparison sort중 하나인 radix sort를 알아보자 radix sort의 조건은1) n개의 d 자리 정수들2) 가장 낮은 자리수부터 정렬이다. 위의 그림이 직관적으로 표현이 되어있는데각 자릿수를 비교하며 정렬을 진행하게 된다.여기서 중요한 것은 자릿수로 정렬을 진행할 때 다른 자리는 생각하지 않는 다는 것이다. 12345RADIX-SORT(A,d){ for i 2017. 4. 19. [알고리즘] Sorting in leanar time(선형시간 알고리즘) Sorting in leanar time(선형시간 알고리즘) 앞서 보았던 예제를 제외한 정렬 알고리즘을 보자. 먼저 count 알고리즘이다.count 알고리즘의 조건은 다음과 같다.1) n개의 정수를 정렬하라(단, 모든정수는 0에서 n사이의 정수이다.)예) n명의 학생들의 시험 점수를 정렬하라. 단 모든 점수는 100 이하의 양의 정수이다. k이하의 정수라는 사전정보가 있고 이 정보를 이용하여 정렬하므로comparison sort가 아니다. count 알고리즘은 k 가 비교적 작을때 적용할 수있는 알고리즘이다.따라서 k가 5일때 예를 들어 알아보도록 하자 이 때, C라는 배열은 카운터이다.카운트 알고리즘은 입력 배열을 처음부터 끝까지 스캔하면서그 값들이 각각 몇개가 있는지 카운트해서 C라는 배열에 저장해.. 2017. 4. 19. [알고리즘] Sort - 정렬의 Low Bound Sort - 정렬의 Low Bound 앞서 여러가지 정렬을 살펴보았다.그 결과 다음과 같은 질문을 할수 있을것 가다.과연 O(nlogn)이라는 시간복잡도가 최선일까 미리 결론을 이야기하자면 O(nlogn)보다 더 나은 시간복잡도는 없다는 것이다.여기에는 한가지 전제조건이 붙는데Comparison sort(비교 정렬)에 대해서는 보다 더 나은 복잡도가 없다는 것이다. 그렇다면 comparison sort는 무엇일까comparison sort는 데이터와의 크기 관계만을 이용해서 정렬하는 알고리즘이다.따라서 데이터들의 크기관계가 정의되어있다면 어떤 데이터 형 에서도 적용이 가능하다(문자, 알파벳, 사용자 정의 객체 등)따라서 앞서 살펴본 버블, 삽입, 선택, 퀵, 힙 정렬들이 모두 해당된다고 볼 수 있다. 이.. 2017. 4. 19. 이전 1 ··· 23 24 25 26 27 28 29 ··· 38 다음 반응형
