자료구조 & 알고리즘 썸네일형 리스트형 레드블랙 트리(red-black tree) 0. 출처 1) [알고리즘] 제12-1강 red black tree1 2) [알고리즘] 제12-2강 red black tree2 3) [알고리즘] 제12-3강 red black tree3 4) Introduction to Algorithms 1. 개요 1. 1 레드블랙 트리란 이진 탐색 트리에서 탐색, 삽입, 삭제의 시간 복잡도는 O(h)이다. 즉, 트리의 높이에 비례한 만큼의 시간이 걸린다. 원소들이 트리에 잘 분산되어 있다면 별 문제가 없으나, 한 쪽으로 치우친 트리(skewd tree)의 경우에는 높이가 n이 되고, 시간 복잡도도 O(n)이 된다. 랜덤하게 만들어진 이진 탐색 트리는 높이가 lgn임이 보장되나, 현실에서의 데이터는 랜덤하지 않다는 점이 문제가 된다. 예를 들어, 키가 정렬된 상태(1.. [std]set, map set set은 고유한 키를 특정한 순서로 저장하는 컨테이너다. set에 저장되는 원소들은 항상 const와 저장되기 때문에 수정할 수 없다. (삽입이나 삭제는 가능) strict weak ordering criterion에 따라 정렬된다고 하는데 무슨 말인지 모르겠다. 먼저, 을 include해야 한다. int를 저장하는 set은 다음과 같이 만들면 된다.(오름차순) set s; 내림차순으로 정렬하려면 다음과 같이 하면 된다. set s; 오름차순으로 정렬되는 set을 정의했다면 아래와 같이 넣고 출력해도 10, 20, 30, 40, 50이 출력된다. s.insert(10); s.insert(50); s.insert(20); s.insert(40); s.insert(30); 원소를 출력하는 것은 다음과.. 에라토스테네스의 체 에라토스테네스의 체는 소수를 구하는 대표적인 알고리즘이며, 자주 쓰지만 쓸 때마다 헷갈려서 정리했다. 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 #include #include #include using namespace std; #define N 3000 int prime[N + 1]; void che() { prime[0] = -1; prime[1] = -1; for (int i = 2; i 마스터 정리(Master Theorem) 마스터 정리는 재귀를 활용한 점화식을 푸는 방법을 알려준다. 다른 것과 다르게 재귀를 사용한 알고리즘은 시간 복잡도를 구하는 것이 어려운데 마스터 정리를 사용하면 아주 간단하게 해결할 수 있다. 재귀 알고리즘의 점화식은 다음과 같은 형태를 띄고 있다. $$T(n) = aT(n / b) + f(n) (단, a ≥ 1, a > 1, f(n)은 점근적으로 양)$$ f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대하여 f(n)이 양이라는 뜻이다. 점화식에서 a, b, f(n)을 가지고 시간 복잡도를 계산한다. 다음과 같이 세 가지 경우가 있다. 1. $f(n) n^{log_ba}$ 3. $f(n) = n^{log_ba}$ 1의 시간 복잡도 T(n) = θ($n^.. 이진 검색 트리(Binary Search Tree) 자료 출처 1. [알고리즘] 제11-1강 이진검색트리(Binary Search Tree) 2. [알고리즘] 제11-2강 이진검색트리(계속) 3. [알고리즘] 제11-3강 이진검색트리 4. Introduction to Algorithms 12장 트리라는 자료구조는 보통 데이터 자체가 계층적인 구조를 가지고 있을 때 주로 사용한다. 이를테면 조직도, 가계도가 있다. 하지만 검색 트리는 조금 다르다. 검색 트리에 저장되는 데이터들은 반드시 계층적인 구조를 가지고 있을 필요는 없으며, 검색 트리는 데이터를 저장하는 컨테이너로서 역할을 한다. 다른 컨테이너 역할을 하는 자료구조들과 다른 점은 검색 트리는 삽입(Insert), 탐색(Search), 삭제(Delete)와 같은 동적 집합(dynamic set) 연산을.. 해시 테이블(Hash Table) 개요 해시 테이블(Hash Table)은 많은 양의 데이터의 인덱싱(indexing)을 빠르게 해 줌으로써 탐색(Search), 삽입(Insert), 삭제(Delete)의 속도를 높여주는 자료구조다. 그렇기 때문에 해시 테이블은 Database indexing, Caching, Error checking, Password authentication 등 많은 곳에서 쓰이고, dynamic set을 구현하는 데 사용되기도 한다. 자료 출처 1. Hash Tables and Hash Functions 2. [알고리즘] 제13-1강 hashing01 3. Introduction to Algorithms third edition 11장 해시 테이블 위의 배열에서 'Ada'를 찾는 프로그램을 만든다고 하자. 보통 .. 힙정렬(Heap Sort) 개요 힙정렬을 하기 위해서는 '최대힙', '최소힙'의 개념을 알아야 한다. 최대힙은 '두 노드값은 그 부모의 값보다 클 수 없다'는 정의를 만족하는 힙이며, 최소힙은 그와 반대로 '두 노드값은 그 부모의 값보다 작을 수 없다'는 정의를 만족하는 힙이다. 즉, 최대힙에서는 최대값이 루트에 있으며, 최소힙에서는 최소값이 루트에 있다. 최대힙의 성질을 이용해 오름차순 정렬을 할 수 있으며, 최소힙의 성질을 이용해 내림차순 정렬을 할 수 있다. 둘 중 하나만 확실하게 알아놓으면 다른 하나는 반대되는 성질로 인해 쉽게 추론할 수 있으므로 '최대힙을 이용한 오름차순 정렬'만 공부하겠다. 최대힙을 이용한 오름차순 정렬 우선 오름차순으로 정렬해야할 배열이 주어지면 그 배열을 최대힙으로 만든다(buildMaxHeap)... 이전 1 다음
