CafeM0ca

12345678910111213141516171819202122232425262728293031323334353637383940414243444546#include void DFS(int n, int d, int s, int arr[]){ if(d == n) { int last_ck = 1; int j = 10-n; for(int i=0; i

Hash Table key를 배열에 mapping하여 삽입/삭제/검색에 사용하는 자료구조. 배열에 key값들이 들어있어서 HashTable이라 한다. 시간복잡도는 $O(1)$의 우수한 성능을 보임 컴퓨터에서는 모든 문자를 숫자로 저장할 수 있음. 따라서 문자도 숫자로 치환하여 저장 가능 e.g) ABC는 각각 ASCII로 65,66,67임. 각 자리수에 대해 128진수로 바꿔주면 $65_128^2 + 66_128^1 + 67*128^0 = 1,073,475$ 이므로 ABC는 1,073,475로 저장된다. 현실적으로 봤을 때 ABC만해도 7자리 자연수로 반환되는데 긴 문자열들은 상상도 할 수 없을만큼 길 것이다. 따라서 해슁된 결과를 m으로 나눈 나머지를 value로 사용하면 메모리에 대한 문제는 해결할 ..

정의 레드블랙트리는 다음 조건을 만족하는 이진탐색트리다. 조건 각 노드는 red 혹은 black이다. 루트 노드는 black이다. 모든 Leaf 노드(NIL 노드)는 black 노드다.(NIL노드: 트리의 각 leaf들이 공통적으로 가리키는 추상적인 노드. root의 부모도 NIL 노드) red 노드의 자식들은 전부 black이다.(red 노드가 연속되어 등장하지 않는다) 모든 노드에 대해서 그 노드로부터 자손인 리프노드에 이르는 모든 경로에는 동일한 개수의 black 노드가 존재한다. 레드블랙트리의 높이 루트노드로부터 NIL 노드를 만날 때까지의 높이를 측정한다. 노드 x의 높이 h(x)는 자신으로부터 리프노드까지의 가장 긴 경로에 포함된 정점의 개수이다. 노드 x의 블랙-높이 bh(x)는 x로부터 리..

heap의 응용 '우선순위 큐는 힙을 응용하여 구현한다' 라는 오류를 갖지 않도록 조심하자. 스택을 배열이나 링크드 리스트로 구현하듯이 우선순위 큐를 heap으로 구현하는 것은 여러 구현체 중 한가지일 뿐이다. 힙과 마찬가지로 (1)최대 우선순위 큐 와 (2)최소 우선순위 큐 2종류가 있다. 우선순위 큐에서는 2가지 연산을 지원한다. insert(x): 새로운 원소 x를 삽입 O(log n) extract_max(): 최대(또는 최소)값을 삭제 O(log n) 이거 한번 해본 것 같은데? 최대 힙 이 문제를 풀면서 heap을 작살나게 정복했다. 구현 template class max_priority_queue{ public: max_priority_queue() { data[0] = 0; }; void ..

자료구조 heap 특징 merge sort처럼 추가 배열이 필요 없음 complete binary tree에 기반함으로 O(nlogn)의 성능을 보임 heap property max heap property: 부모는 자식보다 크거나 같음 min heap property: 부모는 자식보다 작거나 같음 논리적으로는 배열로 구현가능함 루트 노드: A[1] A[i]의 부모 = A[i/2] A[i]의 왼쪽 자식 = A[i*2] A[i]의 오른쪽 자식 = A[i*2+1] 소스코드 heap.hpp #include #include template class max_heap{ public: max_heap(); void insert(type); void remove(type); int find(type); void so..

시간복잡도 최선: NlogN (피벗이 중앙에 위치할 경우) 평균: NlogN 최악: N^2 (분할이 0:10으로 되는 경우) 소스코드 #include #include using namespace std; void generate(vector& v) { random_device rd; mt19937 gen(rd()); uniform_int_distribution dis(1,30); for(int i = 0; i v[r]) { // 오름차순 j++; } else { i++; swap(v[..

std::list를 사용해 구현한 deque 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101#include #include #include using namespace std; template class Deque{private: list element;public: Deque(){} ~Deque(){} void push_front(T& elmnt) { element.push_front(elmnt); } v..

구현한거 맞겠지 O(n^2) 123456789101112131415161718192021222324252627282930313233#include #include #include using namespace std; void printVector(vector& v) { for(auto& i : v) cout

학교 과제로 C로 단일연결리스트 짰다.C++로 구현하면 제네릭 프로그래밍이 가능한데 C는 ... 무안하다. nullptr도 없고 소멸자도없고; 아무튼 링크드리스트의 크기를 명시해주면 삽입,삭제가 수월하다. 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192939495969798991001011021031041051061071081091101111121131141151161171181191201211221231241251261271281291301..

삽입 정렬 로직1.데이터가 있다. 데이터는 두 개 이상이다.2.두번째 요소부터 마지막 요소까지 돈다.3.n번째 요소는 n부터 1까지 돈다.4.만약 n번째 요소가 n-1번째 요소보다 크면 그만 돈다.5.삽입으로 인해 요소들이 밀린다. O(n^2)의 성능을 보인다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849#include using namespace std; inline void ShowArray(int arr[],int); void InsertSort(int arr[],int len){ for(int i=1;i0;j--) //j는 i-1번째 원소 { if(arr[j-1]