프로그래밍/알고리즘 (45) 썸네일형 리스트형 이진 검색 트리(2) 보호되어 있는 글입니다. 이진 검색 트리 (1) 보호되어 있는 글입니다. 트리와 이진트리 검색 트리 (Search Tree) Tree and BinaryTree 트리 (Tree)- 계층적인 구조를 표현한다.조직도 | 디렉토리와 서브 디렉토리 구조 | 가계도 등- 트리는 노드 (node)들과 이를 연결하는 링크 (link)들로 구성되어 있다.맨 위의 노드는 "루트"라고 부른다.노드를 연결하는 선인 링크는 edge, branch등으로도 불린다.- 부모 - 자식 관계 : 상하로 링크되어 있는 두 노드를 비교했을 때 상대적으로 루트에 가까운 노드는 부모 노드, 아래쪽 노드는 자식 노드라고 불린다.- 루트 노드를 제외한 트리의 모든 노드들은 하나의 부모 노드만을 가지고 있다.- 형제 관계 : 같은 부모노드를 가지고 있는 노드들은 서로 형제(sibling)관계라고 부른다.- 리프 노드 : 아래에 자식 .. 자바에서의 정렬 Sorting in Java 기본 타입 데이터의 정렬- Arrays 클래스가 primitive 타입 데이터를 위한 메소드를 제공해준다.int[] data = new int[capacity];// data[0]에서 data[capacity - 1]까지 데이터가 꽉 차있을 경우Arrays.sort(data);//배열이 꽉 차지 않고 data[0]부터 data[size - 1]까지 차있을 경우Arrays.sort(data, 0, size);- int 이외 다른 primitive타입 데이터 (char, double 등)에 대해서도 같은 기능을 제공해준다. 객체의 정렬 - 문자열의 경우- primitive타입 데이터들과 같이 Arrays.sort메소드를 통해 쉽게 정렬이 가능하다.- 기본적으로 문자열은 Strin.. 선형시간 정렬 알고리즘 (2) 보호되어 있는 글입니다. 선형시간 정렬 알고리즘 (1) 선형 시간 정렬 알고리즘 (1) Counting Sort- n개의 정수를 정렬하는데, 모든 정수는 0에서 k사이의 정수라는 사전 지식이 주어지는 정렬법이기 때문에 크기관계만을 이용하여 정렬하지 않고 사전 지식을 적극적으로 활용한다. (k의 크기도 비교적 작은 편이다.)Ex) n명의 학생들의 시험점수를 정렬하라. 단 모든 정수는 100이하의 양의 정수이다.- k = 5인 경우A = 2 5 3 0 2 3 0 3 (n = 8)C(counter) = 2 0 2 3 0 1 => 각 인덱스마다 A배열에서 해당 수가 몇개 들어있는지 세어 저장한다.∴ A = 0 0 2 2 3 3 3 5- 슈도 코드int A[n];int C[k] = {0, };for (int i = 1; i 정렬의 하한점에 대해 정렬의 하한점 (Lower bound) 정렬 알고리즘의 유형- Comparison Sort데이터들 간의 상대적 크기관계만을 이용해 정렬하는 알고리즘따라서 데이터들 간의 크기 관계가 정의되어 있다면 어떤 데이터든 적용이 가능해진다. (문자열, 알파벳, 기타 따로 정의된 객체 등)버블 정렬, 삽입 정렬, 합병 정렬, 퀵 정렬, 힙 정렬 등이 있다.- Non - Comparison Sort정렬할 데이터에 대한 사전지식을 이용한다. 하지만 이는 적용범위가 제한적이라는 한계가 있다.Bucket Sort와 Radix Sort가 대표적으로 알려져있는 정렬 방식이다. 정렬 문제의 최저점- 최저점 (Lower bound)입력된 데이터를 한번씩 다 보기 위해서 최소한 O(n)의 시간복잡도가 필요하다.합병 정렬과 힙 정렬 .. 힙의 응용 - 우선순위 큐 보호되어 있는 글입니다. 이전 1 2 3 4 5 6 다음
