Data Structure/Memo
레드블랙트리
자료 : https://zeddios.tistory.com/237 알고리즘 ) Red-Black Tree 안녕하세요 :) Zedd입니다. 오늘은 알고리즘 파티인가요? 이 전글 와 Red-Black Tree가 같은 강의자료에 있길래.. 얼른 iOS글도 써야하는데...ㅎ_ㅎ 뭐 연휴는 기니까.... 히유ㅠㅠ강의자료 보다보니까, zeddios.tistory.com
[C++] stl priority_queue와 heap
heap이란 heap은 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리로 구성된 자료구조이다. - maxheap 최대힙 maxheap에서는 임의의 한 트리가 있을 때에 root 노드는 항상 최대값을 갖는다. - minheap 최소힙 minheap에서는 임의의 한 트리가 있을 때에 root 노드는 항상 최소값을 갖는다. 둘의 공통점 - 이진 탐색 트리와 같이 작은 값이 왼쪽 큰 값이 오른쪽으로 가지않고 자식이 부모보다 max,min인지의 조건에 따라 크거나 작은지를 확인한다. 힙을 이용한다면 최댓값 혹은 최솟값을 O(logN)에 찾을 수 있다. heap의 삽입 과정 maxheap기준 1. 삽입 값을 힙의 마지막 위치에 넣는다. 2. 부모와의 크기를 비교하여 부모가 더 작다면 자식의 값과 부모의 값..
[C++] stl map
map에 대한 설명 - 노드기반으로 이루어진 균형 이진 트리 ( 어느 한 곳을 기준으로 왼쪽은 작은 것이, 오른쪽은 큰 것이 저장 ) - key와 value로 이루어져 있으며 pair의 형태로 저장된다 - key는 중복이 되지 않는다 (multimap에서는 중복을 허용한다) - 삽입, 삭제, 탐색의 시간 복잡도는 O(logN)이다 map의 사용 방법 #include map m;//선언 m.insert(pair("hello", 33));//삽입 m["hello"] = 33;//이런식으로 삽입도 가능 map의 순회방법 map::iterator iter; //방법1 for(iter = m.begin(); iter != m.end(); iter++) { cout first
해시(hash)
- hash_map의 자료구조는 해시 테이블 이다. 해시 테이블에 자료를 저장할 때는 Key 값을 해시 함수에 대입하여 버킷 번호가 나오면 그 버킷의 빈 슬롯에 자료를 저장한다. - hash_map을 사용하는 경우 1. 많은 자료를 저장하고, 검색 속도가 빨라야 한다. 2. 너무 빈번하게 자료를 삽입, 삭제 하지 않는다. - hash 라는 단어가 있느냐 없느냐의 차이다. 'hash'는 정말 큰 차이다. - map과 set 컨테이너는 자료를 정렬하여 저장한다. 그래서 반복자로 저장된 데이터를 순회할 때 넣은 순서로 순회하지 않고 정렬된 순서대로 순회한다. - hash_map, hash_set은 정렬 하지 않으며 자료를 저장한다. 또 hash라는 자료구조를 사용함으로 검색 속도가 map, set에 비해 빠르..
링크드 리스트(Linked List)
- 데이터값과 포인터로 구성 포인터는 다음 데이터값의 주소를 저장 #include #include using namespace std; struct Node { int data; struct Node *next;//다음 노드를 저장 }; Node* head = NULL; Node* tail = NULL; Node* curr = NULL; void CreateNode(int x); void DeleteNode(int x); void PrintNode(); int main() { ios::sync_with_stdio(false); int n = 0; int k = 1; while (k) { cout > n; cout n; CreateNode(n); break; case 2: cout n; DeleteNode..
스택(stack)
- 후입선출 #include #include using namespace std; int main() { ios::sync_with_stdio(false); stack s; s.push(3); s.push(4); s.push(1); s.push(2); cout